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
\nAs a baseline, we can search the 2D array the same way we might search an\nunsorted 1D array -- by examining each element.
\nAlgorithm
\nThe algorithm doesn\'t really do anything more clever than what is explained\nby the intuition; we loop over the array, checking each element in turn. If\nwe find it, we return true. Otherwise, if we reach the end of the nested\nfor loop without returning, we return false. The algorithm must return\nthe correct answer in all cases because we exhaust the entire search space.
Complexity Analysis
\nTime complexity : \n
\nBecase we perform a constant time operation for each element of an\n element matrix, the overall time complexity is equal to the\nsize of the matrix.
\nSpace complexity : \n
\nThe brute force approach does not allocate more additional space than a\nhandful of pointers, so the memory footprint is constant.
\nIntuition
\nBecause the rows and columns of the matrix are sorted (from left-to-right and\ntop-to-bottom, respectively), we can prune one row or one\n column when looking at any particular value.
\nAlgorithm
\nFirst, we initialize a pointer to the bottom-left of the\nmatrix.1 Then, until we find target and return true (or the pointer\npoints to a that lies outside of the dimensions of the\nmatrix), we do the following: if the currently-pointed-to value is larger\nthan target we can move one row "up". Otherwise, if the\ncurrently-pointed-to value is smaller than target, we can move one column\n"right". It is not too tricky to see why doing this will never prune the\ncorrect answer; because the rows are sorted from left-to-right, we know that\nevery value to the right of the current value is larger. Therefore, if the\ncurrent value is already larger than target, we know that every value to\nits right will also be too large. A very similar argument can be made for the\ncolumns, so this manner of search will always find target in the matrix (if\nit is present).
Check out some sample runs of the algorithm in the animation below:
\n!?!../Documents/240_Search_a_2D_Matrix_II.json:1280,720!?!
\n\nComplexity Analysis
\nTime complexity : \n
\nThe key to the time complexity analysis is noticing that, on every\niteration (during which we do not return true) either row or col is\nis decremented/incremented exactly once. Because row can only be\ndecremented times and col can only be incremented times\nbefore causing the while loop to terminate, the loop cannot run for\nmore than iterations. Because all other work is constant, the\noverall time complexity is linear in the sum of the dimensions of the\nmatrix.
Space complexity : \n
\nBecause this approach only manipulates a few pointers, its memory\nfootprint is constant.
\nAnalysis and solutions written by: @emptyset
\nThis would work equally well with a pointer initialized to the\ntop-right. Neither of the other two corners would work, as pruning a\nrow/column might prevent us from achieving the correct answer.\xc2\xa0\xe2\x86\xa9
\n