Search a 2D Matrix
Medium · Binary Search · Array · Binary Search · Matrix
Problem
You are given an m x n integer matrix with two properties: each row is sorted in non-decreasing order, and the first value of every row is greater than the last value of the row above it. Read row by row, the matrix is one sorted list.
Given an integer target, return True if it occurs in the matrix, otherwise False. Your solution must run in O(log(m · n)) time.
Examples
Input: matrix = [[2,4,7],[10,11,15],[20,26,31]], target = 11 Output: true
11 is the middle element of the flattened list.
Input: matrix = [[2,4,7],[10,11,15],[20,26,31]], target = 8 Output: false
8 would fall between 7 and 10 but is not present.
Input: matrix = [[1,3,5,7,9]], target = 7 Output: true
A single row is just a sorted list.
Constraints
- m == len(matrix), n == len(matrix[i])
- 1 <= m, n <= 100
- -10^4 <= matrix[i][j], target <= 10^4
Approaches
- Scan every cell — time O(m·n), space O(1)
Follow-up
If rows are sorted and columns are sorted but a row may start below the end of the previous one, the matrix is no longer one sorted list. Then start at the top-right corner: each comparison discards a row or a column, for O(m + n).
Related problems
Start free on Cariara · Coding problems · System design studio
