Search a 2D Matrix

Problem Statement

Given an m x n matrix where each row is sorted and the first value of each row is greater than the last value of the previous row, return true if target is present.

Example

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

Approach

The matrix behaves like one sorted array of length m*n. Binary search indices 0 .. m*n-1 and map an index to a cell with row = idx / cols, col = idx % cols.

Complexity

• Time: O(log(m * n))
• Space: O(1)

Solution Code

Python

def searchMatrix(matrix, target):
    rows, cols = len(matrix), len(matrix[0])
    left, right = 0, rows * cols - 1
    while left <= right:
        mid = (left + right) // 2
        val = matrix[mid // cols][mid % cols]
        if val == target:
            return True
        elif val < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

Java

boolean searchMatrix(int[][] matrix, int target) {
    int rows = matrix.length, cols = matrix[0].length;
    int left = 0, right = rows * cols - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int val = matrix[mid / cols][mid % cols];
        if (val == target) return true;
        else if (val < target) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

C++

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int rows = matrix.size(), cols = matrix[0].size();
    int left = 0, right = rows * cols - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int val = matrix[mid / cols][mid % cols];
        if (val == target) return true;
        else if (val < target) left = mid + 1;
        else right = mid - 1;
    }
    return false;
}

Key Takeaways

• Index-to-cell mapping: row = idx / cols, col = idx % cols.
• Works only because the whole matrix is globally sorted (row by row).
• Reference: LeetCode 74 (Search a 2D Matrix).