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. You have a grid where two players start at the top-left corner and move to the bottom-right corner simultaneously, collecting cherries on their paths. Both players can only move right or down, and some cells contain thorns that block passage. The goal is to maximize the total cherries collected by both players without double-counting cherries if they land on the same cell. Which algorithmic approach guarantees finding the optimal solution for this problem?

easy

A. Greedy algorithm that always picks the next cell with the most cherries for each player independently.

B. Divide and conquer by splitting the grid into two halves and solving each half independently.

C. Dynamic programming that tracks both players' positions simultaneously and uses a 3D state to avoid double counting and invalid paths.

D. Simple BFS traversal from start to end for each player separately, then summing their maximum cherries.

Solution

1. Step 1: Understand the problem constraints

   Two players move simultaneously on the grid, collecting cherries without double counting and avoiding thorns. Both must take the same number of steps at any point.

2. Step 2: Identify the suitable algorithmic pattern

   Dynamic programming with a 3D state (step count and both players' row positions) tracks both players' positions simultaneously, ensuring valid states and avoiding double counting.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP with simultaneous states handles constraints correctly [OK]

Hint: Two simultaneous paths require joint DP state [OK]

Common Mistakes:

• Assuming independent paths and summing results
• Using greedy to pick local max cherries
• Splitting grid and solving halves independently

2. Given the following code for the Dungeon Game problem, what is the value of dp[0][0] returned by calculateMinimumHP when called with dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]?

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] = 1
        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]

easy

A. 7

B. 5

C. 3

D. 1

Solution

1. Step 1: Initialize dp boundaries

   dp[3][2] and dp[2][3] set to 1, others infinity.

2. Step 2: Compute dp bottom-up

   Calculate dp values from bottom-right to top-left considering dungeon values and ensuring health ≥1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Known example output is 7 for this input [OK]

Hint: Trace dp from bottom-right to top-left [OK]

Common Mistakes:

• Off-by-one errors in dp indices
• Forgetting max(1, need)

3. Consider the following Python code for computing unique paths in a grid:

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

print(uniquePaths(3, 3))

What is the value of dp after the outer loop completes its second iteration (i=2)?

easy

A. [1, 3, 6]

B. [1, 2, 3]

C. [1, 3, 5]

D. [1, 4, 10]

Solution

1. Step 1: Initialize dp array

   Initially, dp = [1, 1, 1] for n=3.

2. Step 2: Trace iterations

   First outer iteration (i=1): - j=1: dp[1] = dp[1] + dp[0] = 1 + 1 = 2 - j=2: dp[2] = dp[2] + dp[1] = 1 + 2 = 3 After i=1, dp = [1, 2, 3] Second outer iteration (i=2): - j=1: dp[1] = dp[1] + dp[0] = 2 + 1 = 3 - j=2: dp[2] = dp[2] + dp[1] = 3 + 3 = 6 After i=2, dp = [1, 3, 6]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   dp array accumulates path counts correctly -> [1,3,6] [OK]

Hint: Track dp updates carefully per iteration [OK]

Common Mistakes:

• Off-by-one errors in loop indices
• Mis-updating dp[j] with wrong dp[j-1] value

4. The following code attempts to solve the Burst Balloons problem using bottom-up DP. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def maxCoins(nums):
    n = len(nums)
    dp = [[0] * (n + 2) for _ in range(n + 2)]
    nums = nums + [1, 1]
    for length in range(2, n + 2):
        for i in range(0, n + 2 - length):
            j = i + length
            for k in range(i + 1, j):
                coins = dp[i][k] + nums[i] * nums[k] * nums[j] + dp[k][j]
                if coins > dp[i][j]:
                    dp[i][j] = coins
    return dp[0][n + 1]

medium

A. Line 4: Adding virtual balloons at the end instead of both ends

B. Line 3: Initializing dp with size (n+2) x (n+2)

C. Line 7: Looping length from 2 to n+2

D. Line 10: Calculating coins using dp[i][k] + nums[i]*nums[k]*nums[j] + dp[k][j]

Solution

1. Step 1: Check virtual balloon addition

   The code adds [1,1] only at the end of nums, but the algorithm requires adding 1 at both the start and end to handle boundaries correctly.

2. Step 2: Consequences of missing virtual balloon at start

   Without the leading 1, dp indices and coin calculations become incorrect, causing index errors or wrong coin counts at boundaries.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Virtual balloons must be added at both ends [OK]

Hint: Always add virtual balloons at both ends to avoid boundary errors [OK]

Common Mistakes:

• Adding virtual balloons only at one end
• Incorrect dp table size
• Wrong loop boundaries

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