Python solution with detailed explanation


  • 0
    G

    Solution

    Search a 2D Matrix https://leetcode.com/problems/search-a-2d-matrix/?tab=Description

    O(M + log(N)) Solution

    1. Very simple problem. Just apply binary search sequentially in each row. O(M + log(N))
    2. Notice the nice syntax:
      if matrix[i][0] <= target <= matrix[i][N-1]:
    class Solution(object):
        # M + log(N) solution
        def bsearch(self, nums, low, high, target):
            while low <= high:
                mid = low + (high-low)//2
                if nums[mid] == target:
                    return True
                elif nums[mid] > target:
                    high = mid-1
                else:
                    low = mid+1
            return False
        
        def searchMatrix(self, matrix, target):
            """
            :type matrix: List[List[int]]
            :type target: int
            :rtype: bool
            """
            M = len(matrix)
            if M == 0:
                return False
            N = len(matrix[0])
            if N == 0:
                return False
            for i in range(M):
                if matrix[i][0] <= target <= matrix[i][N-1]:
                    return self.bsearch(matrix[i], 0, N-1, target)
            return False
    

    O(log(M)) + O(log(N)) Solution

    1. Use binary search to select the right row. Then use binary search to search within a column,
    class Solution(object):
        # O(log(M)) + O(log(N))
        def bsearch(self, nums, low, high, target):
            while low <= high:
                mid = low + int((high-low)/2)
                if nums[mid] == target:
                    return True
                elif nums[mid] > target:
                    high = mid-1
                else:
                    low = mid+1
            return False
        
        def searchMatrix(self, matrix, target):
            """
            :type matrix: List[List[int]]
            :type target: int
            :rtype: bool
            """
            M,N = len(matrix), len(matrix[0])
            low, high = 0, M-1
            while low <= high:
                mid = low + (high-low)//2
                if matrix[mid][0] <= target <= matrix[mid][N-1]:
                    return self.bsearch(matrix[mid], 0, N-1, target)
                elif target > matrix[mid][N-1]:
                    low = mid+1
                elif target < matrix[mid][0]:
                    high = mid-1            
            return False
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.