Search a 2D Matrix

Problem Statement

You are given an m x n integer matrix matrix with the following two properties:

• Each row is sorted in non-decreasing order.
• The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in $O(\log(m \cdot n))$ time complexity.

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

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

Approach: Treat 2D Matrix as 1D Array

Because of the two properties given, if we were to flatten the entire 2D matrix into a single 1D array, the resulting array would be strictly sorted in ascending order.

This means we can perform a standard Binary Search over the conceptual 1D array of length $m \times n$. We just need a way to map a 1D index back to a 2D [row][col] coordinate.

If m is the number of rows and n is the number of columns:

• A 1D index i maps to the 2D row: Math.floor(i / n)
• A 1D index i maps to the 2D column: i % n

1. Let ROWS = matrix.length and COLS = matrix[0].length.
2. Initialize pointers left = 0 and right = ROWS * COLS - 1.
3. Loop while left <= right:
   • Calculate the mid index of the conceptual 1D array: mid = Math.floor((left + right) / 2).
   • Convert mid into 2D coordinates: row = Math.floor(mid / COLS) and col = mid % COLS.
   • The value is val = matrix[row][col].
   • If val === target, return true.
   • If val < target, we need to search the right half, so set left = mid + 1.
   • If val > target, we need to search the left half, so set right = mid - 1.
4. If the loop terminates without finding the target, return false.

Solution

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
function searchMatrix(matrix, target) {
    if (matrix.length === 0) return false;
    
    const ROWS = matrix.length;
    const COLS = matrix[0].length;
    
    let left = 0;
    let right = ROWS * COLS - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        // Map 1D index to 2D coordinates
        const row = Math.floor(mid / COLS);
        const col = mid % COLS;
        const val = matrix[row][col];
        
        if (val === target) {
            return true;
        } else if (val < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return false;
}

Complexity Analysis

• Time Complexity: $O(\log(m \cdot n))$ where $m$ is the number of rows and $n$ is the number of columns. We are performing a standard binary search over a search space of size $m \times n$. This is equivalent to $O(\log m + \log n)$.
• Space Complexity: $O(1)$ since we are only using a few pointers (left, right, mid) and not allocating any extra memory or actually flattening the array.