MediumArrayBinary SearchMatrixUpdated Sep 2026

74. Search a 2D Matrix

Asked at Oracle, Goldman Sachs

Difficulty

Medium

Time

O(log(m * n))

Space

O(1)

Pattern

Array

Companies

2

Problem

You are given an m x n integer matrix with two special properties. First, every row is sorted in non-decreasing order from left to right. Second, the first value of each row is strictly greater than the last value of the row above it. Because of these two rules, the whole matrix is sorted if you read it row by row, like one long list.

Given an integer target, return true if the target appears anywhere in the matrix, and false if it does not.

Your solution must run in O(log(m * n)) time, so scanning every cell is too slow. The trick is to treat the matrix as one virtual sorted array of length m * n and binary search on it. For any index mid in that virtual array, the real cell is at row mid / n and column mid % n, where n is the number of columns.

The matrix reads as one sorted list

matrix012301213571011162023303460target = 3 is found at row 0, column 1.flattened1357101116202330346001234567891011The same data as one sorted array of length 12; index 1 holds the target.
Because each row starts above the previous row's end, reading row by row gives a fully sorted sequence.

Constraints

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

Examples

Example 1
Inputmatrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Outputtrue
WhyThe value 3 sits in the first row, second column. It is present, so we return true.
Example 2
Inputmatrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Outputfalse
Why13 falls between 11 and 16 in the sorted order, but no cell holds that value, so we return false.

Asked At

2 companies
CompanyDifficulty
OracleMediumView all Oracle questions →
Goldman SachsMediumView all Goldman Sachs questions →

How to Think About It

1

Brute force: treat the matrix as a flat array and scan every element one by one — O(m*n) time.

2

Row-by-row binary search: iterate each row and binary search within it — O(m * log n).

3

Staircase search: start from top-right corner, move left if target is smaller, down if larger — O(m + n).

4

Virtual indexing: treat the 2D matrix as a 1D sorted array of length m*n and binary search on it.

5

Optimal: map a 1D index back to (row, col) via row = mid / n, col = mid % n, then binary search — O(log(m*n)).

Optimal Approach

Flatten the 2D matrix conceptually into a 1D sorted array of length m * n. Perform standard binary search on this virtual 1D array. For any mid index, recover the 2D position using row = mid / n and col = mid % n where n is the number of columns. Compare matrix[row][col] with target and narrow the search window accordingly. This achieves O(log(m * n)) time and O(1) space.

Binary search on virtual indices

virtuallo=0 hi=111357101116202330346001234567891011Start with the whole range; mid = 5 gives value 11.virtuallo=0 hi=4135710111620233034600123456789101111 > 3, so drop the right half and keep indices 0..4.virtuallo=hi=11357101116202330346001234567891011mid = 1 gives value 3, which equals the target — return true.row = mid / ncol = mid % ncompare matrix[row][col] to target
We binary search indices 0..11 and map each mid back to a cell with row = mid / n and col = mid % n.
ComplexityTime O(log(m * n))Space O(1)Binary search halves the virtual array of m*n cells each step, and only a few index variables are stored.

What Trips People Up in Real Interviews

1

Clarify whether rows and columns are individually sorted or the entire matrix is sorted row-wise.

2

Confirm the expected time complexity — interviewer usually wants O(log(m*n)), not O(m+n).

3

Explain how you convert between 1D index and 2D coordinates before coding.

4

Edge cases: single element matrix, target smaller than first element or larger than last.

5

Mention that the 1D binary search approach generalizes to any sorted matrix without the first-element-of-row constraint.

Solution Code

O(log(m * n)) time
def search_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    m, n = len(matrix), len(matrix[0])
    lo, hi = 0, m * n - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        val = matrix[mid // n][mid % n]
        if val == target:
            return True
        elif val < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Search a 2D Matrix problem?

You are given an m x n integer matrix where each row is sorted in ascending order and the first integer of each row is greater than the last integer of the previous row. Given a target value, write a function to determine whether the target exists in the matrix. The solution must run in O(log(m * n)) time complexity.

How do you solve Search a 2D Matrix?

The optimal approach runs in O(log(m * n)) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Search a 2D Matrix?

Search a 2D Matrix is asked at Oracle, Goldman Sachs. It is a medium difficulty problem.

What are common mistakes on Search a 2D Matrix?
  • Clarify whether rows and columns are individually sorted or the entire matrix is sorted row-wise.
  • Confirm the expected time complexity — interviewer usually wants O(log(m*n)), not O(m+n).
  • Explain how you convert between 1D index and 2D coordinates before coding.
  • Edge cases: single element matrix, target smaller than first element or larger than last.
  • Mention that the 1D binary search approach generalizes to any sorted matrix without the first-element-of-row constraint.