[LC Walkthrough] 240. Search a 2D Matrix II

Hello world! This is the seventh article of LeetCode Walkthrough.

Today, I’ll be writing about 240. Search a 2D Matrix II. It is the 23rd question of February LeetCoding Challenge 2021.

For this problem, we are asked to write an efficient algorithm that searches for a target value in an m x n integer matrix. Integers in each row/column are sorted in ascending from left to right/top to bottom.

There are many ways to solve this problem. A brute-force search using nested loops will obvious do the job for you. However, it’s not efficient at all (time complexity of O(n²)), and it does not take the advantage that rows and columns are sorted.

A somewhat better solution would be running a binary search on each row. Let us assume that [m = # of rows] and [n = # of columns]. There are m rows and we are running binary search on every row that has size of n. Hence, the time complexity of that solution would be O(m* log(n)). This seems to be within the time complexity limits that LeetCode permits. However…

it is not as efficient as you see. This solution somewhat takes advantage that the matrix is sorted, but not as fully (since we are still going over every row).

Now, imagine if we start from the top-right position of the matrix. Since it is guaranteed that every row and column is sorted, we can assume that every value to the left of current position is less than the value of current position, and every value to the bottom of current position is bigger than the value of current position.

The value decreases along the red arrow’s flow, but increases along the blue arrow’s flow.

Now we can formulate an idea to solve this problem:

• Start from the top-right position of the matrix.
• Check if the current value equals to the target.
• If the current value is smaller than the target, increase the row value.
• If the current value is bigger than the target, decrease the column value.
• Repeat until we find the target.
• If we ever go out of bounce during the search, that means the target value does not exist in the matrix.

With those in mind, we can come up with following solution:

Let us run a simple test case.

The time complexity of this solution is O(m + n) where m = # of rows and n = # of columns. At the worst case, we will have to traverse all the way to the left-bottom of matrix to find out that the target value does not exist. The length of the longest path we can take is m + n, hence the O(m+n) time complexity.

The space complexity of this solution is O(1). We only declare constant size variables in our solution (e.g., currCol, currRow).

Thanks for reading!