Write an efficient algorithm that searches for a
target value in an
m x n integer
matrix has the following properties:
- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matix[i][j] <= 109
- All the integers in each row are sorted in ascending order.
- All the integers in each column are sorted in ascending order.
-109 <= target <= 109
Approach : Search Space Reduction
Because the rows and columns of the matrix are sorted (from left-to-right and top-to-bottom, respectively).
First, we initialize a (row,col) pointer to the bottom-left of the matrix. Then, until we find
target and return
true (or the pointer points to a (row,col) that lies outside of the dimensions of the matrix), we do the following: if the currently-pointed-to value is larger than
target we can move one row "up". Otherwise, if the currently-pointed-to value is smaller than
target, we can move one column "right". It is not too tricky to see why doing this will never prune the correct answer; because the rows are sorted from left-to-right, we know that every value to the right of the current value is larger. Therefore, if the current value is already larger than
target, we know that every value to its right will also be too large. A very similar argument can be made for the columns, so this manner of search will always find
target in the matrix (if it is present).
Check out some sample runs of the algorithm in the animation below:
- Time complexity : O(n+m)
- The key to the time complexity analysis is noticing that, on every iteration (during which we do not return
colis decremented/incremented exactly once. Because
rowcan only be decremented m times and
colcan only be incremented n times before causing the
whileloop to terminate, the loop cannot run for more than n+m iterations. Because all other work is constant, the overall time complexity is linear in the sum of the dimensions of the matrix.
- Space complexity : O(1).