Python solution with detailed explanation


  • 0
    G

    Solution

    Brute Force: Scan every element and test if it is 1 or not. Keep updating the boundaries of the rectangle. O(mn).

    DFS/BFS: Run DFS from start point and keep updating the boundaries of the rectangle. Big Oh complexity will be of order mn, however in practice, we will be doing O(size_of_rectangle * 4) work.

    class Solution(object):
        def dfs(self, image, x, y, visited):
             self.min_x, self.max_x = min(self.min_x, x), max(self.max_x, x)
             self.min_y, self.max_y = min(self.min_y, y), max(self.max_y, y)
             visited[x][y] = True
             nbrs = [(x-1,y), (x+1,y), (x,y-1), (x,y+1)]
             N, M = len(image), len(image[0])
             for n_x, n_y in nbrs:
                 if n_x >= 0 and n_y >= 0 and n_x < N and n_y < M and image[n_x][n_y] == '1' and visited[n_x][n_y] == False:
                     self.dfs(image, n_x, n_y, visited)
             return
        
        def minArea(self, image, x, y):
            """
            :type image: List[List[str]]
            :type x: int
            :type y: int
            :rtype: int
            """
            if image == []:
                return 0
            if image == ["1"]:
                return 1        
            self.min_x, self.max_x = len(image), -1
            self.min_y, self.max_y = len(image[0]), -1
            visited = [[False]*len(image[0]) for _ in range(len(image))]
            self.dfs(image, x, y, visited)
            return (abs(self.min_x - self.max_x) + 1)*(abs(self.min_y - self.max_y)+1)
    

    Binary Search:

    • Project every column on a 1D array such that if there is any "1" in the column, the projection has a "1". You will therefore have a "00011111000" sort of a projection. You can apply binary search between (0,y-1) and (y, n-1) to find the leftmost and rightmost boundaries. This will be O(mlg(n)).

    • Project every row on a 1D array such that if there is any "1" in the row, the projection has a "1". You will therefore have a "00011111000" sort of a projection. You can apply binary search between (0,x-1) and (x, m-1) to find the leftmost and rightmost boundaries. This will be O(nlg(m)).

    • Total complexity = mlg(n) + nlg(m)

    • https://discuss.leetcode.com/topic/29006/c-java-python-binary-search-solution-with-explanation

    • Project the 2D array into a column array and a row array

    • Binary search to find left in the row array within [0, y)

    • Binary search to find right in the row array within [y + 1, n)

    • Binary search to find top in the column array within [0, x)

    • Binary search to find bottom in the column array within [x + 1, m)

    • Return (right - left) * (bottom - top)

    However, the projection step cost O(mn)O(mn) time which dominates the entire algorithm.If so, we gain nothing comparing with previous approaches.

    The trick is that we do not need to do the projection step as a preprocess. We can do it on the fly, i.e. "don't project the column/row unless needed".Recall the binary search algorithm in a 1D array, each time we only check one element, the pivot, to decide which half we go next. In a 2D array, we can do something similar. The only difference here is that the element is not a number but a vector. For example, a m by n matrix can be seen as n column vectors. In these n elements/vectors, we do a binary search to find left or right. Each time we only check one element/vector, the pivot, to decide which half we go next. In total it checks O(\log n)O(logn) vectors, and each check is O(m)O(m) (we simply traverse all the m entries of the pivot vector). So it costs O(m \log n)O(mlogn) to find left and right. Similarly it costs O(n \log m)O(nlogm) to find top and bottom. The entire algorithm has a time complexity of O(m \log n + n \log m)O(mlogn+nlogm)


Log in to reply
 

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