How do you approach Search a 2D Matrix?

The two sorting properties together mean that reading the matrix row by row gives one fully sorted list of m * n values.

What is the time complexity of Search a 2D Matrix?

Time complexity: O(log(m * n)). Space complexity: O(1).

What are common mistakes on Search a 2D Matrix?

Computing the midpoint as (low + high) / 2. In a fixed-width integer language that overflows on large ranges; low + (high - low) / 2 does not. An update that fails to shrink the range, which spins forever on a two-element window. Answering "does it exist" when the question asked for the first or last occurrence - the boundary variants need a different post-loop return.

gitGood.dev

← Back to problems

Search a 2D Matrix

MediumAlgorithms

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.

Example 1

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

Output: true

Example 2

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

Output: false

Example 3

Input: matrix = [[1]], target = 1

Output: true

Constraints

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

Search a 2D Matrix: approach, complexity and pitfalls

A medium binary search problem, graded against 7 test cases (4 of them hidden).

The pattern: Binary Search

Halving a search space each step - on sorted arrays, and on answers themselves.

Reach for it when you see: A sorted input, or a monotonic "is this value feasible?" predicate you can binary search over.

More Binary Searchproblems →

If you are stuck

Show the 3-step hint ladder

The two sorting properties together mean that reading the matrix row by row gives one fully sorted list of m * n values.
Binary search over indices 0 .. m*n - 1 as if the matrix were a single sorted array.
Map a flat index back to a cell with row = Math.floor(idx / n) and col = idx % n (idx // n and idx % n in Python).

The optimal approach

Show the approach: Binary Search on the Virtual Flat Array

Because each row is sorted and rows are stacked in increasing order, the matrix read row-major is one sorted array of `m * n` elements. Binary search over flat indices `0..m*n-1`, translating each midpoint to a cell via `row = mid / n` (integer division) and `col = mid % n`. All indices here are non-negative, so integer division behaves identically in JavaScript (`Math.floor`) and Python (`//`).

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

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Binary Search mistakes

These apply to the pattern as a whole, not just this problem.

Computing the midpoint as `(low + high) / 2`. In a fixed-width integer language that overflows on large ranges; `low + (high - low) / 2` does not.
An update that fails to shrink the range, which spins forever on a two-element window.
Answering "does it exist" when the question asked for the first or last occurrence - the boundary variants need a different post-loop return.

← Back to problems

Search a 2D Matrix

MediumAlgorithms

Description

Example 1

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

Output: true

Example 2

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

Output: false

Example 3

Input: matrix = [[1]], target = 1

Output: true

Constraints

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

Search a 2D Matrix: approach, complexity and pitfalls

A medium binary search problem, graded against 7 test cases (4 of them hidden).

The pattern: Binary Search

Halving a search space each step - on sorted arrays, and on answers themselves.

Reach for it when you see: A sorted input, or a monotonic "is this value feasible?" predicate you can binary search over.

More Binary Searchproblems →

If you are stuck

Show the 3-step hint ladder

The two sorting properties together mean that reading the matrix row by row gives one fully sorted list of m * n values.
Binary search over indices 0 .. m*n - 1 as if the matrix were a single sorted array.
Map a flat index back to a cell with row = Math.floor(idx / n) and col = idx % n (idx // n and idx % n in Python).

The optimal approach

Show the approach: Binary Search on the Virtual Flat Array

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

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Binary Search mistakes

These apply to the pattern as a whole, not just this problem.

Computing the midpoint as `(low + high) / 2`. In a fixed-width integer language that overflows on large ranges; `low + (high - low) / 2` does not.
An update that fails to shrink the range, which spins forever on a two-element window.
Answering "does it exist" when the question asked for the first or last occurrence - the boundary variants need a different post-loop return.