Search a 2D Matrix II

Prerequisites: 🍦Binary Search(Vanilla) , Search a 2D Matrix (mapping function)

Question

Write an algorithm to search a 2D matrix for a given value. The matrix contains integers sorted in ascending order from left to right in each row and from top to bottom in each column.

Example 1:

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
Output: true

Leetcode

Reframing the question

We can’t use the mapping function as in Search a 2D Matrix (mapping function). As the indexes after mapping don’t retain the monotonic (ascending) nature.

Intuition

In 🍦Binary Search(Vanilla) we picked an element as a midpoint. Compared it to our target. If the element we picked was larger than the target. We could be sure that the target could not be in the elements greater than the value we chose. So we disregarded all the elements after it.
How will our approach change when we are in a matrix which is sorted in ascending order from left to right in each row and from top to bottom in each column.
We need to decide where to start our search, so let's start with the top right element. Starting from the bottom right or the top left element is not the best option because those are the largest and smallest value, so we won't be able to reduce the search space more than 1 item every time. The most commonly used option is to start from the top right element, which can be considered an abstract midpoint. The bottom left element is also an option.
Where is the target in terms of the element we are on? Instead of going left or right like in binary search, we move between rows and columns, eliminating the rows and columns where the target cannot be. Let go over a few examples and generalize the solution.

If we are on the topmost value in a column, which happens to be 15 all elements after it is greater than 15. If 15 is greater than 5, can we disregard all the elements in the column as they will also be greater than 5? Once we get rid of the column our search space will be reduced.

Following the example of 15, we can be sure that the same will be true for 7 and 11 since both of them are less than 5, and all the elements below them in the column will also be less than 5. Now onto 4.

Now things become more interesting regarding 4. Where is 5? Since all elements in the column below are greater than 4, 5 could be in that column, so we can't disregard it. What can we disregard? Since 4 occupies a place in ascending order, all elements before 4 are less than 5. We can disregard the whole row before 4 and the value of 4 itself. YES! We can remove the entire row of the matrix because all of the values greater than 5 were disregarded before reaching 4. And the ones left are less than 5. So, we can be sure that 5 is not in that row.
We got rid of the row we came one row down and ended up at 5 and found our target 🎉

We keep removing the rows and columns that do not contain the desired value (in this case, 5) until we have found the target or run out of elements to search through.

When we are removing the column we are reducing the value we are on as we move to the next column to the left.

From 15 to 11 to 7 getting closer to 5

When we are removing a row we are increasing the value as we are moving down the column.

from 4 to 5

We are removing items greater than or less than the target as we move toward the target. So if there is a target we will find it before the search space is missed.

Implementation

Starting range in 🍦Binary Search(Vanilla) where the search space is 1D is from 0 to len(nums)-1 . What is the search space here?

Column Seach space.

FROM : 0
To: len(matrix[0]) - 1

Row search space.

FROM : 0
TO: len(matrix) - 1

Matrix search space comes down to.


#legal range
colsfFrom = 0
rowsFrom = 0
colsTo = len(matrix[0])-1
rowsTo = len(matrix)-1

while (rowsFrom <= row and row <= rowsTo) and (
            colsfFrom <= col and col <= colsTo
        ):

The starting element is located at the top right where (row, column).

row = 0 
col = len(matrix[0]) - 1

While in legal range.

If target found

# while legal condition

	on = matrix[r][c]
	
	if on == target:
	   return True

Eliminating row, if the element we are on is less than the target, removing all elements in the row are fair game.

elif on < target:
  row+=1

Eliminating col, if the element we are on is greater than the target, removing all elements in the col are fair game.

	elif on > target:
     col-=1

If the range is exhausted we simply return False.

while (rowsFrom <= row  and row <= rowsTo ) and ( colsfFrom <= col and col <= colsTo):

	#if found return instantly.

# exit while loop          
return False

Code

Sandbox—PythonTutor (Visualized)

Complexities

Time Complexity: O(N+M)

N = len(rows)

M = len(cols)

Space Complexity: O(1)

We eliminate each row or column until there are no columns or rows left. The maximum number of iterations we will make is (m+n).

Dedications

💡

Great Video on this problem

class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: colsfFrom = 0 rowsFrom = 0 colsTo = len(matrix[0])-1 rowsTo = len(matrix)-1 # Starting element #top right row = 0 col = len(matrix[0]) - 1 while (rowsFrom <= row and row <= rowsTo ) and ( colsfFrom <= col and col <= colsTo): on = matrix[row][col] if on == target: return True elif on > target: col-=1 elif on < target: row+=1 return False