Skip to main content

58. Search a 2D Matrix

mediumAsked at Snowflake

Search a target in a matrix sorted row-major. Snowflake asks this to test 1D-as-2D binary search — same insight when treating a multi-block column store as a flat sorted sequence for predicate evaluation.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake storage-team uses this to lead into block-level predicate evaluation.
  • LeetCode Discuss (2025-10)— Reported at Snowflake new-grad onsites.

Problem

You are given an m x n integer 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 the 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. Binary search the first column, then the row

Find candidate row by binary search on column 0. Then binary search within that row.

Time
O(log m + log n)
Space
O(1)
// outline only — works but two separate searches.

Tradeoff: Works, but conceptually two passes. Same complexity as the flat-view approach.

2. Treat as flat 1D array (optimal)

Binary search 0..m*n-1, decoding index i as (i/n, i%n) to access the matrix cell.

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 binary search, log(mn). The 1D-as-2D trick is the same insight used to treat block-level storage as a sorted sequence.

Snowflake-specific tips

Snowflake interviewers want the flat-view approach because it's a single clean binary search. Bonus signal: connect to block-level predicate evaluation — when Snowflake's storage layer has multiple sorted blocks of a clustered column, it conceptually treats them as one flat sorted sequence for binary search.

Common mistakes

  • Searching column 0 with > target instead of < target, ending up in the wrong row.
  • Off-by-one when computing high bound (m*n - 1, not m*n).
  • Integer overflow on (lo + hi) in other languages — not an issue in JS Number for these sizes.

Follow-up questions

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

  • Search a 2D Matrix II (LC 240) — row + column sorted but not row-major.
  • How does Snowflake search across multiple sorted micro-partitions?
  • Search in a rotated 2D matrix.

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-view work?

The row-major sortedness + row-boundary-sorted-too property means the matrix, read row-by-row, IS a sorted 1D array of length m*n. Binary search applies directly.

What if rows are sorted but row boundaries aren't?

That's LC 240. You can't binary-search globally; the staircase walk from top-right is O(m+n).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →