221.Maximal Square

Tags: [matrix], [dp], [two_dimension_dp]

Com: {fb}

Link: https://leetcode.com/problems/maximal-square/#/description

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

Solution: DP, Two Dimension DP

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix or not matrix[0]:
            return 0

        num_of_rows = len(matrix)
        num_of_cols = len(matrix[0])

        edges = [[0 for _ in xrange(num_of_cols)] for _ in xrange(num_of_rows)]
        max_edge_len = 0
        for col in xrange(num_of_cols):
            edges[0][col] = int(matrix[0][col])
            max_edge_len = max(max_edge_len, edges[0][col])

        for row in xrange(num_of_rows):
            edges[row][0] = int(matrix[row][0])
            max_edge_len = max(max_edge_len, edges[row][0])

        for row in xrange(1, num_of_rows):
            for col in xrange(1, num_of_cols):
                if matrix[row][col] == '1':
                    edges[row][col] = min(edges[row - 1][col], edges[row][col - 1], edges[row - 1][col - 1]) + 1
                    max_edge_len = max(max_edge_len, edges[row][col])

        return max_edge_len * max_edge_len

Revelation:

• edges[row][col] is recording the edge_len of the square whose right_bottom is [row][col].
• DP state equation: edges[row][col] = min(edges[row - 1][col], edges[row][col - 1], edges[row - 1][col - 1]) + 1.

Note:

• Time complexity = O(m*n), m is the number of rows, n is the number of cols.
• Space complexity = O(m*n), m is the number of rows, n is the number of cols.

Time Limited Exceeded

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix or not matrix[0]:
            return 0

        num_of_rows = len(matrix)
        num_of_cols = len(matrix[0])

        sums = [[0 for _ in xrange(num_of_cols)] for _ in xrange(num_of_rows)]
        sums[0][0] = int(matrix[0][0])
        for col in xrange(1, num_of_cols):
            sums[0][col] = sums[0][col - 1] + int(matrix[0][col])
        for row in xrange(1, num_of_rows):
            sums[row][0] = sums[row - 1][0] + int(matrix[row][0])

        for row in xrange(1, num_of_rows):
            for col in xrange(1, num_of_cols):
                sums[row][col] = int(matrix[row][col]) + sums[row - 1][col] + sums[row][col - 1] - sums[row - 1][col - 1]

        max_area = 0
        for row in xrange(num_of_rows):
            for col in xrange(num_of_cols):
                if matrix[row][col] == '0':
                    continue

                for edge_len in xrange(1, min((row - 0 + 1), (col - 0 + 1)) + 1):
                    if matrix[row - (edge_len - 1)][col - (edge_len - 1)] == '0':
                        break

                    area = self.calculate_area(sums, row, col, edge_len)
                    if area == edge_len ** 2:
                        max_area = max(max_area, area)

        return max_area

    def calculate_area(self, sums, row, col, edge_len):
        result = sums[row][col]
        if row - edge_len >= 0:
            result -= sums[row - edge_len][col]
        if col - edge_len >= 0:
            result -= sums[row][col - edge_len]
        if row - edge_len >= 0 and col - edge_len >= 0:
            result += sums[row - edge_len][col - edge_len]

        return result

Revelation:

• Using the 'sums', we can calculate the area of any square in time complexity = O(1).

Note:

• Time complexity = O(m * n * min(m, n)), m is the number of rows, n is the number of cols.
• Space complexity = O(m * n), m is the number of rows, n is the number of cols.