Skip to main content

20. Search a 2D Matrix II

mediumAsked at N26

Search a value in a 2D matrix sorted both row-wise and column-wise. N26 uses this as a model for indexed lookups in their FX-rate-by-day pivot tables.

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

Problem

Given an m x n matrix where each row is sorted left to right and each column is sorted top to bottom, return true if target exists. Aim better than O(m*n).

Constraints

  • 1 <= n, m <= 300
  • -10^9 <= matrix[i][j] <= 10^9
  • -10^9 <= target <= 10^9

Examples

Example 1

Input
matrix=[[1,4,7,11],[2,5,8,12],[3,6,9,16]], target=5
Output
true

Example 2

Input
matrix=[[1,4,7,11],[2,5,8,12]], target=13
Output
false

Approaches

1. Row-by-row binary search

Binary search each row independently.

Time
O(m log n)
Space
O(1)
for (const row of matrix) {
  let l=0,r=row.length-1;
  while (l<=r) {
    const m=(l+r)>>1;
    if (row[m]===target) return true;
    if (row[m]<target) l=m+1; else r=m-1;
  }
}
return false;

Tradeoff:

2. Staircase from top-right

Start at row 0, last column. If current > target step left; if current < target step down. Each step eliminates a row or a column, giving O(m+n).

Time
O(m+n)
Space
O(1)
function searchMatrix(matrix, target) {
  if (!matrix.length) return false;
  let r = 0, c = matrix[0].length - 1;
  while (r < matrix.length && c >= 0) {
    const v = matrix[r][c];
    if (v === target) return true;
    if (v > target) c--;
    else r++;
  }
  return false;
}

Tradeoff:

N26-specific tips

N26 likes when you note the staircase walk is what their FX-rate lookup uses against the date-by-currency pivot at p99 latency budgets.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →