Minimum Path Sum

📋

Problem

Imagine you are navigating a grid-like city where each block has a cost to cross. You want to find the cheapest route from the top-left corner to the bottom-right corner, moving only right or down.

Given an m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. You can only move either down or right at any point in time.

m == grid.lengthn == grid[i].length1 ≤ m, n ≤ 2000 ≤ grid[i][j] ≤ 100

Edge cases: Single cell grid → output is the cell valueGrid with all zeros → output is 0Grid with one row → sum of that row

</>

IDE

def minPathSum(grid: list[list[int]]) -> int:public int minPathSum(int[][] grid)int minPathSum(vector<vector<int>>& grid)function minPathSum(grid)

def minPathSum(grid):
    # Write your solution here
    pass

class Solution {
    public int minPathSum(int[][] grid) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int minPathSum(vector<vector<int>>& grid) {
    // Write your solution here
    return 0;
}

function minPathSum(grid) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Wrong sums due to ignoring initialization of first row or columnNot initializing dp first row and first column with cumulative sums✅ Initialize dp[0][j] = dp[0][j-1] + grid[0][j] and dp[i][0] = dp[i-1][0] + grid[i][0]

Wrong: Output larger than expected due to greedy local minimum choicesUsing greedy approach picking min neighbor instead of full DP✅ Implement full DP recurrence considering min of top and left cells for each dp[i][j]

Wrong: Index out of range or off-by-one errors causing wrong sumsIncorrect dp indexing or missing base cases✅ Carefully use dp[i-1][j] and dp[i][j-1] with proper boundary checks

Wrong: TLE on large inputsUsing brute force recursion without memoization or DP✅ Use bottom-up DP or top-down memoization to achieve O(m*n) time

✓

Test Cases

Focus on handling grids with minimal sizes and zero values correctly.

Watch out for common pitfalls like greedy traps and indexing errors.

Optimize your solution to run efficiently on large grids.

t1_01basic

Input{"grid":[[1,3,1],[1,5,1],[4,2,1]]}

Expected7

⏱ Performance - must finish in 2000ms

The path 1→3→1→1→1 minimizes the sum.

💡 Think about dynamic programming on a grid where each cell depends on the minimum path to it.

💡 Use a 2D DP table where dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).

💡 Initialize first row and column with cumulative sums, then fill the rest using the recurrence.

Why it failed: Incorrect output means the recurrence is wrong or boundary initialization is missing. Fix by ensuring dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) with proper base cases.

✓ Correctly computes minimum path sum using DP recurrence.

t1_02basic

Input{"grid":[[1,2,3],[4,5,6]]}

Expected12

⏱ Performance - must finish in 2000ms

The path 1→2→3→6 minimizes the sum: 1+2+3+6=12.

💡 Try computing minimum path sums row-wise and column-wise for a rectangular grid.

💡 Remember to handle grids with different numbers of rows and columns correctly.

💡 Use dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) and initialize edges properly.

Why it failed: Wrong output likely due to incorrect handling of grid edges or mixing row/column indices. Fix by carefully initializing first row and column sums.

✓ Correctly handles rectangular grids with DP.

t2_01edge

Input{"grid":[[5]]}

Expected5

⏱ Performance - must finish in 2000ms

Single cell grid, minimum path sum is the cell value itself.

💡 Check how your code handles grids with only one cell.

💡 Base case: dp[0][0] should be grid[0][0].

💡 Ensure no out-of-bound errors when grid size is 1x1.

Why it failed: Fails single cell case if code assumes multiple rows/columns. Fix by handling dp[0][0] = grid[0][0] explicitly.

✓ Correctly returns cell value for single cell grid.

t2_02edge

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

Expected0

⏱ Performance - must finish in 2000ms

Grid with all zeros, minimum path sum is zero.

💡 Test grids with zero values to ensure no incorrect additions.

💡 DP should accumulate sums correctly even if all zeros.

💡 Check initialization of dp arrays to zero or grid values.

Why it failed: Incorrect output if code adds non-zero defaults or fails to handle zero values. Fix by initializing dp with grid values.

✓ Correctly handles zero-valued grids.

t2_03edge

Input{"grid":[[1,2,3,4,5]]}

Expected15

⏱ Performance - must finish in 2000ms

Grid with one row, minimum path sum is sum of that row.

💡 For single row, path can only move right.

💡 DP reduces to cumulative sum of the row.

💡 Check if code handles single row without errors.

Why it failed: Fails if code tries to move down in single row grid. Fix by correctly initializing first row dp values.

✓ Correctly computes sum for single row grids.

t3_01corner

Input{"grid":[[1,100,1],[1,100,1],[1,1,1]]}

Expected5

⏱ Performance - must finish in 2000ms

Greedy approach fails here; must avoid costly middle cells and go down then right.

💡 Greedy picking smallest immediate neighbor can fail in grids with large intermediate values.

💡 Use DP to consider all paths, not just local minimums.

💡 Check dp recurrence to ensure global minimum path is found, not greedy local minimum.

Why it failed: Greedy approach returns 7 or more by choosing local minimums incorrectly. Fix by implementing full DP with min of top and left cells.

✓ DP correctly finds global minimum path sum avoiding costly cells.

t3_02corner

Input{"grid":[[1],[2],[3],[4]]}

Expected10

⏱ Performance - must finish in 2000ms

Single column grid, path must move down only; sum all cells.

💡 For single column, path can only move down.

💡 DP reduces to cumulative sum of the column.

💡 Check if code handles single column without errors.

Why it failed: Fails if code tries to move right in single column grid. Fix by initializing first column dp values correctly.

✓ Correctly computes sum for single column grids.

t3_03corner

Input{"grid":[[1,2],[1,1]]}

Expected3

⏱ Performance - must finish in 2000ms

Off-by-one errors in indexing can cause wrong sums; correct path is 1→1→1.

💡 Check indexing carefully when filling dp table.

💡 Ensure dp[i][j] uses dp[i-1][j] and dp[i][j-1] correctly.

💡 Verify base cases for first row and first column.

Why it failed: Off-by-one indexing causes incorrect dp values. Fix by carefully using dp indices and initializing edges.

✓ Correctly handles indexing and base cases.

t4_01performance

Input{"_description":"n=200 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Grid size 200x200, O(m*n) = 40,000 operations expected to complete within 2 seconds.

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

💡 Avoid exponential brute force recursion.

💡 Use bottom-up tabulation or memoization for efficiency.

Why it failed: Brute force or exponential recursion causes TLE. Fix by implementing O(m*n) DP solution.

✓ Efficient DP solution runs within time limits.

Practice

1. You need to find the cheapest cost to travel from a source city to a destination city with at most K stops, given a list of flights with costs. Which algorithmic approach guarantees finding the optimal solution efficiently under these constraints?

easy

A. Greedy algorithm using Dijkstra's shortest path without modification

B. Topological sort followed by single pass relaxation of edges

C. Simple depth-first search exploring all paths without pruning

D. Dynamic programming using a bottom-up approach iterating over stops

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the cheapest flight with at most K stops, which limits path length and requires considering multiple paths.

2. Step 2: Identify suitable algorithm

   Greedy Dijkstra fails because it doesn't limit stops; DFS is exponential; topological sort requires DAG which flights graph may not be. Bottom-up DP iterates over stops and relaxes edges, guaranteeing optimal cost within K stops.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bottom-up DP with stops limit ensures optimal solution [OK]

Hint: DP with stops limit ensures optimal cost [OK]

Common Mistakes:

• Using Dijkstra without stop limit
• Trying DFS without pruning
• Assuming DAG for topological sort

2. Consider the following Python code implementing the Cherry Pickup problem using bottom-up DP. Given the input grid below, what is the final returned value?

grid = [
  [0, 1, -1],
  [1, 0, -1],
  [1, 1,  1]
]

from typing import List

def cherryPickup(grid: List[List[int]]) -> int:
    n = len(grid)
    dp = [[[-float('inf')] * n for _ in range(n)] for __ in range(n)]
    dp[0][0][0] = grid[0][0]
    for step in range(1, 2 * (n - 1) + 1):
        for r1 in range(max(0, step - (n - 1)), min(n, step + 1)):
            c1 = step - r1
            if c1 < 0 or c1 >= n:
                continue
            for r2 in range(max(0, step - (n - 1)), min(n, step + 1)):
                c2 = step - r2
                if c2 < 0 or c2 >= n:
                    continue
                if grid[r1][c1] == -1 or grid[r2][c2] == -1:
                    continue
                candidates = []
                if r1 > 0 and r2 > 0:
                    candidates.append(dp[r1 - 1][c1][r2 - 1])
                if r1 > 0 and c2 > 0:
                    candidates.append(dp[r1 - 1][c1][r2])
                if c1 > 0 and r2 > 0:
                    candidates.append(dp[r1][c1 - 1][r2 - 1])
                if c1 > 0 and c2 > 0:
                    candidates.append(dp[r1][c1 - 1][r2])
                best_prev = max(candidates) if candidates else -float('inf')
                if best_prev == -float('inf'):
                    continue
                val = best_prev + grid[r1][c1]
                if r1 != r2:
                    val += grid[r2][c2]
                dp[r1][c1][r2] = max(dp[r1][c1][r2], val)
    return max(0, dp[n - 1][n - 1][n - 1])

print(cherryPickup(grid))

easy

A. 6

B. 5

C. 4

D. 3

Solution

1. Step 1: Trace dp states for step=4 (final step for 3x3 grid)

   At step=4, both players reach bottom-right (2,2). The dp value dp[2][2][2] accumulates max cherries collected along valid paths avoiding thorns (-1).

2. Step 2: Calculate max cherries collected

   By tracing paths, max cherries collected is 6, considering both players' paths and avoiding double counting.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Manual path tracing confirms max cherries = 6 [OK]

Hint: Trace dp at final step for both players [OK]

Common Mistakes:

• Off-by-one errors in step or indices
• Double counting cherries when players overlap
• Ignoring thorn cells leading to invalid paths

3. You are given a printer that can print a continuous substring of identical characters in one turn. Given a string, you want to find the minimum number of turns needed to print the entire string. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic Programming over intervals with string compression and merging states

B. Greedy approach printing each character separately from left to right

C. Simple recursion without memoization or compression

D. Sliding window technique to find longest repeated substrings

Solution

1. Step 1: Understand problem constraints

   The problem requires minimizing turns to print a string where each turn prints a continuous block of identical characters.

2. Step 2: Identify suitable algorithmic pattern

   Greedy or sliding window approaches fail to merge overlapping prints optimally. Pure recursion is inefficient. Interval DP with string compression and merging states captures overlapping subproblems and optimizes turns.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Interval DP with compression is known optimal [OK]

Hint: Interval DP with compression merges overlapping prints [OK]

Common Mistakes:

• Assuming greedy printing each char separately is optimal

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

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