Integral image solution, 156ms. I know I know, it's slow, just want to throw it out here


  • 4
    C

    Just want to throw a solution using integral image. Clearly it's not as fast as DP solution, but it's fun

    class Solution {
    public:
        int maximalSquare(vector<vector<char>>& matrix) {
            int rows = matrix.size();
            if (rows == 0) return 0;
            int cols = matrix[0].size();
            if (cols == 0) return 0;
            int val;
            vector<vector<int> > image(rows+1, vector<int>(cols+1, 0)); // Integral image
            for (int r = 1; r <= rows; r++){
                for (int c = 1; c <= cols; c++){
                    val = (matrix[r-1][c-1] == '0' ? 0 : 1);
                    image[r][c] = val + image[r][c-1] + image[r-1][c] - image[r-1][c-1];
                }
            }
            if (image[rows][cols] == 0) return 0;
            int maxSize = 1;
            for (int r = 0; r <= rows; r++){
                for (int c = 0; c <= cols; c++){
                    for (int s = min(rows-r, cols-c); s >= maxSize; s--){
                        if (image[r+s][c+s] + image[r][c] - image[r][c+s] - image[r+s][c] == s * s) {
                            maxSize = s;
                            break;
                        }
                    }
                }
            }
            return maxSize * maxSize;
        }
    };

  • 2
    D

    Your idea is good but the code needs optimization.

    After generating the summed area table, we can scan the table row by row, checking if there is any square satisfying the square area condition. Once we found one, we can increase the maxSize by 1 and check next row. The optimized version has running time of 12 ms.

    class Solution {
    public:
        int maximalSquare(vector<vector<char>>& matrix) {
            int rows = matrix.size();
            if (rows == 0) return 0;
            int cols = matrix[0].size();
            if (cols == 0) return 0;
            int val;
            vector < vector<int> > image(rows+1, vector <int> (cols+1, 0)); // Integral image
            for (int r = 1; r <= rows; r++) {
                for (int c = 1; c <= cols; c++) {
                    val = (matrix[r-1][c-1] == '0' ? 0 : 1);
                    image[r][c] = val + image[r][c-1] + image[r-1][c] - image[r-1][c-1];
                }
            }
            if (image[rows][cols] == 0) return 0;
            int maxSize = 1;
            for (int r = 2; r <= rows; r++){
                int next = maxSize + 1;
                int area = next*next; 
                for (int c = next; c <= cols; c++){
                    if (image[r][c] + image[r-next][c-next] - image[r][c-next] - image[r-next][c] == area) {
                        maxSize = next;
                        break;
                    }
                }
            }
            return maxSize * maxSize;
        }
    };
    

    And the Python version:

    class Solution(object):
        def maximalSquare(self, matrix):
            """
            :type matrix: List[List[str]]
            :rtype: int
            """
            rows, max_size = len(matrix), 0
            if rows > 0:
                cols = len(matrix[0])
                '''
                Use summed area table to calculate maximal square
                The value at image[x][y] is the sum of all elements above and to the left of (x-1, y-1) in matrix (converted to int)
                The area of rectangle ABDC (top left -> top right -> bottom right --> bottom left), as below
                    A   B
                    C   D
                is image[D] + image[A] - image[B] - image[C]
                We can scan the summed area table, check if the area of a squre is exactly the square of the length of edge
                '''
                image = [[0] * (cols+1) for _ in range(rows+1)]
                # generate summed-area table
                for x in xrange(rows):
                    for y in xrange(cols):
                        image[x+1][y+1] = image[x+1][y] + image[x][y+1] - image[x][y] + (1 if matrix[x][y] == '1' else 0)
    
                if image[rows][cols] > 0:
                    max_size = 1
                    for x in xrange(2, rows+1):
                        # next_size: next possible maximal size of square
                        next_size = max_size + 1
                        area = next_size*next_size
                        for y in xrange(next_size, cols+1):
                            # check the area of squares
                            if (image[x][y] + image[x-next_size][y-next_size] - image[x][y-next_size] - image[x-next_size][y] == area):
                                max_size = next_size
                                break;
    
            return max_size*max_size
    

Log in to reply
 

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