Skip to main content

56. Search a 2D Matrix

mediumAsked at Plaid

Search for a target in a row-sorted matrix where each row's first element is greater than the previous row's last. Plaid asks this as a binary-search-on-flattened-grid problem before harder bank-feed lookup questions.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid backend OA.
  • LeetCode Discuss (2026)— Plaid SWE II binary search.

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 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 to find the row, then binary search the 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;
    }
    if (target < matrix[mid][0]) hi = mid - 1;
    else lo = mid + 1;
  }
  return false;
}

Tradeoff: Two clean binary searches. Easier to reason about than the flattened version.

2. Treat as flattened sorted array

Binary search over [0, m*n). Map mid back to (row, col) via division.

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[(mid / n) | 0][mid % n];
    if (v === target) return true;
    if (v < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return false;
}

Tradeoff: Single binary search. The (mid/n) | 0 and mid%n collapse the 2D coordinates.

Plaid-specific tips

Plaid grades this on whether you spot the matrix as a 'virtual sorted array.' Bonus signal: derive the index-to-coordinate mapping out loud. Connect to bank-feed lookup where ledger rows are partitioned by date-bucket — you binary-search the bucket, then within it.

Common mistakes

  • Off-by-one when mapping (row, col) from flat index — getting (mid % n, mid / n) backward.
  • Using >> instead of | 0 — works for positive numbers but is semantically less clear.
  • Treating the matrix as if columns were also sorted globally (they aren't necessarily).

Follow-up questions

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

  • Search a 2D matrix II (LC 240) — both rows and columns sorted but not globally.
  • Find Kth smallest in a sorted matrix.
  • Range queries on a sorted 2D structure.

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

The property 'first of each row > last of previous row' makes the matrix equivalent to a single sorted array when read in row-major order.

When can't you flatten?

LC 240 — both axes sorted but rows don't chain. There you start at top-right and step left/down.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →