Skip to main content

56. Search a 2D Matrix

mediumAsked at Datadog

Search for a target in a row-sorted matrix where the first element of each row > the last element of the previous row. Datadog asks this to verify you spot the flatten-to-1D trick — same shape as indexing a packed sorted block as if it were a flat array.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — 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: row then column

Binary search for the row that could contain target; then binary search in that row.

Time
O(log m + log n)
Space
O(1)
// Find row r such that matrix[r][0] <= target <= matrix[r][n-1]; then binary search row.

Tradeoff: Works but two binary searches when one suffices.

2. Flatten conceptually + single binary search (optimal)

Treat the matrix as a flat sorted array of length m*n. Index k maps to (k/n, k%n).

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

Tradeoff: Single binary search. The row = k/n, col = k%n mapping is the Datadog-canonical trick for treating a 2D block as 1D — same as their flat-encoded chunk index.

Datadog-specific tips

Datadog grades on the flatten-to-1D insight. The two properties (row-sorted + first-of-row > last-of-prev) together mean the whole matrix is sorted in row-major order, so a 1D binary search works directly. Articulate this BEFORE writing the index math.

Common mistakes

  • Mapping mid to (mid % m, mid / m) instead of (mid / n, mid % n) — uses the wrong dimension.
  • Forgetting that hi is exclusive (half-open) — off by one.
  • Treating this as 'Search a 2D Matrix II' (LC 240) — that's a different problem with weaker constraints.

Follow-up questions

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

  • Search a 2D Matrix II (LC 240) — only rows and columns individually sorted; O(m+n) staircase search.
  • Datadog-style: bisect a row-major chunked TSDB block.
  • Median of Two Sorted Arrays (LC 4) — partition-based bisect.

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 flatten trick work?

The two properties together guarantee row-major sortedness across the whole matrix. So matrix viewed as a 1D array is sorted, and standard binary search applies.

What if only rows are sorted (not the global property)?

Then it's LC 240 — use staircase search starting from the top-right corner. O(m+n) but no log factor possible.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →