Skip to main content

56. Search a 2D Matrix

mediumAsked at Vercel

Search a target in an m x n matrix where rows are sorted and each row's first element > previous row's last. Vercel asks this for the 'treat as 1D and binary search' insight — same shape as searching a flattened time-series of edge metrics.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-12)— Vercel screen; 1D binary search trick expected.
  • LeetCode Discuss (2026-Q1)— Listed in Vercel screen pool.

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 on first-column to find candidate row; then binary search within that row.

Time
O(log m + log n)
Space
O(1)
function searchMatrix(matrix, target) {
  // Find row
  let lo = 0, hi = matrix.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >>> 1;
    if (matrix[mid][0] <= target && target <= matrix[mid][matrix[mid].length - 1]) {
      // Search this row
      let l = 0, r = matrix[mid].length - 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;
    }
    if (matrix[mid][0] > target) hi = mid - 1; else lo = mid + 1;
  }
  return false;
}

Tradeoff: O(log m + log n) = O(log(mn)). Acceptable but two searches.

2. Flatten conceptually, one binary search (optimal)

Treat the matrix as a 1D array of length m*n. Binary search; convert flat index to (row, col) via div/mod.

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 r = Math.floor(mid / n);
    const c = mid % n;
    const v = matrix[r][c];
    if (v === target) return true;
    if (v < target) lo = mid + 1; else hi = mid - 1;
  }
  return false;
}

Tradeoff: Single binary search using the index-conversion trick. Cleaner than two searches, same complexity.

Vercel-specific tips

Vercel grades the single-binary-search insight. Bonus signal: explaining the index-conversion (mid -> (mid / n, mid % n)) and noting that the matrix's sorted property makes it behave like a 1D sorted array. They may follow up with LC 240 (row sorted AND column sorted, but no global order) which needs a different staircase approach.

Common mistakes

  • Confusing row and column dividers (mid % m vs mid % n).
  • Off-by-one on the hi bound — must be m * n - 1, not m * n.
  • Applying this technique to LC 240 — that one is different.

Follow-up questions

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

  • Search a 2D Matrix II (LC 240) — row and column sorted but no global order. Staircase from top-right.
  • Find all occurrences in a sorted matrix.
  • Range search — return all elements in [l, r].

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 does the flat-1D trick work?

Because the matrix is row-major sorted AND row-i's last element < row-(i+1)'s first. The concatenation of rows is monotonically non-decreasing — exactly a 1D sorted array.

When does this NOT work?

LC 240's variant: rows and columns each sorted independently but no global order. You'd need a staircase from a corner.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →