Maximal Square medium

Problem Statement

Given an m x n binary matrix matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

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

Steps to Solve

The problem can be efficiently solved using dynamic programming. We'll create a DP table dp of the same dimensions as the input matrix. dp[i][j] will store the side length of the largest square whose bottom-right corner is at matrix[i][j].

1. Initialization: The first row and column of dp are initialized directly from the input matrix. If matrix[i][j] == '1', then dp[i][j] = 1; otherwise, dp[i][j] = 0.

2. Iteration: We iterate through the remaining cells of the dp table. For each cell dp[i][j], if matrix[i][j] == '1', then the size of the square ending at (i, j) is determined by the minimum of the squares ending at (i-1, j), (i, j-1), and (i-1, j-1), plus 1. This is because we can extend the square only as far as the smallest square to its top, left, and top-left.

3. Finding the Maximum: After filling the dp table, we iterate through it to find the maximum value, which represents the side length of the largest square. The area is then the square of this side length.

Explanation

The dynamic programming approach works because it builds up the solution incrementally. Each cell in the dp table depends only on the values of cells to its top, left, and top-left. This avoids redundant calculations and ensures an optimal solution is found. The key insight is that to extend a square, you must ensure that the cells above, to the left, and diagonally above and to the left all contain '1's. The minimum of these three determines how far you can extend the current square.

Code (C++)

#include <vector>
#include <algorithm>

using namespace std;

int maximalSquare(vector<vector<char>>& matrix) {
    int m = matrix.size();
    if (m == 0) return 0;
    int n = matrix[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    int maxSide = 0;

    // Initialize first row and column
    for (int i = 0; i < m; ++i) {
        if (matrix[i][0] == '1') {
            dp[i][0] = 1;
            maxSide = 1;
        }
    }
    for (int j = 0; j < n; ++j) {
        if (matrix[0][j] == '1') {
            dp[0][j] = 1;
            maxSide = 1;
        }
    }

    // Fill the DP table
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            if (matrix[i][j] == '1') {
                dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
                maxSide = max(maxSide, dp[i][j]);
            }
        }
    }

    return maxSide * maxSide;
}

Complexity

• Time Complexity: O(m*n), where 'm' and 'n' are the dimensions of the input matrix. We iterate through the matrix once to build the DP table and once to find the maximum.
• Space Complexity: O(m*n), due to the DP table we use. While we could potentially optimize space to O(n) by using only two rows of the DP table, this would add complexity to the code.