Maximal Square

▶

Steps

setup

Initialize DP array and variables

We initialize a DP array of length cols+1 with zeros to represent the largest square side lengths for the previous row. We also initialize max_side to 0 and prev to 0 to track the maximum square side and the previous diagonal DP value.

💡 This initialization sets up the data structures needed to iteratively compute the largest square side lengths row by row.

Line:

dp = [0] * (cols + 1)
max_side = 0
prev = 0

💡 The DP array length is one more than the number of columns to simplify indexing and boundary conditions.

fill_cells

Process row 0, columns 1 to 5

We process the first row (index 0) from column 1 to 5. For each cell, if the matrix cell is '1', we update dp[j] to 1 plus the minimum of dp[j], dp[j-1], and prev. Otherwise, dp[j] is set to 0. We update max_side accordingly.

💡 This step shows how the DP array updates for each cell in the first row, starting or resetting squares based on matrix values.

Line:

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

💡 DP updates reflect the formation or breaking of squares at each cell.

fill_cells

Process row 1, columns 1 to 5

We process the second row (index 1) from column 1 to 5. For each cell, if the matrix cell is '1', we update dp[j] to 1 plus the minimum of dp[j], dp[j-1], and prev. Otherwise, dp[j] is set to 0. We update max_side accordingly.

💡 DP updates continue for the next row, reusing previous dp values and tracking squares.

Line:

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

💡 Squares of side 1 continue or start anew depending on neighbors.

fill_cells

Process row 2, columns 1 to 5

We process the third row (index 2) from column 1 to 5. For each cell, if the matrix cell is '1', we update dp[j] to 1 plus the minimum of dp[j], dp[j-1], and prev. Otherwise, dp[j] is set to 0. We update max_side accordingly.

💡 DP values increase to 2 where larger squares form, showing growth of squares.

Line:

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

💡 Squares grow by combining neighbors' dp values.

fill_cells

Process row 3, columns 1 to 5

We process the last row (index 3) from column 1 to 5. For each cell, if the matrix cell is '1', we update dp[j] to 1 plus the minimum of dp[j], dp[j-1], and prev. Otherwise, dp[j] is set to 0. We update max_side accordingly.

💡 DP updates continue, with zeros resetting dp[j] and breaking squares.

Line:

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

💡 Squares can restart after zeros, reflected in dp updates.

reconstruct

Return final answer

After processing all rows, we return max_side squared, which is 2*2=4, representing the area of the largest square of '1's.

💡 The maximum side length found during DP updates gives the largest square area.

Line:

return max_side * max_side

💡 The DP array and max_side tracking allow efficient computation of the largest square area.

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

📊

Maximal Square - Watch the Algorithm Execute, Step by Step

Watching each update to the DP array and how the maximum side length evolves helps you understand the dynamic programming state transitions and dependencies clearly.

Initializing dp array

i\w	0	1	2	3	4	5
i=0	0	0	0	0	0	0

DP initialized to 0

Item 4 - wt:0 val:0

i\w	0	1	2	3	4	5
i=0	0	1	0	1	0	0

dp[1] updated to 1

Item 9 - wt:1 val:1

i\w	0	1	2	3	4	5
i=0	0	1	0	1	0	0
i=1	0	1	0	1	1	1

dp[1] updated to 1

Item 14 - wt:1 val:2

i\w	0	1	2	3	4	5
i=0	0	1	0	1	0	0
i=1	0	1	0	1	1	1
i=2	0	1	2	2	2	2

dp[1] updated to 1

Item 19 - wt:0 val:0

i\w	0	1	2	3	4	5
i=0	0	1	0	1	0	0
i=1	0	1	0	1	1	1
i=2	0	1	2	2	2	2
i=3	0	1	0	0	1	0

dp[1] updated to 1

Initializing dp array

i\w	0	1	2	3	4	5
i=0	0	1	0	1	0	0
i=1	0	1	0	1	1	1
i=2	0	1	2	2	2	2
i=3	0	1	0	0	1	0

Final DP array

Key Takeaways

✓ The DP array stores the side length of the largest square ending at each column for the current row.

This insight is hard to see from code alone because the DP array is 1D and re-used, but watching the updates clarifies its meaning.

✓ Each DP cell depends on three neighbors: left, top, and top-left (prev), reflecting the square's growth conditions.

Visualizing these dependencies helps understand why the minimum of these neighbors determines the new DP value.

✓ Zeros in the matrix reset DP values to zero, breaking square continuity and forcing new squares to start.

Seeing how zeros reset dp[j] in the trace concretely shows how squares cannot span zero cells.

Practice

1. What is the time complexity of the bottom-up dynamic programming solution for the Burst Balloons problem with input size n, and why?

medium

A. O(n^3) because for each interval we try all possible last balloons to burst

B. O(n^3) due to three nested loops iterating over intervals and burst positions

C. O(2^n) because of the exponential number of burst orders

D. O(n^2) because we fill a 2D dp table of size n by n

Solution

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

   There are three nested loops: length of interval (up to n), start index i (up to n), and position k (up to n) inside the interval.

2. Step 2: Calculate complexity

   Each loop runs up to n times, so total time is O(n * n * n) = O(n^3). The dp table is size O(n^2), but filling it requires the third loop over k.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Three nested loops over n -> O(n^3) time complexity [OK]

Hint: Three nested loops over intervals and positions cause cubic time [OK]

Common Mistakes:

• Confusing dp table size with time complexity
• Ignoring the innermost loop over k
• Assuming exponential time for DP solution

2. What is the time complexity of the bottom-up dynamic programming solution for the minimum score triangulation of a polygon with n vertices?

medium

A. O(n^2)

B. O(n^4)

C. O(n^3)

D. O(n^3 * log n)

Solution

1. Step 1: Identify loops in the code

   There are three nested loops: length (up to n), i (up to n), and k (up to n), each iterating up to n times.

2. Step 2: Calculate total complexity

   Multiplying these loops gives O(n * n * n) = O(n^3). No extra log factor or higher power arises.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Three nested loops over n vertices -> cubic time [OK]

Hint: Count nested loops carefully to avoid underestimating complexity [OK]

Common Mistakes:

• Confusing recursion stack space
• Assuming only two nested loops
• Adding unnecessary log factors

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 Strange Printer problem after string compression, where m is the length of the compressed string?

medium

A. O(m^2)

B. O(m^3)

C. O(n^3) where n is original string length

D. O(m^2 * log m)

Solution

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

   There are three nested loops: length (1 to m), start index i (up to m), and partition index k (between i and j), each up to m.

2. Step 2: Calculate complexity

   Overall complexity is O(m * m * m) = O(m^3). Compression reduces n to m, so complexity depends on compressed length.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Three nested loops over compressed length m [OK]

Hint: Three nested loops over compressed string length cause cubic time [OK]

Common Mistakes:

• Confusing original length n with compressed length m
• Forgetting the inner loop over k

5. The following code attempts to compute the number of unique paths in an m x n grid using a space-optimized DP approach:

def uniquePaths(m, n):
    dp = [1] * n
    for i in range(1, m):
        for j in range(1, n):
            dp[j] = dp[j] + dp[j]
    return dp[-1]

What is the bug in this code?

medium

A. Line 3 should start loop from 0 instead of 1

B. Line 4 incorrectly doubles dp[j] instead of adding dp[j-1]

C. Line 5 should return dp[0] instead of dp[-1]

D. Line 2 initializes dp with wrong size

Solution

1. Step 1: Analyze inner loop update

   Line 4 updates dp[j] by adding dp[j] to itself, doubling the value instead of adding dp[j-1].

2. Step 2: Identify correct update

   The correct update is dp[j] += dp[j - 1] to accumulate paths from left and top cells.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Doubling dp[j] breaks path count logic -> bug at line 4 [OK]

Hint: Check dp update uses dp[j-1], not dp[j] twice [OK]

Common Mistakes:

• Using dp[j] + dp[j] instead of dp[j] + dp[j-1]
• Off-by-one errors in loops