Leetcode 74. Search a 2D Matrix

Problem

Leetcode 74 - Search a 2D Matrix

Example:

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

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

Approach

We can solve this problem using Binary Search since we have a sorted matrix.

We can think of each index as such index = row * number of columns + cols - 1 For example if we’re looking at matrix[3][4] from 5x5 matrix, then our index would be 3*5 + 4 - 1 = 18.

We can use this information to get our left and right pointer and even mid pointer

Here is the Python code for the solution:

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        left, right = 0, len(matrix) * len(matrix[0]) - 1
        cols = len(matrix[0])

        while left <= right:
            mid = (left + right) // 2

            # row = index // number of columns
            # col = index % number of columns
            if matrix[mid//cols][mid%cols] < target:
                left = mid+1
            elif matrix[mid//cols][mid%cols] > target:
                right = mid-1
            else:
                return True
        
        return False    

Time Complexity and Space Complexity

Time Complexity: $O(log(n*m))$ where $m$ is number of rows $n$ is number of columns

Space Complexity: $O(1)$