Maximal Square

Problem Statement

In the given problem, you are provided with a two-dimensional binary matrix, which is only filled with the characters 0 and 1. Your task is to identify the largest square sub-matrix entirely composed of 1s and determine its area. The area is defined as the number of 1s in the square, which equates to the square of the side length of the largest square found in the matrix. We will leverage the given matrix dimensions and values to solve this problem efficiently within the constraints.

Examples

Example 1

Input:

matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]

Output:

4

Example 2

Input:

matrix = [["0","1"],["1","0"]]

Output:

1

Example 3

Input:

matrix = [["0"]]

Output:

0

Constraints

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] is '0' or '1'.

Approach and Intuition

The premise behind solving this problem is to employ dynamic programming to reduce redundant calculations:

1. Initial Setup:

   • To solve this, we first create an auxiliary matrix dp of the same dimensions as the original matrix. Each cell (i, j) in dp will store the size of the largest square sub-matrix whose lower right corner is at (i, j).

2. Fill the dp Matrix:

   • For every cell in dp, if the corresponding cell in the matrix is a 0, the value in dp should obviously be 0 because you cannot start a square of 1s at that cell.
   • If it is a 1, you can potentially extend the squares ending at (i-1, j), (i, j-1), and (i-1, j-1). Hence, dp[i][j] would be the minimum of these three cells plus one. This represents the new square formed by adding the (i, j) cell to those squares.

3. Edge Cases:

   • If the matrix dimension is 1x1, check directly and return 0 or 1 which concurs with the absence or presence of a 1.
   • For the first row and first column in dp, if the matrix has a 1 at these positions, that alone forms a square of side 1 sizing the area to 1.

4. Compute the Maximum:

   • After building the dp matrix, scan through it to find the maximum value which represents the side length of the largest square of 1s. Squaring this value gives the area of the largest square.

5. Optimize by Space:

   • Note that updating the dp array only requires knowledge of the previous row and the current row, so one could optimize the space complexity to be linear relative to the number of columns.

Examples:

• Example 1 Insights:
  • The largest square of 1s ends at position (2, 4) with side 2, hence the area is 2x2 = 4.
• Example 2 Insights:
  • The maximum side length of 1 only allows a minimal square area of 1.
• Example 3 Insights:
  • Only 0s present, so the resultant area is 0.

This dynamic programming approach efficiently computes the largest square area, adheres to the constraints, and systematically uses prior results to construct new values, culminating in substantial computational savings.

Solutions

class Solution {
public:
    int largestSquare(vector<vector<char>>& grid) {
        int numRows = grid.size();
        int numCols = numRows > 0 ? grid[0].size() : 0;
        vector<int> dynamicP(numCols + 1, 0);
        int largestLength = 0, previous = 0;
        for (int r = 1; r <= numRows; ++r) {
            for (int c = 1; c <= numCols; ++c) {
                int temp = dynamicP[c];
                if (grid[r - 1][c - 1] == '1') {
                    dynamicP[c] = min(min(dynamicP[c - 1], previous), dynamicP[c]) + 1;
                    largestLength = max(largestLength, dynamicP[c]);
                } else {
                    dynamicP[c] = 0;
                }
                previous = temp;
            }
        }
        return largestLength * largestLength;
    }
};