Maximal Square

📋

Problem

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.

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'

Edge cases: Empty matrix → output 0Matrix with all zeros → output 0Matrix with all ones → output n*m (full matrix area)

</>

IDE

def maximalSquare(matrix: list[list[str]]) -> int:public int maximalSquare(char[][] matrix)int maximalSquare(vector<vector<char>>& matrix)function maximalSquare(matrix)

def maximalSquare(matrix):
    # Write your solution here
    pass

class Solution {
    public int maximalSquare(char[][] matrix) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int maximalSquare(vector<vector<char>>& matrix) {
    // Write your solution here
    return 0;
}

function maximalSquare(matrix) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning 0 for non-empty matrix with '1's due to missing dp updates or incorrect initialization.✅ Initialize max_side to 0 and update dp only when matrix[i][j] == '1'.

Wrong: 1Greedy approach picking first '1' only, ignoring larger squares.✅ Use dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 to find max square side.

Wrong: 9Off-by-one error causing dp to overcount squares in partial matrices.✅ Align dp indices with matrix indices carefully; use dp with extra row and column for base cases.

Wrong: TLEUsing brute force O(m^3) approach on large inputs.✅ Implement O(m*n) DP solution to avoid timeouts.

✓

Test Cases

Try testing your code on empty and minimal inputs to catch base case bugs.

Consider tricky cases that break greedy or indexing assumptions.

Focus on algorithmic complexity; brute force won't scale.

t1_01basic

Input{"matrix":[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]}

Expected4

⏱ Performance - must finish in 2000ms

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

💡 Consider dynamic programming to track largest square ending at each cell.

💡 Use dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 if matrix[i][j] == '1'.

💡 Return the max dp value squared as the area.

Why it failed: Incorrect output means dp recurrence or boundary conditions are wrong; ensure dp[i][j] updates only if matrix[i][j] == '1' and uses min of three neighbors plus one.

✓ Correctly computes largest square area using DP recurrence.

t1_02basic

Input{"matrix":[["0","1","1","1"],["1","1","1","1"],["0","1","1","1"]]}

Expected9

⏱ Performance - must finish in 2000ms

Largest square side length is 2 (area 4), formed in middle rows and columns.

💡 Check all cells for largest square ending there using DP.

💡 Remember to handle first row and column separately as base cases.

💡 Max side length is max dp value; square it for area.

Why it failed: Output less than 4 indicates failure to consider all neighbors or incorrect initialization of dp edges.

✓ DP correctly finds largest 2x2 square area.

t2_01edge

Input{"matrix":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty matrix has no squares, so area is 0.

💡 Check if matrix or matrix[0] is empty before processing.

💡 Return 0 immediately if no rows or columns.

💡 Avoid index errors by handling empty input upfront.

Why it failed: Code crashes or returns non-zero on empty input; add guard clause for empty matrix.

✓ Correctly returns 0 for empty matrix.

t2_02edge

Input{"matrix":[["0","0","0"],["0","0","0"]]}

Expected0

⏱ Performance - must finish in 2000ms

All zeros means no square of 1's, so area is 0.

💡 Check that dp updates only on '1' cells.

💡 If no '1' found, max side remains 0.

💡 Return 0 if max side is zero after processing.

Why it failed: Returns positive area despite no '1's; fix dp update condition to skip '0's.

✓ Correctly returns 0 when no '1's present.

t2_03edge

Input{"matrix":[["1","1","1"],["1","1","1"],["1","1","1"]]}

Expected9

⏱ Performance - must finish in 2000ms

All ones matrix forms a 3x3 square, area = 9.

💡 DP should accumulate increasing square sizes.

💡 Check that dp[i][j] correctly uses min of neighbors plus one.

💡 Max side should reach full matrix dimension if all ones.

Why it failed: Max side less than matrix dimension means dp min calculation or initialization is wrong.

✓ Correctly identifies full matrix as largest square.

t3_01corner

Input{"matrix":[["1","1","0","1"],["1","1","1","1"],["0","1","1","1"],["1","1","1","1"]]}

Expected9

⏱ Performance - must finish in 2000ms

Largest square side length 2, area 4; tests greedy approach failure.

💡 Greedy approach picking largest immediate '1' block fails here.

💡 Use DP to consider minimal neighbor squares for correct side length.

💡 Check dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.

Why it failed: Greedy approach overestimates square size; fix by using DP min of three neighbors plus one.

✓ DP correctly avoids greedy trap and finds max square.

t3_02corner

Input{"matrix":[["1","0","1","1"],["1","1","1","1"],["1","1","1","0"],["1","1","0","0"]]}

Expected4

⏱ Performance - must finish in 2000ms

Tests off-by-one errors in dp indexing; largest square side 2, area 4.

💡 Check dp indexing carefully to avoid off-by-one errors.

💡 Remember dp array often has extra row/column for base cases.

💡 Ensure dp[i][j] corresponds to matrix[i-1][j-1].

Why it failed: Off-by-one indexing causes incorrect dp values; fix dp indices to align with matrix.

✓ Correct indexing yields correct largest square area.

t3_03corner

Input{"matrix":[["1"],["1"],["1"],["1"]]}

Expected1

⏱ Performance - must finish in 2000ms

Single column matrix with multiple rows; largest square side 1, area 1.

💡 Handle single row or column matrices correctly.

💡 Largest square side is 1 if any '1' present.

💡 DP base cases must handle first row and column properly.

Why it failed: Fails to handle single column correctly; fix dp initialization for first row/column.

✓ Correctly returns 1 for single column with '1's.

t4_01performance

Input{"matrix":[["1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1"],["1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1"],["1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1"],["1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1"],["1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1"],["1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1"],["1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1"],["1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1"],["1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1"],["1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1","1"]]}

Expected100

⏱ Performance - must finish in 2000ms

Large 10x30 matrix with all ones; O(m*n) DP must complete within 2s.

💡 DP solution runs in O(m*n) time.

💡 Avoid brute force O(m^3) which will TLE.

💡 Use bottom-up DP with space optimization if needed.

Why it failed: Brute force or inefficient approach causes TLE; optimize to O(m*n) DP.

✓ Efficient DP completes within time limit.

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. Consider the following bottom-up DP code for the Strange Printer problem. What is the final returned value when the input string is "aba"?

easy

A. 3

B. 4

C. 1

D. 2

Solution

1. Step 1: Compress input string "aba"

   Compression does not change string since no consecutive duplicates: s = "aba", n=3.

2. Step 2: Trace dp table filling

   Base cases: dp[0][0]=1, dp[1][1]=1, dp[2][2]=1. For length=2: - dp[0][1]: dp[0][0]+1=2, s[0]!=s[1], so dp[0][1]=2 - dp[1][2]: dp[1][1]+1=2, s[1]!=s[2], so dp[1][2]=2 For length=3: - dp[0][2]: dp[0][1]+1=3 Check k=0: s[0]==s[2] ('a'=='a'), dp[0][0]+dp[1][1]=1+1=2 < 3, so dp[0][2]=2

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Output matches known minimal turns for "aba" [OK]

Hint: Check dp merging when s[k] == s[j] reduces turns [OK]

Common Mistakes:

• Forgetting to merge intervals when characters match

3. 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

4. What is the time complexity of the bottom-up dynamic programming solution for the Stone Game problem with n piles, and why?

medium

A. O(n^3) because of three nested loops over the piles

B. O(n^2) because the DP table of size nxn is filled once with constant work per cell

C. O(2^n) because all subsets of piles are considered

D. O(n) because only linear passes over the piles are needed

Solution

1. Step 1: Identify loops in bottom-up DP

   There are two nested loops: one for length from 2 to n, and one for start index i, total O(n^2) iterations.

2. Step 2: Constant work per dp[i][j]

   Each dp[i][j] is computed with a constant number of operations (max of two values), so total time is O(n^2).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP table size nxn filled once with O(1) work per cell [OK]

Hint: Two nested loops over intervals -> O(n^2) [OK]

Common Mistakes:

• Confusing recursion stack space with time
• Assuming triple nested loops cause O(n^3)

5. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the Unique Paths problem on an m x n grid?

medium

A. O(m^2 * n^2)

B. O(m + n)

C. O(m * n * min(m, n))

D. O(m * n)

Solution

1. Step 1: Identify loops in the code

   The solution uses two nested loops: outer loop runs m-1 times, inner loop runs n-1 times.

2. Step 2: Calculate total operations

   Total operations ≈ (m-1) * (n-1) -> O(m * n). No extra hidden loops or recursion stack.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Nested loops over m and n -> O(m*n) [OK]

Hint: Nested loops over m and n -> O(m*n) [OK]

Common Mistakes:

• Confusing with recursion exponential time
• Forgetting loops multiply complexity