Showing posts with label Search a 2D Matrix Python Leetcode. Show all posts
Showing posts with label Search a 2D Matrix Python Leetcode. Show all posts

Search a 2D Matrix Python Leetcode

 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

Example 1:

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

Example 2:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
Output: false
Main thing to note in this problem : row = pivot // cols and col = pivot % cols 
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or len(matrix) == 0:
            return False
        rows = len(matrix)
        cols = len(matrix[0])
        
        if rows == 1 and cols ==1:
            if target == matrix[rows-1][cols-1]:
                return True
            else:
                return False
       
        left = 0
        right = rows * cols -1
        
        while left <= right:
            pivot = left + (right-left) // 2
            
            if target == matrix[pivot // cols][pivot % cols]:
                return True
            elif target > matrix[pivot // cols][pivot % cols]:
                    left = pivot + 1
            else:
                right = pivot - 1
        return False
Time Complexity : O(logn(mn))
Space Complexity : O(1)

Featured Post

H1B Visa Stamping at US Consulate

  H1B Visa Stamping at US Consulate If you are outside of the US, you need to apply for US Visa at a US Consulate or a US Embassy and get H1...