Maximal Square

🎯

Maximal Square

mediumDPFacebookAmazonApple

Imagine you are designing a photo editing app that needs to detect the largest square area of a certain color in an image grid to apply a filter efficiently.

💡 This problem is a classic example of dynamic programming on grids. Beginners often struggle because it requires understanding how to build solutions for bigger squares from smaller ones, which is not obvious without a systematic approach.

📋

Problem Statement

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

1 ≤ number of rows ≤ 3001 ≤ number of columns ≤ 300matrix[i][j] is '0' or '1'

💡

Example

Input"[[\"1\",\"0\",\"1\",\"0\",\"0\"],[\"1\",\"0\",\"1\",\"1\",\"1\"],[\"1\",\"1\",\"1\",\"1\",\"1\"],[\"1\",\"0\",\"0\",\"1\",\"0\"]]"

Output4

The largest square has side length 2, so area = 2*2 = 4.

• Empty matrix → output 0
• Matrix with all zeros → output 0
• Matrix with all ones → output n*m (full matrix area)
• Single row or single column matrix → output 1 if any '1' present, else 0

🔁

Why DP?

Why greedy fails:

A greedy approach might try to expand squares from each cell independently without considering smaller squares inside, leading to incorrect results. For example, a cell with '1' surrounded by zeros cannot form a larger square, but greedy might falsely assume it can.

DP state:

dp[i][j] represents the side length of the largest square whose bottom-right corner is at cell (i, j).

Recurrence:dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 if matrix[i][j] == '1' else 0

If the current cell is '1', the largest square ending here is 1 plus the smallest of the largest squares ending above, left, and diagonally up-left.

⚠️

Common Mistakes

Not handling first row and first column as base cases

Index out of bounds or incorrect dp values

✅ Explicitly set dp[i][0] and dp[0][j] to 1 if matrix cell is '1'

Using dp[i-1][j-1] without checking boundaries

Runtime error or wrong answer

✅ Add boundary checks or initialize dp with extra padding

Updating dp array in wrong order in space optimized approach

Incorrect dp values due to overwritten dependencies

✅ Iterate dp array backwards to preserve needed previous values

Confusing dp state meaning leading to wrong recurrence

Incorrect maximum square size computed

✅ Remember dp[i][j] means largest square ending at (i,j), not starting

🧠

Brute Force (Check All Squares)

💡 This approach exists to understand the problem from first principles by checking every possible square, which helps grasp the problem's nature before optimizing.

Intuition

Try every cell as the top-left corner of a square and expand the square size until a zero is encountered or boundary is reached.

Algorithm

1. Iterate over each cell in the matrix.
2. For each cell with '1', try to form squares of increasing size.
3. Check if all cells in the current square are '1'.
4. Update the maximum square side length found.

💡 The nested loops and repeated checks make this approach inefficient and hard to optimize without DP.

Recurrence:N/A for brute force

</>

Code

def maximalSquare(matrix):
    if not matrix or not matrix[0]:
        return 0
    max_side = 0
    rows, cols = len(matrix), len(matrix[0])
    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == '1':
                side = 1
                flag = True
                while i + side < rows and j + side < cols and flag:
                    for k in range(i, i + side + 1):
                        if matrix[k][j + side] == '0':
                            flag = False
                            break
                    for l in range(j, j + side + 1):
                        if matrix[i + side][l] == '0':
                            flag = False
                            break
                    if flag:
                        side += 1
                max_side = max(max_side, side)
    return max_side * max_side

# Example usage:
if __name__ == '__main__':
    matrix = [
        ["1","0","1","0","0"],
        ["1","0","1","1","1"],
        ["1","1","1","1","1"],
        ["1","0","0","1","0"]
    ]
    print(maximalSquare(matrix))  # Output: 4

Line Notes

if not matrix or not matrix[0]:Check for empty input to avoid errors

for i in range(rows):Iterate over each row as potential square start

if matrix[i][j] == '1':Only start expanding squares from cells with '1'

while i + side < rows and j + side < cols and flag:Expand square size while within bounds and no zero found

public class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int maxSide = 0;
        int rows = matrix.length, cols = matrix[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    int side = 1;
                    boolean flag = true;
                    while (i + side < rows && j + side < cols && flag) {
                        for (int k = i; k <= i + side; k++) {
                            if (matrix[k][j + side] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        for (int l = j; l <= j + side; l++) {
                            if (matrix[i + side][l] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        if (flag) side++;
                    }
                    maxSide = Math.max(maxSide, side);
                }
            }
        }
        return maxSide * maxSide;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        char[][] matrix = {
            {'1','0','1','0','0'},
            {'1','0','1','1','1'},
            {'1','1','1','1','1'},
            {'1','0','0','1','0'}
        };
        System.out.println(sol.maximalSquare(matrix)); // Output: 4
    }
}

Line Notes

if (matrix == null || matrix.length == 0 || matrix[0].length == 0)Guard clause for empty input

for (int i = 0; i < rows; i++)Outer loop over rows

if (matrix[i][j] == '1')Start expanding squares only from '1' cells

while (i + side < rows && j + side < cols && flag)Expand square size while valid and no zero found

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int maxSide = 0;
        int rows = matrix.size(), cols = matrix[0].size();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    int side = 1;
                    bool flag = true;
                    while (i + side < rows && j + side < cols && flag) {
                        for (int k = i; k <= i + side; k++) {
                            if (matrix[k][j + side] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        for (int l = j; l <= j + side; l++) {
                            if (matrix[i + side][l] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        if (flag) side++;
                    }
                    maxSide = max(maxSide, side);
                }
            }
        }
        return maxSide * maxSide;
    }
};

int main() {
    Solution sol;
    vector<vector<char>> matrix = {
        {'1','0','1','0','0'},
        {'1','0','1','1','1'},
        {'1','1','1','1','1'},
        {'1','0','0','1','0'}
    };
    cout << sol.maximalSquare(matrix) << endl; // Output: 4
    return 0;
}

Line Notes

if (matrix.empty() || matrix[0].empty())Check for empty matrix to avoid errors

for (int i = 0; i < rows; i++)Iterate over rows as square start points

if (matrix[i][j] == '1')Only consider cells with '1' to start squares

while (i + side < rows && j + side < cols && flag)Expand square size while valid and no zero found

var maximalSquare = function(matrix) {
    if (!matrix || matrix.length === 0 || matrix[0].length === 0) return 0;
    let maxSide = 0;
    let rows = matrix.length, cols = matrix[0].length;
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (matrix[i][j] === '1') {
                let side = 1;
                let flag = true;
                while (i + side < rows && j + side < cols && flag) {
                    for (let k = i; k <= i + side; k++) {
                        if (matrix[k][j + side] === '0') {
                            flag = false;
                            break;
                        }
                    }
                    for (let l = j; l <= j + side; l++) {
                        if (matrix[i + side][l] === '0') {
                            flag = false;
                            break;
                        }
                    }
                    if (flag) side++;
                }
                maxSide = Math.max(maxSide, side);
            }
        }
    }
    return maxSide * maxSide;
};

// Example usage:
const matrix = [
    ['1','0','1','0','0'],
    ['1','0','1','1','1'],
    ['1','1','1','1','1'],
    ['1','0','0','1','0']
];
console.log(maximalSquare(matrix)); // Output: 4

Line Notes

if (!matrix || matrix.length === 0 || matrix[0].length === 0)Guard clause for empty input

for (let i = 0; i < rows; i++)Loop over rows to start squares

if (matrix[i][j] === '1')Only expand squares from '1' cells

while (i + side < rows && j + side < cols && flag)Expand square size while valid and no zero found

⏱

Complexity

TimeO(m^3) where m = max(rows, cols)

SpaceO(1) additional space

For each cell, we try to expand squares up to the matrix size, checking all cells inside the square each time.

💡 For a 300x300 matrix, this means up to 27 million operations, which is too slow for interviews.

Interview Verdict: TLE / Use only to introduce problem

This approach is too slow but helps understand the problem before moving to DP.

🧠

Top-Down DP with Memoization

💡 This approach improves brute force by caching results of subproblems to avoid repeated work, introducing the core DP concept.

Intuition

Define a recursive function that returns the largest square side length ending at (i,j), using memoization to store results.

Algorithm

1. Define a recursive function that returns largest square side ending at (i,j).
2. If cell is '0', return 0.
3. Otherwise, recursively compute left, top, and top-left neighbors.
4. Return 1 plus minimum of these neighbors.
5. Use memoization to store and reuse results.
6. Track maximum side length during recursion.

💡 Memoization avoids recomputing the same states, drastically improving efficiency over brute force.

Recurrence:dp(i,j) = 0 if matrix[i][j] == '0' else 1 + min(dp(i-1,j), dp(i,j-1), dp(i-1,j-1))

</>

Code

def maximalSquare(matrix):
    if not matrix or not matrix[0]:
        return 0
    rows, cols = len(matrix), len(matrix[0])
    memo = [[-1]*cols for _ in range(rows)]
    max_side = 0
    def dfs(i, j):
        nonlocal max_side
        if i < 0 or j < 0:
            return 0
        if memo[i][j] != -1:
            return memo[i][j]
        if matrix[i][j] == '0':
            memo[i][j] = 0
        else:
            left = dfs(i, j-1)
            up = dfs(i-1, j)
            diag = dfs(i-1, j-1)
            memo[i][j] = 1 + min(left, up, diag)
            max_side = max(max_side, memo[i][j])
        return memo[i][j]
    for i in range(rows):
        for j in range(cols):
            dfs(i, j)
    return max_side * max_side

# Example usage:
if __name__ == '__main__':
    matrix = [
        ["1","0","1","0","0"],
        ["1","0","1","1","1"],
        ["1","1","1","1","1"],
        ["1","0","0","1","0"]
    ]
    print(maximalSquare(matrix))  # Output: 4

Line Notes

memo = [[-1]*cols for _ in range(rows)]Initialize memo table with -1 to indicate uncomputed states

def dfs(i, j):Recursive function to compute largest square ending at (i,j)

if memo[i][j] != -1:Return cached result to avoid recomputation

memo[i][j] = 1 + min(left, up, diag)DP recurrence to build solution from neighbors

public class Solution {
    private int maxSide = 0;
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int rows = matrix.length, cols = matrix[0].length;
        int[][] memo = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                memo[i][j] = -1;
            }
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                dfs(matrix, memo, i, j);
            }
        }
        return maxSide * maxSide;
    }
    private int dfs(char[][] matrix, int[][] memo, int i, int j) {
        if (i < 0 || j < 0) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        if (matrix[i][j] == '0') {
            memo[i][j] = 0;
        } else {
            int left = dfs(matrix, memo, i, j - 1);
            int up = dfs(matrix, memo, i - 1, j);
            int diag = dfs(matrix, memo, i - 1, j - 1);
            memo[i][j] = 1 + Math.min(left, Math.min(up, diag));
            maxSide = Math.max(maxSide, memo[i][j]);
        }
        return memo[i][j];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        char[][] matrix = {
            {'1','0','1','0','0'},
            {'1','0','1','1','1'},
            {'1','1','1','1','1'},
            {'1','0','0','1','0'}
        };
        System.out.println(sol.maximalSquare(matrix)); // Output: 4
    }
}

Line Notes

int[][] memo = new int[rows][cols];Memo table to store computed results

if (memo[i][j] != -1) return memo[i][j];Return cached result to avoid recomputation

memo[i][j] = 1 + Math.min(left, Math.min(up, diag));Apply DP recurrence relation

maxSide = Math.max(maxSide, memo[i][j]);Track maximum square side length found

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
    int maxSide = 0;
    int dfs(vector<vector<char>>& matrix, vector<vector<int>>& memo, int i, int j) {
        if (i < 0 || j < 0) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        if (matrix[i][j] == '0') {
            memo[i][j] = 0;
        } else {
            int left = dfs(matrix, memo, i, j - 1);
            int up = dfs(matrix, memo, i - 1, j);
            int diag = dfs(matrix, memo, i - 1, j - 1);
            memo[i][j] = 1 + min({left, up, diag});
            maxSide = max(maxSide, memo[i][j]);
        }
        return memo[i][j];
    }
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int rows = matrix.size(), cols = matrix[0].size();
        vector<vector<int>> memo(rows, vector<int>(cols, -1));
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                dfs(matrix, memo, i, j);
            }
        }
        return maxSide * maxSide;
    }
};

int main() {
    Solution sol;
    vector<vector<char>> matrix = {
        {'1','0','1','0','0'},
        {'1','0','1','1','1'},
        {'1','1','1','1','1'},
        {'1','0','0','1','0'}
    };
    cout << sol.maximalSquare(matrix) << endl; // Output: 4
    return 0;
}

Line Notes

vector<vector<int>> memo(rows, vector<int>(cols, -1));Initialize memo table with -1 for uncomputed states

if (memo[i][j] != -1) return memo[i][j];Return cached result to avoid recomputation

memo[i][j] = 1 + min({left, up, diag});DP recurrence to compute largest square side

maxSide = max(maxSide, memo[i][j]);Update maximum side length found

var maximalSquare = function(matrix) {
    if (!matrix || matrix.length === 0 || matrix[0].length === 0) return 0;
    const rows = matrix.length, cols = matrix[0].length;
    const memo = Array.from({length: rows}, () => Array(cols).fill(-1));
    let maxSide = 0;
    function dfs(i, j) {
        if (i < 0 || j < 0) return 0;
        if (memo[i][j] !== -1) return memo[i][j];
        if (matrix[i][j] === '0') {
            memo[i][j] = 0;
        } else {
            const left = dfs(i, j - 1);
            const up = dfs(i - 1, j);
            const diag = dfs(i - 1, j - 1);
            memo[i][j] = 1 + Math.min(left, up, diag);
            maxSide = Math.max(maxSide, memo[i][j]);
        }
        return memo[i][j];
    }
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            dfs(i, j);
        }
    }
    return maxSide * maxSide;
};

// Example usage:
const matrix = [
    ['1','0','1','0','0'],
    ['1','0','1','1','1'],
    ['1','1','1','1','1'],
    ['1','0','0','1','0']
];
console.log(maximalSquare(matrix)); // Output: 4

Line Notes

const memo = Array.from({length: rows}, () => Array(cols).fill(-1));Initialize memo table with -1 for uncomputed states

if (memo[i][j] !== -1) return memo[i][j];Return cached result to avoid recomputation

memo[i][j] = 1 + Math.min(left, up, diag);Apply DP recurrence relation

maxSide = Math.max(maxSide, memo[i][j]);Track maximum square side length found

⏱

Complexity

TimeO(m*n) where m = rows and n = cols

SpaceO(m*n) for memoization

Each cell is computed once and cached, avoiding repeated work of brute force.

💡 For a 300x300 matrix, this reduces operations to about 90,000, which is efficient enough.

Interview Verdict: Accepted / Good for understanding recursion + memoization

This approach is efficient and introduces DP concepts clearly, but iterative DP is usually preferred.

🧠

Bottom-Up DP (Tabulation)

💡 This is the optimal and most common approach, building the solution iteratively and avoiding recursion overhead.

Intuition

Use a dp table where dp[i][j] stores the largest square side ending at (i,j), computed from neighbors above, left, and diagonal.

Algorithm

1. Initialize a dp matrix with same dimensions as input.
2. Copy first row and first column from input as base cases.
3. For each cell from (1,1), if matrix[i][j] == '1', set dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).
4. Track the maximum dp[i][j] value during iteration.
5. Return the square of the maximum side length found.

💡 This approach uses a clear bottom-up pattern, making it easier to debug and understand than recursion.

Recurrence:dp[i][j] = 0 if matrix[i][j] == '0' else 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

</>

Code

def maximalSquare(matrix):
    if not matrix or not matrix[0]:
        return 0
    rows, cols = len(matrix), len(matrix[0])
    dp = [[0]*cols for _ in range(rows)]
    max_side = 0
    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == '1':
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
                max_side = max(max_side, dp[i][j])
    return max_side * max_side

# Example usage:
if __name__ == '__main__':
    matrix = [
        ["1","0","1","0","0"],
        ["1","0","1","1","1"],
        ["1","1","1","1","1"],
        ["1","0","0","1","0"]
    ]
    print(maximalSquare(matrix))  # Output: 4

Line Notes

dp = [[0]*cols for _ in range(rows)]Initialize dp table with zeros

if i == 0 or j == 0:Base case: first row or column can only form squares of size 1 if '1'

dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])DP recurrence to build largest square ending at (i,j)

max_side = max(max_side, dp[i][j])Track maximum square side length found

public class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int rows = matrix.length, cols = matrix[0].length;
        int[][] dp = new int[rows][cols];
        int maxSide = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = 1 + Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]));
                    }
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
        return maxSide * maxSide;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        char[][] matrix = {
            {'1','0','1','0','0'},
            {'1','0','1','1','1'},
            {'1','1','1','1','1'},
            {'1','0','0','1','0'}
        };
        System.out.println(sol.maximalSquare(matrix)); // Output: 4
    }
}

Line Notes

int[][] dp = new int[rows][cols];Create dp table to store largest square sides

if (i == 0 || j == 0)Handle first row and column base cases

dp[i][j] = 1 + Math.min(...)Apply DP recurrence relation

maxSide = Math.max(maxSide, dp[i][j]);Update maximum square side length

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int rows = matrix.size(), cols = matrix[0].size();
        vector<vector<int>> dp(rows, vector<int>(cols, 0));
        int maxSide = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
                    }
                    maxSide = max(maxSide, dp[i][j]);
                }
            }
        }
        return maxSide * maxSide;
    }
};

int main() {
    Solution sol;
    vector<vector<char>> matrix = {
        {'1','0','1','0','0'},
        {'1','0','1','1','1'},
        {'1','1','1','1','1'},
        {'1','0','0','1','0'}
    };
    cout << sol.maximalSquare(matrix) << endl; // Output: 4
    return 0;
}

Line Notes

vector<vector<int>> dp(rows, vector<int>(cols, 0));Initialize dp table with zeros

if (i == 0 || j == 0)Base case for first row and column

dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});DP recurrence to compute largest square side

maxSide = max(maxSide, dp[i][j]);Track maximum square side length found

var maximalSquare = function(matrix) {
    if (!matrix || matrix.length === 0 || matrix[0].length === 0) return 0;
    const rows = matrix.length, cols = matrix[0].length;
    const dp = Array.from({length: rows}, () => Array(cols).fill(0));
    let maxSide = 0;
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (matrix[i][j] === '1') {
                if (i === 0 || j === 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = 1 + Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
                }
                maxSide = Math.max(maxSide, dp[i][j]);
            }
        }
    }
    return maxSide * maxSide;
};

// Example usage:
const matrix = [
    ['1','0','1','0','0'],
    ['1','0','1','1','1'],
    ['1','1','1','1','1'],
    ['1','0','0','1','0']
];
console.log(maximalSquare(matrix)); // Output: 4

Line Notes

const dp = Array.from({length: rows}, () => Array(cols).fill(0));Initialize dp table with zeros

if (i === 0 || j === 0)Handle base cases for first row and column

dp[i][j] = 1 + Math.min(...)Apply DP recurrence relation

maxSide = Math.max(maxSide, dp[i][j]);Update maximum square side length

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

Each cell is computed once using previously computed neighbors.

💡 For a 300x300 matrix, this is efficient and runs comfortably within time limits.

Interview Verdict: Accepted / Optimal iterative DP

This is the preferred approach in interviews due to clarity and efficiency.

🧠

Space Optimized Bottom-Up DP

💡 This approach reduces space usage from O(m*n) to O(n) by using a single array and careful iteration order.

Intuition

Since dp[i][j] depends only on dp[i-1][j], dp[i][j-1], and dp[i-1][j-1], we can use one-dimensional dp and a variable to track the diagonal value.

Algorithm

1. Initialize a 1D dp array with zeros, length equal to number of columns + 1.
2. Iterate over each row of the matrix.
3. For each cell, store dp[j] (previous row) and dp[j-1] (current row) values.
4. Update dp[j] using the minimum of dp[j], dp[j-1], and a variable holding the previous diagonal value.
5. Track maximum square side length during iteration.

💡 The key is to update dp in reverse order to avoid overwriting values needed for computation.

Recurrence:dp[j] = 0 if matrix[i][j-1] == '0' else 1 + min(dp[j], dp[j-1], prev)

</>

Code

def maximalSquare(matrix):
    if not matrix or not matrix[0]:
        return 0
    rows, cols = len(matrix), len(matrix[0])
    dp = [0] * (cols + 1)
    max_side = 0
    prev = 0
    for i in range(rows):
        for j in range(1, cols + 1):
            temp = dp[j]
            if matrix[i][j-1] == '1':
                dp[j] = 1 + min(dp[j], dp[j-1], prev)
                max_side = max(max_side, dp[j])
            else:
                dp[j] = 0
            prev = temp
    return max_side * max_side

# Example usage:
if __name__ == '__main__':
    matrix = [
        ["1","0","1","0","0"],
        ["1","0","1","1","1"],
        ["1","1","1","1","1"],
        ["1","0","0","1","0"]
    ]
    print(maximalSquare(matrix))  # Output: 4

Line Notes

dp = [0] * (cols + 1)Initialize 1D dp array with extra space for easier indexing

prev = 0Stores dp[j-1] from previous iteration (diagonal value)

temp = dp[j]Temporarily store current dp[j] before update

dp[j] = 1 + min(dp[j], dp[j-1], prev)Update dp[j] using previous row, left, and diagonal values

public class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int rows = matrix.length, cols = matrix[0].length;
        int[] dp = new int[cols + 1];
        int maxSide = 0, prev = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 1; j <= cols; j++) {
                int temp = dp[j];
                if (matrix[i][j - 1] == '1') {
                    dp[j] = 1 + Math.min(dp[j], Math.min(dp[j - 1], prev));
                    maxSide = Math.max(maxSide, dp[j]);
                } else {
                    dp[j] = 0;
                }
                prev = temp;
            }
        }
        return maxSide * maxSide;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        char[][] matrix = {
            {'1','0','1','0','0'},
            {'1','0','1','1','1'},
            {'1','1','1','1','1'},
            {'1','0','0','1','0'}
        };
        System.out.println(sol.maximalSquare(matrix)); // Output: 4
    }
}

Line Notes

int[] dp = new int[cols + 1];1D dp array to save space

int prev = 0;Stores dp[j-1] from previous iteration (diagonal)

int temp = dp[j];Temporarily hold dp[j] before update

dp[j] = 1 + Math.min(...)Update dp[j] using previous row, left, and diagonal values

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int rows = matrix.size(), cols = matrix[0].size();
        vector<int> dp(cols + 1, 0);
        int maxSide = 0, prev = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 1; j <= cols; j++) {
                int temp = dp[j];
                if (matrix[i][j - 1] == '1') {
                    dp[j] = 1 + min({dp[j], dp[j - 1], prev});
                    maxSide = max(maxSide, dp[j]);
                } else {
                    dp[j] = 0;
                }
                prev = temp;
            }
        }
        return maxSide * maxSide;
    }
};

int main() {
    Solution sol;
    vector<vector<char>> matrix = {
        {'1','0','1','0','0'},
        {'1','0','1','1','1'},
        {'1','1','1','1','1'},
        {'1','0','0','1','0'}
    };
    cout << sol.maximalSquare(matrix) << endl; // Output: 4
    return 0;
}

Line Notes

vector<int> dp(cols + 1, 0);Initialize 1D dp array with zeros

int prev = 0;Stores previous diagonal dp value

int temp = dp[j];Temporarily store dp[j] before update

dp[j] = 1 + min({dp[j], dp[j - 1], prev});Update dp[j] using previous states

var maximalSquare = function(matrix) {
    if (!matrix || matrix.length === 0 || matrix[0].length === 0) return 0;
    const rows = matrix.length, cols = matrix[0].length;
    const dp = new Array(cols + 1).fill(0);
    let maxSide = 0, prev = 0;
    for (let i = 0; i < rows; i++) {
        for (let j = 1; j <= cols; j++) {
            let temp = dp[j];
            if (matrix[i][j - 1] === '1') {
                dp[j] = 1 + Math.min(dp[j], dp[j - 1], prev);
                maxSide = Math.max(maxSide, dp[j]);
            } else {
                dp[j] = 0;
            }
            prev = temp;
        }
    }
    return maxSide * maxSide;
};

// Example usage:
const matrix = [
    ['1','0','1','0','0'],
    ['1','0','1','1','1'],
    ['1','1','1','1','1'],
    ['1','0','0','1','0']
];
console.log(maximalSquare(matrix)); // Output: 4

Line Notes

const dp = new Array(cols + 1).fill(0);Initialize 1D dp array with zeros

let prev = 0;Stores previous diagonal dp value

let temp = dp[j];Temporarily store dp[j] before update

dp[j] = 1 + Math.min(dp[j], dp[j - 1], prev);Update dp[j] using previous states

⏱

Complexity

TimeO(m*n)

SpaceO(n)

Uses a single dp array updated in place, reducing space from O(m*n) to O(n).

💡 This optimization is important for large inputs where memory is limited.

Interview Verdict: Accepted / Optimal space usage

This approach is ideal when memory constraints exist, demonstrating mastery of DP optimization.

📊

All Approaches - One-Glance Tradeoffs

💡 Bottom-up DP is the best to code in interviews due to clarity and efficiency; mention brute force only to show understanding.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(m^3)	O(1)	No	N/A	Mention only - never code
2. Top-Down DP with Memoization	O(m*n)	O(m*n)	Possible (deep recursion)	Yes	Good to explain DP concepts
3. Bottom-Up DP (Tabulation)	O(m*n)	O(m*n)	No	Yes	Preferred approach to code
4. Space Optimized Bottom-Up DP	O(m*n)	O(n)	No	Yes, with extra tracking	Mention if asked about optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify input and output format and constraints.Explain brute force approach to show understanding of problem.Introduce memoization to optimize repeated work.Present bottom-up DP as optimal solution.Mention space optimization if time permits.Code the bottom-up DP solution carefully.Test with edge cases and explain complexity.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Understanding of DP concepts, ability to optimize naive solutions, coding accuracy, and handling edge cases.

Common Follow-ups

• How to find the largest rectangle instead of square → use stack-based histogram approach.
• Can you optimize space usage? → yes, use 1D dp array.
• What if input is very large? → consider streaming or early pruning.
• How to reconstruct the largest square coordinates? → track max position during DP.

💡 These follow-ups test deeper understanding and ability to extend solutions under constraints.

🔍

Pattern Recognition

When to Use

1) Problem involves 2D grid with binary values; 2) Need to find largest square or rectangle; 3) Overlapping subproblems exist; 4) Optimal substructure present.

Signature Phrases

largest square containing only 1'smaximal square areasubmatrix with all ones

NOT This Pattern When

Problems asking for longest increasing path or non-square shapes are different patterns.

Similar Problems

Maximal Rectangle - extends square to rectanglesCount Square Submatrices with All Ones - counts all squares, not just largest

Practice

1. Consider the following code for minimum score triangulation of a polygon with vertex values [1, 3, 1, 4]. What is the final returned value?

easy

A. 7

B. 12

C. 10

D. 13

Solution

1. Step 1: Trace dp for length=3 (triangles)

   For i=0,j=2: dp[0][2] = 1*3*1=3; for i=1,j=3: dp[1][3] = 3*1*4=12

2. Step 2: Trace dp for length=4 (whole polygon)

   For i=0,j=3, k=1: cost=dp[0][1]+dp[1][3]+1*3*4=0+12+12=24; k=2: cost=dp[0][2]+dp[2][3]+1*1*4=3+0+4=7; dp[0][3]=7

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Minimal triangulation cost is 7, not 9 or higher [OK]

Hint: Check all k splits for minimal dp[i][j] cost [OK]

Common Mistakes:

• Off-by-one in loops
• Ignoring dp initialization
• Wrong triangle cost calculation

2. What is the time and space complexity of the space-optimized bottom-up dynamic programming solution for the Minimum Path Sum problem on an m x n grid?

medium

A. Time: O(m*n), Space: O(m*n)

B. Time: O(m*n), Space: O(m)

C. Time: O(2^(m+n)), Space: O(m+n)

D. Time: O(m*n), Space: O(n)

Solution

1. Step 1: Identify time complexity

   The algorithm iterates over each cell once, so time is O(m*n).

2. Step 2: Identify space complexity

   Space optimized DP uses a single 1D array of length n, so space is O(n), not O(m*n) or O(m).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Single dp array of size n updated row by row [OK]

Hint: Space optimized DP uses one row array, not full matrix [OK]

Common Mistakes:

• Assuming space is O(m*n) due to 2D dp
• Confusing recursion stack space with DP space
• Mistaking m for n in space complexity

3. What is the time complexity of the optimal bottom-up DP solution for the Paint House (K Colors) problem with n houses and k colors?

medium

A. O(n * k)

B. O(n^2 * k)

C. O(k^n)

D. O(n * k * k)

Solution

1. Step 1: Identify loops in the DP solution

   The outer loop runs over n houses, the inner loop over k colors, and inside that, a min over k colors excluding current color is computed, resulting in k iterations.

2. Step 2: Calculate total complexity

   Total operations = n (houses) * k (colors) * k (min over colors) = O(n * k * k). The recursion stack or auxiliary space does not add to time complexity here.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Nested loops over n, k, and k confirm O(n*k*k) [OK]

Hint: Remember min over k colors inside k-loop -> O(n*k*k) [OK]

Common Mistakes:

• Assuming O(n*k) ignoring inner min loop
• Confusing exponential brute force with DP
• Mistaking recursion stack space for time

4. What is the time complexity of the bottom-up DP solution for the Triangle minimum path sum problem with n rows, and why?

medium

A. O(n^2) because each element in the triangle is processed once

B. O(2^n) because of the exponential number of paths

C. O(n) because each row is processed once

D. O(n^3) because of nested loops over rows and columns

Solution

1. Step 1: Count total elements in triangle

   Triangle has 1 + 2 + ... + n = n(n+1)/2 elements, which is O(n^2).

2. Step 2: Analyze loops

   Outer loop runs n times, inner loop runs up to n times per iteration, total O(n^2) operations.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each element processed once in nested loops [OK]

Hint: Sum of rows is O(n^2), so time is O(n^2) [OK]

Common Mistakes:

• Confusing number of rows with total elements
• Assuming exponential complexity due to recursion
• Overestimating complexity due to nested loops

5. Suppose the Burst Balloons problem is modified so that each balloon can be burst multiple times (reused), and bursting a balloon again yields coins based on the current adjacent balloons. Which of the following changes to the bottom-up DP approach correctly adapts to this variant?

hard

A. Switch to a stateful DP that tracks the count of bursts per balloon and use memoization over these counts

B. Modify the DP to consider only the first burst of each balloon and ignore reuse

C. Use the same interval DP but allow k to be chosen multiple times per interval

D. Use a greedy approach bursting the balloon with the maximum product of neighbors repeatedly

Solution

1. Step 1: Understand reuse impact

   Allowing multiple bursts per balloon means the problem state must track how many times each balloon has been burst, increasing complexity.

2. Step 2: Adapt DP state

   Interval DP assuming each balloon bursts once no longer works. We need a DP or memoization that tracks burst counts per balloon to correctly compute coins.

3. Step 3: Evaluate options

   Switch to a stateful DP that tracks the count of bursts per balloon and use memoization over these counts correctly proposes a stateful DP with counts and memoization. Use the same interval DP but allow k to be chosen multiple times per interval incorrectly reuses interval DP without state changes. Modify the DP to consider only the first burst of each balloon and ignore reuse ignores reuse, and D is greedy and incorrect.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tracking burst counts is necessary for reuse variants [OK]

Hint: Reuse requires tracking burst counts, not just intervals [OK]

Common Mistakes:

• Trying naive interval DP for reuse
• Ignoring state explosion
• Using greedy for complex DP variants