Search a 2D Matrix — Binary Search Patterns That Scale

You're in an interview and the problem gives you a sorted matrix. You know binary search is relevant, but now the data is 2D. Do you flatten it? Search row by row? Most people stall here for 30 seconds while the interviewer watches.

Here's the thing: how you search a matrix depends entirely on what properties the matrix has. There are two common matrix problems in interviews — and the optimal approach for each is completely different. Understanding why unlocks both.

The Pattern: Exploiting Matrix Constraints

Before writing a single line of code, ask: "Is this matrix globally sorted or only row-and-column sorted?" That single question determines your entire approach.

• Globally sorted (each row's first element > previous row's last element): The entire matrix is one big sorted array in disguise. Use binary search with index mapping.
• Row-and-column sorted only: Binary search breaks down. Use the staircase search instead.

Visualizing the Two Approaches

Problem 1: Search a 2D Matrix (LC 74)

The matrix rows are sorted left-to-right, and each row's first element is greater than the previous row's last element. Classic globally-sorted matrix.

Brute Force

The naive approach: check every cell until you find the target.

// Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
// Output: true
 
const searchMatrixBrute = (matrix, target) => {
  for (const row of matrix) {
    for (const val of row) {
      if (val === target) return true;
    }
  }
  return false;
};
// Time: O(m * n) | Space: O(1)

This works but ignores every guarantee the problem gives you. In an interview, saying "I'd start here and then optimize" is fine — but make sure you actually get to the optimization.

Optimized: Treat as 1D Array

The key realization: if you unroll this matrix row by row into a single array, it's perfectly sorted. You don't need to actually create that array — you can map any virtual 1D index back to a 2D coordinate with arithmetic.

For a matrix with n columns:

• row = Math.floor(mid / n)
• col = mid % n

// Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
// Output: true
 
const searchMatrix = (matrix, target) => {
  const m = matrix.length;
  const n = matrix[0].length;
  let lo = 0;
  let hi = m * n - 1;
 
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    // Map virtual 1D index to 2D coordinates
    const midRow = Math.floor(mid / n);
    const midCol = mid % n;
    const val = matrix[midRow][midCol];
 
    if (val === target) return true;
    if (val < target) lo = mid + 1;
    else hi = mid - 1;
  }
 
  return false;
};
// Time: O(log(m * n)) | Space: O(1)

Walk through it on matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3:

• m = 3, n = 4, so virtual indices 0–11
• lo = 0, hi = 11, mid = 5 → matrix[1][1] = 11 > 3 → hi = 4
• lo = 0, hi = 4, mid = 2 → matrix[0][2] = 5 > 3 → hi = 1
• lo = 0, hi = 1, mid = 0 → matrix[0][0] = 1 < 3 → lo = 1
• lo = 1, hi = 1, mid = 1 → matrix[0][1] = 3 === 3 → true

Problem 2: Search a 2D Matrix II (LC 240)

Now the constraints are weaker: rows sorted left-to-right, columns sorted top-to-bottom — but there's no guarantee that a row's first element is larger than the previous row's last element.

This breaks the 1D binary search completely. Consider:

row 0: [1,  4,  7]
row 1: [2,  5,  8]   ← 2 < 4, so global order is violated
row 2: [3,  6,  9]

Unrolled, that reads [1, 4, 7, 2, 5, 8, 3, 6, 9] — not sorted, so the search makes wrong turns. Take target = 3. The midpoint is position 4 (value 5); 5 is bigger than 3, so binary search throws away the entire right half — including position 6, which is exactly where the 3 lives. It reports false for a value that is in the matrix. The same thing happens for targets 2, 7 and 8.

Brute Force

Same O(m × n) scan, but you're now throwing away both of the problem's guarantees.

// Input: matrix = [[1,4,7,11],[2,5,8,12],[3,6,9,16]], target = 5
// Output: true
 
const searchMatrixIIBrute = (matrix, target) => {
  for (const row of matrix) {
    for (const val of row) {
      if (val === target) return true;
    }
  }
  return false;
};
// Time: O(m * n) | Space: O(1)

Optimized: Staircase Search

The insight is to find a pivot point that lets you eliminate an entire row or column with each comparison. The top-right corner is that pivot:

• It's the maximum of its row (moving left means smaller values)
• It's the minimum of its column (moving down means larger values)

So: if the current value is larger than target, move left (eliminate that column). If smaller, move down (eliminate that row). Each step eliminates an entire row or column — you can make at most m + n moves total.

// Input: matrix = [[1,4,7,11],[2,5,8,12],[3,6,9,16]], target = 5
// Output: true
 
const searchMatrixII = (matrix, target) => {
  // Start at the top-right corner — the staircase pivot
  let row = 0;
  let col = matrix[0].length - 1;
 
  while (row < matrix.length && col >= 0) {
    const val = matrix[row][col];
 
    if (val === target) return true;
    if (val > target) col--;   // too big — eliminate this column
    else row++;                // too small — eliminate this row
  }
 
  return false;
};
// Time: O(m + n) | Space: O(1)

Let's trace through matrix = [[1,4,7,11],[2,5,8,12],[3,6,9,16]], target = 5:

• [0,2] = 7 > 5 → col = 1
• [0,1] = 4 < 5 → row = 1
• [1,1] = 5 === 5 → true ✓

Problem 3: Returning the Position, Not a Boolean

Some problems ask you to return the exact position (row and column index) rather than a boolean. The approach for LC 74 extends without changing the search at all:

// Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 16
// Output: [1, 2]  (row 1, col 2)
 
const searchMatrixPosition = (matrix, target) => {
  const m = matrix.length;
  const n = matrix[0].length;
  let lo = 0;
  let hi = m * n - 1;
 
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    const midRow = Math.floor(mid / n);
    const midCol = mid % n;
    const val = matrix[midRow][midCol];
 
    if (val === target) return [midRow, midCol];
    if (val < target) lo = mid + 1;
    else hi = mid - 1;
  }
 
  return [-1, -1];
};
// Time: O(log(m * n)) | Space: O(1)

The index math (Math.floor(mid / n), mid % n) is the exact same trick — just return coordinates instead of a boolean.

Complexity Cheat Sheet

Interview Tips

Clarify constraints before coding. "Is each row's first element greater than the previous row's last?" is a one-sentence question that determines your entire strategy. Interviewers respect candidates who identify this distinction without being told.

Internalize the index math. Math.floor(mid / n) for row and mid % n for column — write this down on the whiteboard first and refer back to it. This eliminates the cognitive load of re-deriving it while you're trying to think through the algorithm.

The staircase search is the one people forget. For LC 240, most candidates either scan row by row (O(m × n)) or waste 10 minutes trying to make binary search work. If you know the staircase pattern cold, you'll distinguish yourself. Remember: top-right corner, eliminate row or column with every step.