Skip to main content

57. Search a 2D Matrix

mediumAsked at Reddit

Search a sorted 2D matrix where each row is sorted and each row's first > previous row's last. Reddit uses this to test the 1D-binary-search-on-flattened-matrix trick.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit phone screen, binary search variant.

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

Approaches

1. Two binary searches

Binary search rows by first-col; then binary search within the candidate row.

Time
O(log m + log n)
Space
O(1)
function searchMatrix(matrix, target) {
  const m = matrix.length, n = matrix[0].length;
  let lo = 0, hi = m - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >>> 1;
    if (matrix[mid][0] <= target && target <= matrix[mid][n-1]) {
      let l = 0, r = n - 1;
      while (l <= r) {
        const m2 = (l + r) >>> 1;
        if (matrix[mid][m2] === target) return true;
        if (matrix[mid][m2] < target) l = m2 + 1;
        else r = m2 - 1;
      }
      return false;
    } else if (matrix[mid][0] > target) hi = mid - 1;
    else lo = mid + 1;
  }
  return false;
}

Tradeoff: Correct and clear. Two stage searches.

2. Treat as flat array, one binary search (optimal)

Index k in flattened array corresponds to (k / n, k % n). Single binary search.

Time
O(log(m * n))
Space
O(1)
function searchMatrix(matrix, target) {
  const m = matrix.length, n = matrix[0].length;
  let lo = 0, hi = m * n - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >>> 1;
    const v = matrix[Math.floor(mid / n)][mid % n];
    if (v === target) return true;
    if (v < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return false;
}

Tradeoff: Single search loop. The (k/n, k%n) decomposition is the entire trick.

Reddit-specific tips

Reddit interviewers want the flatten trick. Bonus signal: explain WHY this works (the matrix is essentially a 1D sorted array reshaped). Mention LC 240 ('Search a 2D Matrix II') uses a different staircase-walk because the property is weaker.

Common mistakes

  • Using parseInt instead of Math.floor for division (works for non-negative ints but Math.floor is clearer).
  • Off-by-one on hi (use m*n - 1).
  • Mixing up row and col in the decomposition.

Follow-up questions

An interviewer at Reddit may pivot to one of these next:

  • Search a 2D Matrix II (LC 240) — rows sorted left-to-right, cols top-to-bottom but rows don't chain. Staircase walk.
  • Kth smallest in sorted matrix (LC 378).
  • Find peak in 2D matrix (LC 1901).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why two binary searches isn't bad?

Same complexity asymptotically. Single search is cleaner code.

What if rows didn't chain?

Then LC 240's staircase O(m + n) — start from top-right, go left or down based on comparison.

Practice these live with InterviewChamp.AI

Drill Search a 2D Matrix and other Reddit interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →