Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
For example,
Consider the following 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] ]
Given target = 5
, return true
.
Given target = 20
, return false
.
Intuition
As a baseline, we can search the 2D array the same way we might search an unsorted 1D array -- by examining each element.
Algorithm
The algorithm doesn't really do anything more clever than what is explained
by the intuition; we loop over the array, checking each element in turn. If
we find it, we return true
. Otherwise, if we reach the end of the nested
for
loop without returning, we return false
. The algorithm must return
the correct answer in all cases because we exhaust the entire search space.
Complexity Analysis
Time complexity :
Becase we perform a constant time operation for each element of an element matrix, the overall time complexity is equal to the size of the matrix.
Space complexity :
The brute force approach does not allocate more additional space than a handful of pointers, so the memory footprint is constant.
Intuition
Because the rows and columns of the matrix are sorted (from left-to-right and top-to-bottom, respectively), we can prune one row or one column when looking at any particular value.
Algorithm
First, we initialize a pointer to the bottom-left of the
matrix.1 Then, until we find target
and return true
(or the pointer
points to a 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:
!?!../Documents/240_Search_a_2D_Matrix_II.json:1280,720!?!
Complexity Analysis
Time complexity :
The key to the time complexity analysis is noticing that, on every
iteration (during which we do not return true
) either row
or col
is
is decremented/incremented exactly once. Because row
can only be
decremented times and col
can only be incremented times
before causing the while
loop to terminate, the loop cannot run for
more than iterations. Because all other work is constant, the
overall time complexity is linear in the sum of the dimensions of the
matrix.
Space complexity :
Because this approach only manipulates a few pointers, its memory footprint is constant.
Analysis and solutions written by: @emptyset
This would work equally well with a pointer initialized to the top-right. Neither of the other two corners would work, as pruning a row/column might prevent us from achieving the correct answer. ↩