DSA · Binary Search · #158
Search a 2D Matrix
Module 59 · difficulty 3/5·⏱ 30:00starts on first keystroke
You are given an `m x n` integer matrix where each row is sorted in non-decreasing order, and the first integer of each row is greater than the last integer of the previous row. Implement `searchMatrix(matrix, target)` that returns `true` if `target` is present in the matrix and `false` otherwise. Aim for `O(log(m*n))` time.
Examples
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3→true— 3 lives in the first row.matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13→false— 13 would sit between 11 and 16 but is absent.matrix = [[1]], target = 1→true
Constraints
- · m == matrix.length
- · n == matrix[0].length
- · 1 <= m, n <= 100
- · -10^4 <= matrix[i][j], target <= 10^4
- · Every row is sorted and rows are globally ordered (flattening yields one sorted array).
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.