Back to main article
LC 74 Classic Medium

Search a 2D Matrix

A 2D matrix with a clever property: treat it as a single sorted array and run standard binary search. One index mapping trick does all the work.

Problem

What are we solving?

Problem Statement

Given an m x n integer matrix where each row is sorted left-to-right and the first integer of each row is greater than the last integer of the previous row, return true if target is in the matrix. Must run in O(log(m × n)).

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

Flatten to 1D with an index mapping

Because every row is sorted and the first element of each row is greater than the last element of the previous row, the entire matrix is effectively one long sorted array — just arranged in 2D. We binary search this virtual 1D array and convert each mid index to a row/column on the fly.

matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]] as virtual 1D array
[0,0]1
[0,1]3
[0,2]5
[0,3]7
[1,0]10
[1,1]11
[1,2]16
[1,3]20
[2,0]23
[2,1]30
[2,2]34
[2,3]60
Virtual index 1 maps to row=0, col=1, value=3 = target. Found!

The index mapping formula

For a matrix with cols columns, virtual index mid maps to:

row = mid / cols    col = mid % cols
→

Search space: left = 0, right = m*n - 1. The rest is identical to LC 704 — just swap nums[mid] with matrix[mid/cols][mid%cols].

Solution

Clean implementation

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

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = matrix[mid / n][mid % n]; // 1D → 2D 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:
        m, n = len(matrix), len(matrix[0])
        left, right = 0, m * n - 1

        while left <= right:
            mid = left + (right - left) // 2
            val = matrix[mid // n][mid % n]  # 1D → 2D mapping

            if val == target: return True
            elif val < target: left = mid + 1
            else: right = mid - 1
        return False

Complexity

Time
O(log(m·n))
Binary search over m×n virtual elements.
Space
O(1)
The index mapping is arithmetic — no extra structures.
↑ Pattern map