Skip to main content

74. Search a 2D Matrix

medium

Search a row-sorted matrix where each row begins after the previous row ends. The 'flatten in your head' binary search — a common phone-screen warm-up at FAANG.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

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

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

The constraints mean the matrix flattened in row-major order is one big sorted array.

Hint 2

Treat the matrix as a 1-D array of length m*n. Use binary search over indices 0..m*n - 1.

Hint 3

Convert index idx to (row, col) via idx / n and idx % n.

Hint 4

O(log(m * n)) — strictly better than 'binary search each row' (which is O(m log n)).

Solution approach

Reveal approach

Treat the matrix as a flattened sorted array of length m * n. Binary search over the flat index space: lo = 0, hi = m * n - 1. While lo <= hi: mid = lo + (hi - lo) / 2; convert mid back to a 2-D position via row = mid / n, col = mid % n. Read val = matrix[row][col]. If val == target return true; if val < target, lo = mid + 1; else hi = mid - 1. Return false if the loop exits. O(log(m * n)) time, O(1) space. Note that 'binary search to find the right row, then binary search inside it' is also O(log m + log n) = O(log(mn)) — both work; the flat-index version is just a single loop.

Complexity

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

Related patterns

  • binary-search
  • matrix

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Search a 2D Matrix and Binary Search problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →