Skip to main content

58. Search a 2D Matrix

mediumAsked at Ola

Search for a target in a row-and-column-sorted matrix.

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

Problem

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. Integers in each row are sorted from left to right, and the first integer of each row is greater than the last integer of the previous row.

Constraints

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -10^4 <= matrix[i][j] <= 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
same matrix, target = 13
Output
false

Approaches

1. Row-then-column search

Find the row whose last value is >= target; binary-search that row.

Time
O(log m + log n)
Space
O(1)
// 2 binary searches; usually slightly more bookkeeping

Tradeoff:

2. Flatten and binary search

Treat the m*n grid as one sorted array; binary search by mapping mid to (row, col).

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:

Ola-specific tips

Ola asks this to test index mapping fluency; tie it to fast lookup in a flattened sorted ETA matrix indexed by (driver, hour).

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 and other Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →