1. Variant 1: Virtual 1D Array Flattening (LeetCode 74)

In LeetCode 74, the matrix satisfies two strict properties: each row is sorted from left to right, and the first integer of each row is strictly greater than the last integer of the previous row. Under these conditions, the entire $M \times N$ matrix behaves as a single continuous sorted 1D array of length $M \times N$.

Rather than performing two separate searches (searching for the row, then searching within the row), an optimal algorithm treats the 2D matrix as a virtual 1D array and executes a single binary search in $O(\log(M \times N))$ time:

• Search Interval: Set low = 0 and high = (rows * cols) - 1.
• Coordinate Transformation: For any virtual 1D midpoint mid, compute the physical 2D matrix coordinates via integer division and modulo arithmetic:

  int row = mid / cols;
  int col = mid % cols;

• Single-Pass Binary Evaluation: If mat[row][col] == target, return true. If less than target, set low = mid + 1; if greater, set high = mid - 1.

2. Variant 2: Staircase Elimination (LeetCode 240)

In LeetCode 240, the condition is relaxed: rows are sorted left-to-right, and columns are sorted top-to-bottom, but row $i$ is not necessarily greater than row $i-1$. The matrix cannot be treated as a single flat array.

Instead, we apply the Staircase Elimination algorithm starting from the top-right corner (row = 0, col = cols - 1):

• The top-right corner possesses an essential mathematical property: it is the maximum element in its row, and the minimum element in its column.
• If mat[row][col] == target, we have found the element.
• If mat[row][col] > target, because the current element is the smallest in its column, no element below it can possibly match. We eliminate the entire column: col--.
• If mat[row][col] < target, because the current element is the largest in its row, no element to its left can match. We eliminate the entire row: row++.
• This guarantees finding the target or concluding its absence in at most $M + N$ steps ($O(M + N)$ time complexity).

3. Production Implementations: Modern C++20 & TypeScript

Below are production-grade implementations of both search paradigms.

C++20 Implementation (Single-Pass Virtual 1D Search)

#include <vector>
#include <cstddef>

class MatrixSearcher {
public:
    // LeetCode 74: O(log(M * N)) virtual 1D binary search
    static bool searchMatrixStrict(const std::vector<std::vector<int>>& matrix, int target) noexcept {
        if (matrix.empty() || matrix[0].empty()) return false;

        const size_t rows = matrix.size();
        const size_t cols = matrix[0].size();
        size_t low = 0;
        size_t high = (rows * cols) - 1;

        while (low <= high) {
            const size_t mid = low + (high - low) / 2;
            const int midVal = matrix[mid / cols][mid % cols];

            if (midVal == target) {
                return true;
            } else if (midVal < target) {
                low = mid + 1;
            } else {
                if (mid == 0) break; // Guard underflow on unsigned size_t
                high = mid - 1;
            }
        }
        return false;
    }

    // LeetCode 240: O(M + N) Staircase Elimination
    static bool searchMatrixStaircase(const std::vector<std::vector<int>>& matrix, int target) noexcept {
        if (matrix.empty() || matrix[0].empty()) return false;

        int row = 0;
        int col = static_cast<int>(matrix[0].size()) - 1;

        while (row < static_cast<int>(matrix.size()) && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] > target) {
                col--; // Eliminate column
            } else {
                row++; // Eliminate row
            }
        }
        return false;
    }
};

TypeScript Implementation with Strict Boundary Types

export function searchMatrix(matrix: number[][], target: number): boolean {
  if (!matrix.length || !matrix[0].length) return false;

  const rows = matrix.length;
  const cols = matrix[0].length;
  let low = 0;
  let high = rows * cols - 1;

  while (low <= high) {
    const mid = Math.floor(low + (high - low) / 2);
    const row = Math.floor(mid / cols);
    const col = mid % cols;
    const val = matrix[row][col];

    if (val === target) return true;
    if (val < target) low = mid + 1;
    else high = mid - 1;
  }

  return false;
}

4. Cache Locality & Hardware Memory Layout

In physical computer hardware, multidimensional arrays are stored in a contiguous linear memory address space. In C++, C, and JavaScript engines, matrices use Row-Major Order: elements of row 0 are contiguous, followed by elements of row 1.

When an algorithm traverses along rows, the CPU's memory management unit (MMU) loads an entire 64-byte cache line containing adjacent integers simultaneously into L1 data cache. Jumping randomly down columns across distant memory addresses incurs frequent cache misses. The Staircase Elimination algorithm balances cache locality by sliding smoothly across adjacent row indices.

5. Algorithmic Complexity Comparison