221. Largest square ● &1277. Square submatrix with statistics all 1 ● ●

221. The largest square ●●

describe

In a ‘0’ and ‘1’ In the two-dimensional matrix , Found contains only ‘1’ The largest square of , And return its area .

Example

Input ：matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]
Output ：4

Answer key

1. Violence solution （ Overtime ）

To find the area of the largest square , First, you need to find the side length of the largest square , Then calculate the square of the maximum side length .

Violence is the simplest and most intuitive approach , The specific methods are as follows ：

• Traverse every element in the matrix , Every encounter 1, Then take this element as a square top left corner ;
• After determining the upper left corner of the square , Calculate the side length of the largest possible square according to the row and column in the upper left corner （ The range of the square cannot exceed the number of rows and columns of the matrix ）, Look for only 1 The largest square of ;
• Add a new row at the bottom and a new column at the right , Judge whether the newly added rows and columns satisfy that all elements are 1.

---

• Time complexity ：$O(mn\min (m,n{)}^2)$, among m and n Is the number of rows and columns of the matrix .
  – You need to traverse the entire matrix to find each 1, The time complexity of traversing the matrix is O(mn)O(mn).
  – For every possible square , Its side length does not exceed m and n Minimum of , You need to traverse each element in the square to determine whether it only contains 1, The time complexity of traversing a square is $O(\min (m,n{)}^2)$.
• Spatial complexity ：$O(1)$. The additional space complexity used is constant .

class Solution {
    
public:
    int maximalSquare(vector<vector<char>>& matrix) {
    
        int m = matrix.size();
        int n = matrix[0].size();
        int maxArea = 0;
        for(int i = 0; i < m; ++i){
    
            for(int j = 0; j < n; ++j){
    
                if(matrix[i][j] == '1'){
            	    // (i, j) Is the upper-left coordinate 
                    int minLen = n+m;				    //  Continuous on the column  1  The minimum length of 
                    for(int k = j; k < n; ++k){
    		    //  Traverse each column 
                        if(k - j + 1 > minLen) break;   //  The side length of the row where the current column is located is greater than the minimum length , Out of the loop 
                        int len = 0;				    //  Record the continuous  1  The number of 
                        for(int l = i; l < m; ++l){
     
                            if(l-i+1 > minLen) break;	//  The current column side length is greater than the minimum length , Out of the loop 
                            if(matrix[l][k] == '0') break;
                            ++len;  
                        }
                        maxArea = max(maxArea, min(len, k-j+1)*min(len, k-j+1));    //  After traversing a column , Update the current maximum area , Side length is  min( Column length , governor )
                        minLen = min(len, minLen);      //  Update minimum length 
                    }
                }
            }
        }
        return maxArea;
    }
};

2. Dynamic programming

1. dp[i][j] Express With matrix[i][j] by The lower right corner when , Contains only 1 The square of Maximum side length .
2. Initialize the first row and the first column ,‘1’ Is the side length setting 1, Otherwise 0;
3. matrix[i][j] == '0'： dp[i][j] = 0;
matrix[i][j] == '1'：dp[i][j] = min(min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1]) + 1;
4. From left to right , Traverse from top to bottom .

---

• Time complexity ：$O(mn)$, among m and n Is the number of rows and columns of the matrix . You need to traverse each element in the original matrix to calculate dp Value .
• Spatial complexity ：$O(mn)$, among m and n Is the number of rows and columns of the matrix . Create a matrix with the same size as the original matrix dp.
  Due to the dp(i,j) From above 、 Three adjacent positions on the left and upper left dp Values determine , Therefore, two one-dimensional arrays can be used for state transition , Space complexity is optimized to O(n).

class Solution {
    
public:
    int maximalSquare(vector<vector<char>>& matrix) {
    
        int m = matrix.size(), n = matrix[0].size(), maxLen = 0;
        vector<vector<int>> dp(m, vector<int>(n, 0));   
        //  Boundary condition treatment 
        for(int i = 0; i < m; ++i) if(matrix[i][0] == '1'){
    dp[i][0] = 1; maxLen = 1;}
        for(int j = 0; j < n; ++j) if(matrix[0][j] == '1'){
    dp[0][j] = 1; maxLen = 1;}
        for(int i = 1; i < m; ++i){
    
            for(int j = 1; j < n; ++j){
    
                if(matrix[i][j] == '1'){
    
                    dp[i][j] = min(min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1]) + 1;
                    maxLen = max(maxLen, dp[i][j]);
                }
            }
        }
        return maxLen * maxLen;
    }
};

1277. The statistics are all 1 Square submatrix of ●●

describe

To give you one m * n Matrix , The elements in the matrix are not 0 Namely 1, Please count and return all the data 1 Composed of Square Number of submatrixes .

Example

Input ：matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]
Output ：15
explain ：
Side length is 1 What's the square of 10 individual .
Side length is 2 What's the square of 4 individual .
Side length is 3 What's the square of 1 individual .
The total number of squares = 10 + 4 + 1 = 15.

Answer key

Dynamic programming

And 221. The largest square ●● similar , Add up the sum of squares for each calculation , With (i, j) It's in the lower right corner Number of squares Is the maximum side length dp[i][j], Pay attention to the treatment of boundary conditions ,(0,0) It can't be repeated .

class Solution {
    
public:
    int countSquares(vector<vector<int>>& matrix) {
    
        int m = matrix.size(), n = matrix[0].size(), sum = 0;
        vector<vector<int>> dp(m, vector<int>(n, 0));   
        for(int i = 0; i < m; ++i) if(matrix[i][0] == 1){
    dp[i][0] = 1; ++sum;}
        for(int j = 1; j < n; ++j) if(matrix[0][j] == 1){
    dp[0][j] = 1; ++sum;}
        for(int i = 1; i < m; ++i){
    
            for(int j = 1; j < n; ++j){
    
                if(matrix[i][j] == 1){
    
                    dp[i][j] = min(min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1]) + 1;
                    sum += dp[i][j];
                }
            }
        }
        return sum;
    }
};