MediumArrayBinary SearchDivide and ConquerMatrixUpdated Sep 2026

240. Search a 2D Matrix II

Asked at Goldman Sachs

Difficulty

Medium

Time

O(m + n)

Space

O(1)

Pattern

Array

Companies

1

Problem

You are given an m x n integer matrix and a target value. The matrix has two sorting rules: each row is sorted in increasing order from left to right, and each column is sorted in increasing order from top to bottom. Return true if the target appears anywhere in the matrix, and false otherwise.

Note that the rows are sorted independently. The last value of one row is not necessarily smaller than the first value of the next row, so you cannot treat the whole matrix as one flat sorted array.

Aim for an efficient search. A solution that visits every cell works, but the sorting rules let you do much better.

Rows and columns both sorted

matrix012340123414711152581219369162210131417241821232630target = 5 lives at row 1, column 1, so the answer istrue
Every row grows to the right and every column grows downward, so the matrix is a set of sorted lines.

Constraints

  • ●m == matrix.length
  • ●n == matrix[i].length
  • ●1 <= n, m <= 300
  • ●-10^9 <= matrix[i][j] <= 10^9
  • ●All the integers in each row are sorted in ascending order.
  • ●All the integers in each column are sorted in ascending order.
  • ●-10^9 <= target <= 10^9

Examples

Example 1
Inputmatrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Outputtrue
WhyThe value 5 sits in row 1, column 1 (0-indexed). It is present, so we return true.
Example 2
Inputmatrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Outputfalse
WhyNo cell holds 20. The values near it are 19 and 21, but 20 itself never appears, so we return false.

Asked At

1 companies
CompanyDifficulty
Goldman SachsMediumView all Goldman Sachs questions →

How to Think About It

1

Brute force scans every cell: O(m * n). Binary searching each row is better at O(m log n), but there is a linear solution.

2

Key insight: start at the top-right corner. Everything to its left is smaller and everything below it is larger. That single cell lets you discard a whole row or a whole column with one comparison.

3

If the current value is greater than the target, the entire column below is even larger — move left. If it is smaller, the entire row to the left is even smaller — move down. If equal, you found it.

4

Walkthrough for target 5 on [[1,4,7,11,15],[2,5,8,12,19],...]: start at 15 -> left to 11 -> left to 7 -> left to 4 -> 4 < 5, down to 5 -> found.

5

Why not the top-left corner? Both neighbors (right and down) are larger, so a comparison does not tell you which direction to eliminate. The bottom-left corner works just as well as top-right.

Optimal Approach

Step 1: Set r = 0, c = n - 1 (top-right).
Step 2: While r < m and c >= 0:
If matrix[r][c] == target: return true.
If matrix[r][c] > target: c -= 1 (eliminate the column).
Else: r += 1 (eliminate the row).
Step 3: Return false.

Each step removes one row or one column, so there are at most m + n steps.

Time: O(m + n). Space: O(1).

Staircase walk from the top-right corner

matrix012340123414711152581219369162210131417241821232630Start at 15. It is bigger than 5, so the whole column4 is too big — move leftmatrix01234012341471115258121936916221013141724182123263011, 7 and 4 are all too big, so we keep moving leftuntil we reach 4matrix0123401234147111525812193691622101314172418212326304 is smaller than 5, so row 0 is too small — move downand find 5v > target → c -= 1v < target → r += 1v == target → return true
At the top-right cell, the row to the left is smaller and the column below is larger, so one comparison kills a whole line.
ComplexityTime O(m + n)Space O(1)Each comparison removes one full row or one full column, so at most m + n steps are taken and only two index variables are stored.

What Trips People Up in Real Interviews

1

Treating it like Search a 2D Matrix I and binary searching a flattened index. The last value of a row is not guaranteed to be smaller than the first value of the next row here.

2

Starting from the top-left or bottom-right corner, where both moves go in the same direction and you cannot eliminate anything.

3

Mixing up the moves. Greater than target means move left (smaller values); less than target means move down (larger values).

4

Not stating the O(m + n) argument. Explain that every comparison permanently removes a row or column — that is the proof.

Solution Code

O(m + n) time
def searchMatrix(matrix, target):
    m, n = len(matrix), len(matrix[0])
    r, c = 0, n - 1
    while r < m and c >= 0:
        v = matrix[r][c]
        if v == target:
            return True
        if v > target:
            c -= 1
        else:
            r += 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 II problem?

Search a 2D Matrix II asks whether a target exists in a matrix where every row is sorted left to right and every column is sorted top to bottom. Unlike the first version, rows do not continue from one another, so you cannot binary search the matrix as one flat array. The elegant answer walks a staircase from a corner.

How do you solve Search a 2D Matrix II?

The optimal approach runs in O(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 II?

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

What are common mistakes on Search a 2D Matrix II?
  • Treating it like Search a 2D Matrix I and binary searching a flattened index. The last value of a row is not guaranteed to be smaller than the first value of the next row here.
  • Starting from the top-left or bottom-right corner, where both moves go in the same direction and you cannot eliminate anything.
  • Mixing up the moves. Greater than target means move left (smaller values); less than target means move down (larger values).
  • Not stating the `O(m + n)` argument. Explain that every comparison permanently removes a row or column — that is the proof.