#74 Search a 2D Matrix
frequently reported atAmazonMicrosoftBloombergGoogleMetaApple
the problem
In plain words
An m×n matrix has each row sorted, and each row's first value is bigger than the previous row's last. Return whether target is in it, in O(log(m·n)).
in matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
out true
in same matrix, target = 13
out false
- 1 ≤ m, n ≤ 100
- -10⁴ ≤ matrix[i][j], target ≤ 10⁴
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBinary search (exact & bounds)
Read row by row, the matrix is one sorted array of length m·n. Index k lives at row k / n, column k % n.
solutions
From brute force to optimal
Two loops, compare each cell.
- For each row, for each value: equal → true.
- Return false.
Every cell once.
No extra structures.
class Solution { public boolean searchMatrix(int[][] matrix, int target) { for (int[] row : matrix) for (int x : row) if (x == target) return true; return false; }}From the top-right corner, a bigger value means drop the column, a smaller one means drop the row.
- r = 0, c = n − 1.
- x > target → c--; x < target → r++; equal → true.
Each step removes a row or a column.
Two indices.
class Solution { public boolean searchMatrix(int[][] matrix, int target) { int r = 0, c = matrix[0].length - 1; // start at the top-right corner while (r < matrix.length && c >= 0) { int x = matrix[r][c]; if (x == target) return true; if (x > target) c--; // everything below in this column is bigger else r++; // everything left in this row is smaller } return false; }}Treat indices 0..m·n−1 as one sorted array and map each mid back to (row, col).
- lo = 0, hi = m·n − 1.
- x = matrix[mid / n][mid % n].
- Classic binary search on x.
One binary search over m·n virtual cells.
No copy is made.
class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length; int lo = 0, hi = m * n - 1; // pretend it is one sorted array while (lo <= hi) { int mid = lo + (hi - lo) / 2; int x = matrix[mid / n][mid % n]; // 1D index → (row, col) if (x == target) return true; if (x < target) lo = mid + 1; else hi = mid - 1; } return false; }}in the room
How to say it in the interview
talk track
- Say the mapping out loud with a tiny example: n = 4, index 6 → row 1, col 2.
traps
- Dividing by m (rows) instead of n (columns) in the index mapping.
what they ask next
Follow-ups
Search a 2D Matrix II (LC 240): rows and columns sorted, but rows don't continue each other?
Flattening no longer works. The staircase from the top-right is the standard O(m + n) answer.
before you submit
Edge cases to test
- A 1×1 matrix.
- A single row, or a single column.
- Target between the last value of one row and the first value of the next.
practise next
Similar problems
- #704Binary SearchEasyin Binary Search
- #33Search in Rotated Sorted ArrayMediumin Binary Search