Search a 2D Matrix (mapping function)

Prerequisites: 🍦Binary Search(Vanilla)

Question

Search an element in a matrix of m*n where integers in each row are sorted from left to right and the first integer of each row is greater than the last integer of the previous row.

Example 1:

Copy

matrix = 
[[1,3,5,7],
[10,11,16,20],
[23,30,34,60]]

target = 3
Output: true

Example 2:

Copy

matrix = 
[[1,3,5,7],
[10,11,16,20],
[23,30,34,60]] 
target = 13
Output: false

Reframing the question

1. We have integers sorted from left to right, and this sorting continues with each new level.
2. Imagine each row is a floor in a carpark
1. Each floor has 4 spaces

2. There are 3 floors. So a total of 12 spots.

3. If you travel in a linear fashion and keep track of the cars you have passed, when you are on the first car. You have covered 0 floors and 0 cars.

4. You are on the fifth car. You have covered one floor, instead of 4 cars we can say you have covered one floor.

5. You have reached the 11th car, having covered two floors and two cars.

6. To cover each floor you have to go through 4 cars. Let's formalize it with a mathematical equation.
7. We are at the 5th car means we have covered 4 cars.
1. How many floors have we covered?
1. We have covered 1 floor: 4 divided by 4 equals 1.
2. What parking space on a particular floor(1)?
1. We have covered 0 parking spaces: 4 modulo 4 (remainder) equals 0.
3. With the 5th car, we have covered 1 floor and 0 parking spaces.
8. Bringing that analogy to the matrix, each row represents a floor and each column represents the parking space on that floor. The index of the matrix represents how many cars you have covered. One other thing to consider is that the parking lot is upside down, compared to the matrix
1. Since the indexes in arrays start from zero, we used the analogy of cars covered versus one car. This made the math work out.

9. How can we formalize this from floors to rows and parking space to cols?
1. Why are we dividing it by cols, in each floor, there was a set number of parking spaces that can represent cols in a row.

10. Let's do a test drive with the matrix above
1. 0th index
Copy

row = 0/4 = (0)
cols = 0 % 4 = (0)

0th at (0,0)

2. 11th index
Copy

row = 11/4 = (2)
cols = 11 % 4 = (3)

11th at (2,3)

3. 8th index
Copy

row = 8/4 = (2)
cols = 8 % 4 = (0)

11th at (2,0)

11. Since the number of cols can be dynamic we can formalize this to code.
Copy

# mapping 1D -> 2D
row = midpoint // len(matrix[0])
col = midpoint % len(matrix[0])

12. With the mapping function, we have reduced the problem from 2 dimensions (2D) to 1 dimension (1D), by ensuring that the elements retain their increasing monotonic structure in one dimension, which allows us to use a regular 🍦Binary Search(Vanilla) .
1. Left and right pointers mapped.
Copy

left, right = 0,(len(matrix)*len(matrix[0]))-1

Implementation

1. We map 2D rows and columns to indexes, allowing us to use binary search. Simple as that.
1. Instead of returning the index, we return True if found and False if not.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        
        left, right = 0,(len(matrix)*len(matrix[0]))-1
        
        while left <= right:
            
            midpoint = left + ((right-left)//2)
          
            # mapping 1D -> 2D
            
            row = midpoint // len(matrix[0])
            col = midpoint % len(matrix[0])
          
        
            value = matrix[row][col]
            
            
            if value == target:
                return True
            elif value > target:
                right = midpoint - 1
            elif value < target:
                left = midpoint+1
                
                
        return False

Sandbox—PythonTutor (Visualized)

Complexities

Time Complexity: O(log(rows * cols))

Space Complexity: O(1)

📐Understanding Time Complexity of OLog(N): Math + Intuition