algoadvance

Leetcode 221. Maximal Square

Problem Statement

The problem “Maximal Square” is described as follows:

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 Format: Is the matrix always non-empty?
   • Assumption: Yes, the matrix is always non-empty.
2. Matrix Dimensions: What are the constraints on the dimensions of the matrix (m and n)?
   • Assumption: 1 <= m, n <= 300
3. Matrix Values: Can the matrix contain any character other than ‘0’ and ‘1’?
   • Assumption: No, the matrix only contains ‘0’ and ‘1’.

Strategy

To solve this problem, we can use a dynamic programming approach. The main idea is to create a DP table where dp[i][j] represents the side length of the largest square whose bottom-right corner is at cell (i, j).

Here’s a step-by-step strategy:

1. Dynamic Programming Table: Create a 2D array dp of the same dimensions as the input matrix.
2. Initialization:
   • If matrix[i][j] == '1', initialize the first row and first column of dp table with the same values as the matrix, because they can only form a square of side 1 (if they are ‘1’).
3. DP Transition:
   • For each cell (i, j), if matrix[i][j] == '1', then calculate dp[i][j] as:
     • dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
   • This formula works because a cell (i, j) can only form a square if its top, left, and top-left neighbors also have the potential to contribute to a square.
4. Tracking Maximum Square: Keep track of the maximum side length found in the dp table.
5. Return Result: The area of the largest square will be the maximum side length squared.

Code

class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int maxSide = 0;

        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;
                    } else {
                        dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                    }
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
        return maxSide * maxSide;
    }
}

Time Complexity

• Time Complexity: (O(m \times n)), where (m) is the number of rows and (n) is the number of columns in the matrix. We are iterating through each cell once.
• Space Complexity: (O(m \times n)) for the DP table. However, we can optimize the space complexity to (O(n)) using only a single array to store the intermediate results.

This solution efficiently finds the largest square of ‘1’s in the given matrix using dynamic programming principles. If you have any further questions or need additional optimizations, feel free to ask!

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?