Constant Time
Constant Time
Search a 2D Matrix (mapping function)

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:

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

target = 3
Output: true

Example 2:

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

Leetcode

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. image
    2. There are 3 floors. So a total of 12 spots.
      3. image
  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. image
  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. image
  5. You have reached the 11th car, having covered two floors and two cars.
    6. image
  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.
      2. image
  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.
      2. image
  10. Let's do a test drive with the matrix above
    1. 0th index 
      2. row = 0/4 = (0)
cols = 0 % 4 = (0)

0th at (0,0)
    2. 11th index 
      3. row = 11/4 = (2)
cols = 11 % 4 = (3)

11th at (2,3)
    3. 8th index 
      4. 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.
    12. # 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.
      2. left, right = 0,(len(matrix)*len(matrix[0]))-1
image

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.

Sandbox—PythonTutor (Visualized)

Complexities

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

Space Complexity: O(1)

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

Logo
YouTubeDiscord
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