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 bottom-up DP code for the Triangle minimum path sum problem. Given the input triangle = [[2],[3,4],[6,5,7]], what is the value of dp after the first iteration of the outer loop (i = 1)?

easy

A. [8, 9, 7]

B. [9, 10, 7]

C. [11, 10, 7]

D. [7, 9, 7]

Solution

1. Step 1: Initialize dp with last row

   dp = [6, 5, 7]

2. Step 2: Compute dp for i=1 (row [3,4])

   For j=0: dp[0] = 3 + min(6,5) = 3 + 5 = 8 For j=1: dp[1] = 4 + min(5,7) = 4 + 5 = 9 Updated dp = [8, 9, 7]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   dp updated correctly for row 1 [OK]

Hint: dp[j] updated using min of dp[j], dp[j+1] from row below [OK]

Common Mistakes:

• Off-by-one error in indexing dp
• Not copying last row correctly
• Mixing up dp[j] and dp[j+1] in min calculation

2. Consider the following buggy code for the Dungeon Game problem. Which line contains the subtle bug that causes incorrect minimum health calculation?

from typing import List

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]
        dp[m][n - 1] = 0  # Bug here
        dp[m - 1][n] = 1

        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
                dp[i][j] = max(1, need)

        return dp[0][0]

medium

A. Line computing need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]

B. Line initializing dp[m - 1][n] to 1

C. Line initializing dp[m][n - 1] to 0 instead of 1

D. Line setting dp[i][j] = max(1, need)

Solution

1. Step 1: Check base case initialization

   The cell dp[m][n - 1] must be initialized to 1 to represent minimum health needed beyond the princess cell.

2. Step 2: Identify impact of wrong initialization

   Setting dp[m][n - 1] to 0 allows health to drop to zero, violating constraints and causing incorrect dp propagation.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Base case must be 1, not 0 [OK]

Hint: Base case dp[m][n-1] must be 1, not 0 [OK]

Common Mistakes:

• Incorrect base case initialization
• Forgetting max(1, need) clamp

3. The following code attempts to compute the minimum falling path sum using bottom-up DP. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def minFallingPathSum(matrix):
    n = len(matrix)
    dp = matrix[0][:]

    for i in range(1, n):
        for j in range(n):
            best = dp[j]
            if j > 0:
                best = min(best, dp[j-1])
            if j < n - 1:
                best = min(best, dp[j+1])
            dp[j] = matrix[i][j] + best

    return min(dp)

medium

A. Line 7: Updating dp[j] inside the inner loop without backup

B. Line 9: Checking if j > 0 before accessing dp[j-1]

C. Line 3: dp initialization with matrix[0][:]

D. Line 12: Returning min(dp) after the loops

Solution

1. Step 1: Understand dp update logic

   dp array holds minimum sums for previous row. Updating dp[j] in place overwrites values needed for neighbors in the same iteration.

2. Step 2: Identify the bug

   Updating dp[j] inside the inner loop without using a separate array causes premature overwriting, leading to incorrect neighbor comparisons.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using a separate new_dp array fixes the bug [OK]

Hint: Don't overwrite dp while still reading from it in same iteration [OK]

Common Mistakes:

• Updating dp in place without backup
• Ignoring boundary checks

4. The following code attempts to solve the Strange Printer problem using bottom-up DP. Which line contains a subtle bug that can cause incorrect results on inputs like "aba"?

medium

A. Line 18: dp[i][j] = dp[i][j - 1] + 1 assignment

B. Line 13: dp[i][i] = 1 initialization

C. Line 4: compressed.append(c) without checking for duplicates

D. Line 21: if s[k] == s[j] condition

Solution

1. Step 1: Identify compression step

   Line 4 appends every character without checking if it equals the last compressed character, so no compression occurs.

2. Step 2: Understand impact of missing compression

   Without compression, the DP runs on the full string length, causing inefficiency and possibly incorrect merges, especially on inputs like "aba" where compression reduces complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Compression step must skip duplicates to optimize DP [OK]

Hint: Compression must skip consecutive duplicates to avoid TLE and errors [OK]

Common Mistakes:

• Forgetting to compress string before DP

5. Suppose the problem is modified so that you can move right, down, or diagonally down-right, still avoiding obstacles. Which of the following changes to the space-optimized DP approach correctly accounts for the new diagonal move?

hard

A. Modify dp[j] += dp[j-1] to dp[j] += dp[j-1] + dp[j] without extra storage.

B. Use a 2D dp array where dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1], updating in row-major order.

C. Add dp[j-1] and dp[j] plus dp[j-1] from previous row, requiring a 2D dp array to track diagonal paths.

D. Keep 1D dp array but add dp[j-1] twice to account for diagonal moves.

Solution

1. Step 1: Understand diagonal dependency

   Diagonal move depends on dp[i-1][j-1], which cannot be tracked with only 1D dp array updated in-place.

2. Step 2: Correct approach

   Use 2D dp array to store counts for all cells, updating dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1], ensuring all dependencies are available.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Diagonal requires previous row and previous column info simultaneously [OK]

Hint: Diagonal moves require 2D dp to track previous row and column [OK]

Common Mistakes:

• Trying to reuse 1D dp without extra storage
• Double counting paths
• Ignoring diagonal dependency