algoadvance

Leetcode 221. Maximal Square

Problem Statement

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

Clarifying Questions

  1. Input Size: What are the constraints on the dimensions of the matrix?
    • Typically, constraints would be: (1 \leq m, n \leq 300).
  2. Matrix Content: Is the matrix guaranteed to be binary?
    • Yes, each element in the matrix is either 0 or 1.
  3. Expected Output: Should the result be the area of the largest square?
    • Yes, the output should be the area of the largest square containing only 1's.

With these clarifications, let’s proceed to the strategy.

Strategy

  1. Dynamic Programming Table: We will use a 2D DP table dp where dp[i][j] represents the side length of the largest square whose bottom-right corner is the cell (i, j).

  2. Transition: For each cell (i, j) in the matrix:
    • If matrix[i][j] == '0', then dp[i][j] = 0 because it can’t be a part of any square of 1's.
    • If matrix[i][j] == '1' and it’s not on the first row or first column (where squares larger than 1x1 can’t exist), then: [ dp[i][j] = \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 ] This relation arises because we can form a larger square only if there are squares ending at (i-1, j), (i, j-1), and (i-1, j-1).

  3. Result: Track the maximum value in the DP table, say maxSide. The area will be (maxSide^2).

  4. Initialization: Initialize a DP table with all zeroes.

Time Complexity

Code

Here is the C++ solution for the problem:

#include <vector>
#include <algorithm>

using namespace std;

int maximalSquare(vector<vector<char>>& matrix) {
    if (matrix.empty() || matrix[0].empty()) return 0;
    int m = matrix.size();
    int n = matrix[0].size();
    
    // DP table initialized to 0
    vector<vector<int>> dp(m, vector<int>(n, 0));
    
    int maxSide = 0;

    // Fill the dp table
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j] == '1') {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1; // Edge case for first row and column
                } else {
                    dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
                }
                maxSide = max(maxSide, dp[i][j]);
            }
        }
    }

    // Area of the largest square
    return maxSide * maxSide;
}

This C++ code will find and return the area of the largest square containing only 1's in the given binary matrix.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI