Skip to main content

57. Search a 2D Matrix

mediumAsked at Salesforce

Search for a target in a row-wise and column-wise sorted matrix where each row's first is greater than the previous row's last. Salesforce uses this to test treating a 2D matrix as a 1D sorted array for binary search.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses similar lookups in indexed-row table scans.
  • Blind (2025)— Tests the 1D-flatten trick.

Problem

You are given an m x n integer matrix matrix with the following 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-step search

Binary search to find the right row; then binary search within that row.

Time
O(log m + log n)
Space
O(1)
function searchMatrix(matrix, target) {
  let lo = 0, hi = matrix.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (matrix[mid][0] <= target && target <= matrix[mid][matrix[0].length - 1]) {
      return matrix[mid].includes(target);
    }
    if (matrix[mid][0] < target) lo = mid + 1; else hi = mid - 1;
  }
  return false;
}

Tradeoff: Two log searches. Works but the cleaner version treats the matrix as 1D.

2. Treat as flat 1D array

Map index 0..m*n-1 to (i, j) = (idx / n, idx % n). One binary search.

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: Single binary search. The (i, j) = (idx / n, idx % n) trick collapses the 2D structure into a 1D sorted array.

Salesforce-specific tips

Salesforce uses this 1D-flatten trick in their indexed-row table scans (records sorted by composite key). They grade on whether you can derive the index mapping cleanly. Bonus signal: explain that LC 240 ('staircase' search) is a DIFFERENT problem because rows-and-cols sorted independently doesn't allow the 1D flatten.

Common mistakes

  • Confusing LC 74 (this) with LC 240 — different invariants.
  • Off-by-one in the high bound (m*n - 1, not m*n).
  • Computing row as idx / m instead of idx / n — col-major vs row-major confusion.

Follow-up questions

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

  • Search a 2D Matrix II (LC 240) — staircase search.
  • Median of two sorted arrays (LC 4).
  • Find smallest k in row+col sorted matrix (LC 378).

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 1D flatten work here but not in LC 240?

LC 74 has a strict total order across the flattened array (last of row i < first of row i+1). LC 240 only has independent row and column orders, so no total flat order exists.

Why mid / n, not mid / m?

Each row has n columns, so the row index is mid / n (number of full rows before mid). The column is mid % n.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →