Search a 2D Matrix

Problem Description

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 * n)) time complexity.

Examples

Constraints

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -10⁴ <= matrix[i][j], target <= 10⁴

Virtual 1D Coordinate Mapping

Since each row is sorted and the first element of a row is larger than the last element of the previous row, the entire matrix can be treated as a single sorted 1D array of length m * n. We can run a standard binary search on this virtual 1D array. To map a 1D index mid back to its 2D coordinates (row, col) in a matrix with n columns, use: row = mid / n and col = mid % n. This allows us to search the entire matrix in O(log(m * n)) time without using extra space.

Solution 1: Virtual 1D Binary Search

Run a single binary search across all cells using index division and modulo mapping.

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0;
        int right = m * n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = matrix[mid / n][mid % n]; // virtual 1D mapping

            if (val == target) {
                return true;
            } else if (val < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        m, n = len(matrix), len(matrix[0])
        left = 0
        right = m * n - 1

        while left <= right:
            mid = left + (right - left) // 2
            val = matrix[mid // n][mid % n]  # virtual 1D mapping
            
            if val == target:
                return True
            elif val < target:
                left = mid + 1
            else:
                right = mid - 1
                
        return False

#include <vector>

class Solution {
public:
    bool searchMatrix(std::vector<std::vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        int m = matrix.size();
        int n = matrix[0].size();
        int left = 0;
        int right = m * n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = matrix[mid / n][mid % n]; // virtual 1D mapping

            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 * n)) as standard binary search splits the search range of size m * n in half at each step.
• Space Complexity: O(1) auxiliary space as we search in place using coordinate pointers.

Where It Breaks

This virtual 1D mapping technique relies on the condition that the first element of each row is greater than the last element of the previous row. If this condition is not met (e.g. Search a 2D Matrix II where rows and columns are sorted independently), we cannot treat the grid as a single flat sorted array. Under those conditions, we must start search from the top-right corner and move left/down in O(m + n) time.

Common Mistakes

• Incorrect index formula: Mapping 2D coordinates using row count m instead of column count n (e.g. writing mid / m or mid % m).
• Integer overflow in index calculation: Using (left + right) / 2 instead of left + (right - left) / 2 when computing the midpoint index.

Frequently Asked Questions

Why does division by n map to the row index? Each row contains exactly n elements. Therefore, the number of full rows skipped by index mid is mid / n (using floor division).

Can we run two binary searches instead? Yes. You can run one binary search on the first column to identify the correct row, then a second binary search on that row. Both approaches have the same O(log m + log n) = O(log(m * n)) time complexity, but the virtual 1D approach is cleaner to write.

← All Problems