Search a 2D Matrix

Concept

LeetCode #74.
Problem: Write an efficient algorithm that searches for a value target in an m x n integer matrix. This matrix has the following properties:

1. Integers in each row are sorted from left to right.
2. The first integer of each row is greater than the last integer of the previous row.

Input: matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
], target = 3
Output: true

If you read the numbers left-to-right, top-to-bottom, they form one perfectly continuous, sorted array: [1, 3, 5, 7, 10, 11, 16...].

The Strategy

You could just loop through the rows and Binary Search the specific row that contains your target. That takes $O(M + \log N)$ time.

The Optimal Approach ($O(\log(M \times N))$):
Because the matrix acts like one massive sorted array, we can pretend it IS a 1D array!
We run a standard Binary Search from index 0 to index (Rows * Cols) - 1.

The only trick is mathematically translating the 1D mid index back into a 2D [row][col] coordinate so we can read the value from the matrix.

The Math Formula:

• Row = Math.floor(mid / Cols)
• Col = mid % Cols

Let’s test it. The matrix has 4 columns. We want to find the 2D coordinate of 1D index 5 (the number 11).

• Row = Math.floor(5 / 4) = 1
• Col = 5 % 4 = 1
• matrix[1][1] is indeed 11. The math is flawless!

Implementation

// Time Complexity: O(log(M * N))
// Space Complexity: O(1)

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

    const rows = matrix.length;
    const cols = matrix[0].length;

    // Treat the matrix as a 1D array
    let left = 0;
    let right = (rows * cols) - 1;

    // Standard Binary Search
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);

        // Translate the 1D mid index back to 2D coordinates
        const r = Math.floor(mid / cols);
        const c = mid % cols;

        const midValue = matrix[r][c];

        if (midValue === target) {
            return true; // Found it!
        } else if (midValue < target) {
            left = mid + 1; // Target is larger, move right
        } else {
            right = mid - 1; // Target is smaller, move left
        }
    }

    return false; // Not found
}

The “Search a 2D Matrix II” Variation

LeetCode #240. What if the matrix is sorted differently?
Properties:

1. Integers in each row are sorted in ascending from left to right.
2. Integers in each column are sorted in ascending from top to bottom.
   (Notice it does NOT guarantee the next row starts higher than the previous row!).

Because the linear wrap-around is broken, the 1D flattening math completely fails. We cannot use standard Binary Search.

The Trick (The Staircase Search):
We start our pointer at the Top-Right Corner.

• Is the current value the target? Return true!
• Is the current value larger than the target? Because the column is sorted downwards, everything below us is even larger. We mathematically eliminate the entire column! Move Left.
• Is the current value smaller than the target? Because the row is sorted leftwards, everything to our left is even smaller. We mathematically eliminate the entire row! Move Down.

This elegantly slices through the matrix, finding the target in $O(M + N)$ time.

Interview Questions

Q: In the Staircase Search (Matrix II), why do we specifically start at the Top-Right corner (or Bottom-Left)? Why not Top-Left?
A: The strategy requires every step to make a definitive Binary choice.
If we start Top-Right, moving Left strictly decreases the value, and moving Down strictly increases the value. The decision tree is perfect.
If we start Top-Left, both moving Right AND moving Down will increase the value. If our target is larger, we have absolutely no mathematical way of knowing whether we should move Right or move Down to find it. The logic completely breaks.