Search a 2D Matrix
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 that runs in O(log(m * n)) time.
Example 1
1 3 5 7 10 11 16 20 23 30 34 60
Input
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3Output
trueThe value 3 appears in the first row of the matrix.
Example 2
1 3 5 7 10 11 16 20 23 30 34 60
Input
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13Output
falseThe value 13 does not appear anywhere in the matrix.
Constraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 100
- -10^4 <= matrix[i][j], target <= 10^4
Asked at 19 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.