Given an m x n matrix where each row is sorted in ascending order and the first element of each row is greater than the last element of the previous row, determine if a target value exists in the matrix.
For example, given matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]] and target = 3, the output is true. For target = 13, the output is false.
Explain your approach, how you treat the 2D matrix as a 1D problem, and analyze time and space complexity.
How to approach it
- Hint 1
The matrix is fully sorted if you read it row by row. Can you treat it as a single sorted array?
- Hint 2
Map a 1D index to 2D coordinates: row = index / columns, col = index % columns.
- Hint 3
Standard binary search on the virtual 1D array gives you O(log(m * n)) time.
Ready to answer it out loud?
Record your answer in 1:00 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.