Minimum Path Sum

▶

Steps

setup

Initialize dp array size

We determine the number of rows (m) and columns (n) in the grid and create a dp array of length n initialized with zeros.

💡 Knowing the grid dimensions and preparing dp storage is the foundation for the bottom-up computation.

Line:

m, n = len(grid), len(grid[0])
dp = [0]*n

💡 The dp array length matches the number of columns, enabling row-wise updates.

setup

Set dp[0] to grid[0][0]

Initialize the first element of dp with the top-left grid value, as the path starts here.

💡 This sets the base case for the path sum at the starting cell.

Line:

dp[0] = grid[0][0]

💡 The minimum path sum to the first cell is simply its own value.

fill_row

Fill dp for first row cumulatively (j=1)

Update dp[1] by adding grid[0][1] to dp[0], accumulating the path sum moving right.

💡 Filling the first row dp values shows how the path sum accumulates when moving only right.

Line:

for j in range(1, n):
    dp[j] = dp[j-1] + grid[0][j]

💡 The minimum path sum to cell (0,1) is the sum of the path to (0,0) plus the current cell value.

fill_row

Fill dp for first row cumulatively (j=2)

Update dp[2] by adding grid[0][2] to dp[1], continuing cumulative sums for the first row.

💡 Completing the first row dp array shows the path sums when moving only right across the top row.

Line:

dp[j] = dp[j-1] + grid[0][j]

💡 The minimum path sum to cell (0,2) accumulates all previous values in the first row.

fill_cells

Start processing second row: update dp[0]

Add grid[1][0] to dp[0], updating the minimum path sum for the first column of the second row.

💡 Updating dp[0] reflects moving down from the cell above in the first column.

Line:

for i in range(1, m):
    dp[0] += grid[i][0]

💡 The minimum path sum to cell (1,0) is the sum of the path to (0,0) plus the current cell value.

fill_cells

Update dp[1] for second row

Calculate dp[1] as grid[1][1] plus the minimum of dp[1] (above) and dp[0] (left).

💡 Choosing the minimum between coming from above or left ensures the path sum is minimized.

Line:

for j in range(1, n):
    dp[j] = grid[i][j] + min(dp[j], dp[j-1])

💡 The path to (1,1) is best reached from the left cell (1,0) with sum 2 rather than from above (0,1) with sum 4.

fill_cells

Update dp[2] for second row

Calculate dp[2] as grid[1][2] plus the minimum of dp[2] (above) and dp[1] (left).

💡 Again, we pick the minimum path sum from the two possible directions to minimize total cost.

Line:

dp[j] = grid[i][j] + min(dp[j], dp[j-1])

💡 The path to (1,2) is better from above (0,2) with sum 5 than from left (1,1) with sum 7.

fill_cells

Start processing third row: update dp[0]

Add grid[2][0] to dp[0], updating the minimum path sum for the first column of the third row.

💡 Moving down in the first column accumulates the path sum from above.

Line:

dp[0] += grid[i][0]

💡 The minimum path sum to cell (2,0) accumulates from the previous row's first column.

fill_cells

Update dp[1] for third row

Calculate dp[1] as grid[2][1] plus the minimum of dp[1] (above) and dp[0] (left).

💡 Choosing the minimum path sum from above or left continues to build the optimal path.

Line:

dp[j] = grid[i][j] + min(dp[j], dp[j-1])

💡 The path to (2,1) is better from left (2,0) with sum 6 than from above (1,1) with sum 7.

fill_cells

Update dp[2] for third row

Calculate dp[2] as grid[2][2] plus the minimum of dp[2] (above) and dp[1] (left).

💡 Final update completes the dp array with the minimum path sums for the last row.

Line:

dp[j] = grid[i][j] + min(dp[j], dp[j-1])

💡 The minimum path sum to the bottom-right corner is 7, the smallest possible sum.

reconstruct

Return final minimum path sum

Return the last element of dp, which holds the minimum path sum to the bottom-right corner.

💡 The final dp value is the answer to the problem.

Line:

return dp[-1]

💡 The algorithm efficiently computes the minimum path sum using only a 1D dp array.

def minPathSum(grid):
    m, n = len(grid), len(grid[0])  # STEP 1
    dp = [0]*n  # STEP 1
    dp[0] = grid[0][0]  # STEP 2
    for j in range(1, n):  # STEP 3-4
        dp[j] = dp[j-1] + grid[0][j]
    for i in range(1, m):  # STEP 5-10
        dp[0] += grid[i][0]  # STEP 5,8
        for j in range(1, n):  # STEP 6-7,9-10
            dp[j] = grid[i][j] + min(dp[j], dp[j-1])
    return dp[-1]  # STEP 11

📊

Minimum Path Sum - Watch the Algorithm Execute, Step by Step

Watching each update to the dp array reveals how the algorithm accumulates minimum sums and why it only needs one dimension of storage.

Item 0 - wt:0 val:0

i\w	0	1	2
i=0	?	?	?

Item 0 - wt:1 val:1

i\w	0	1	2
i=0	1	?	?

start

Item 0 - wt:3 val:4

i\w	0	1	2
i=0	1	4	?

update

Item 0 - wt:1 val:5

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

update

Item 1 - wt:1 val:2

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

down move

Item 1 - wt:5 val:7

i\w	0	1	2
i=0	2	7	5

min choice

Item 1 - wt:1 val:6

i\w	0	1	2
i=0	2	7	6

min choice

Item 2 - wt:4 val:6

i\w	0	1	2
i=0	6	7	6

down move

Item 2 - wt:2 val:8

i\w	0	1	2
i=0	6	8	6

min choice

Item 2 - wt:1 val:7

i\w	0	1	2
i=0	6	8	7

final answer

Item 2 - wt:1 val:7

i\w	0	1	2
i=0	6	8	7

answer

Key Takeaways

✓ The algorithm uses a single 1D dp array to store minimum path sums for each column, updating it row by row.

This insight is hard to see from code alone because the dp array is reused and overwritten, but the visualization shows its evolution clearly.

✓ Each dp cell update depends on the minimum of the value above (previous dp[j]) and the value to the left (dp[j-1]), reflecting allowed moves.

Seeing these dependencies visually helps understand why the algorithm chooses the minimum path at each step.

✓ The final answer is the last element of the dp array after processing all rows, representing the minimum path sum to the bottom-right corner.

The visualization clarifies why returning dp[-1] gives the correct answer, which might be less obvious from code alone.

Practice

1. You are given an array of balloons, each with a number representing coins. When you burst a balloon, you gain coins equal to the product of the balloon's number and its adjacent balloons' numbers. After bursting, the balloon disappears and adjacent balloons become neighbors. Which algorithmic approach guarantees finding the maximum coins you can collect by bursting all balloons in an optimal order?

easy

A. Greedy approach bursting the balloon with the highest number first

B. Sorting balloons and bursting them in ascending order

C. Dynamic programming using interval partitioning and considering the last balloon to burst in each interval

D. Simple recursion trying all burst orders without memoization

Solution

1. Step 1: Understand problem structure

   The problem requires maximizing coins by bursting balloons in an order where each burst depends on adjacent balloons, which changes dynamically.

2. Step 2: Identify suitable algorithm

   Greedy or sorting approaches fail because local choices don't guarantee global optimum. Simple recursion is correct but inefficient. Interval DP solves by considering subproblems defined by intervals and choosing the last balloon to burst in each interval, ensuring optimal substructure.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Interval DP handles overlapping subproblems and changing neighbors [OK]

Hint: Optimal substructure requires interval DP, not greedy [OK]

Common Mistakes:

• Assuming greedy bursting yields max coins
• Trying recursion without memoization
• Ignoring interval-based subproblems

2. Consider the following Python code implementing the space-optimized DP solution for Maximal Square. Given the input matrix below, what is the final returned value? Matrix: [ ["1", "0", "1"], ["1", "1", "1"], ["1", "1", "0"] ]

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

easy

A. 0

B. 4

C. 9

D. 1

Solution

1. Step 1: Trace dp array updates for each row

   Row 0: dp updates to [0,1,0,1], max_side=1; Row 1: dp updates to [0,1,1,1], then dp[3]=1+min(1,1,1)=2, max_side=2; Row 2: dp updates to [0,1,2,0], max_side remains 2.

2. Step 2: Calculate final area

   max_side=2, so area = 2*2 = 4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Max square side 2 -> area 4 [OK]

Hint: Track dp updates row-wise to find max side [OK]

Common Mistakes:

• Off-by-one in indexing dp array
• Confusing prev and temp updates
• Returning max_side instead of area

3. You are given a grid where some cells are blocked and others are free. You need to find the number of unique paths from the top-left corner to the bottom-right corner, moving only down or right, but you cannot pass through blocked cells. Which algorithmic approach guarantees an efficient and correct solution for this problem?

easy

A. Dynamic Programming that builds solutions using previously computed subproblems while skipping blocked cells

B. Pure brute force recursion exploring all paths without memoization

C. Greedy algorithm that always moves right if possible, else down

D. Dijkstra's shortest path algorithm treating grid cells as graph nodes

Solution

1. Step 1: Understand problem constraints

   The problem requires counting all unique paths avoiding obstacles, which involves overlapping subproblems and optimal substructure.

2. Step 2: Identify suitable algorithm

   Dynamic Programming efficiently computes the number of paths by reusing results and handling obstacles by zeroing paths through blocked cells.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP handles obstacles and overlapping subproblems correctly [OK]

Hint: DP handles obstacles and overlapping subproblems correctly [OK]

Common Mistakes:

• Thinking greedy can find all paths
• Using brute force without pruning
• Confusing shortest path with counting paths

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