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. Given the following code for finding the cheapest flight within K stops, what is the returned value for the input below? Input: n = 3 flights = [[0,1,100],[1,2,100],[0,2,500]] src = 0 dst = 2 K = 1

def findCheapestPrice(n, flights, src, dst, K):
    INF = float('inf')
    prev = [INF] * n
    prev[src] = 0
    for _ in range(K + 1):
        curr = prev[:]
        for u, v, w in flights:
            if prev[u] != INF:
                curr[v] = min(curr[v], prev[u] + w)
        prev = curr
    return prev[dst] if prev[dst] != INF else -1

print(findCheapestPrice(n, flights, src, dst, K))

easy

A. 500

B. 200

C. -1

D. 100

Solution

1. Step 1: Trace dp arrays for each iteration

   Initially prev = [0, inf, inf]. After first iteration (0 stops), curr updates cost to city 1 as 100 and city 2 as 500. After second iteration (1 stop), curr updates city 2 cost to min(500, 100 + 100) = 200.

2. Step 2: Return final cost for destination

   prev[2] after K+1=2 iterations is 200, which is the cheapest cost with at most 1 stop.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP updates costs correctly over K+1 iterations [OK]

Hint: DP updates cost over K+1 iterations [OK]

Common Mistakes:

• Returning direct edge cost ignoring stops
• Off-by-one in iteration count
• Confusing curr and prev arrays

3. You are given a triangular array of numbers where each element can only move to one of the two adjacent numbers in the row below. The goal is to find the minimum sum path from the top to the bottom. Which algorithmic approach guarantees an optimal solution efficiently?

easy

A. Greedy algorithm that picks the minimum adjacent number at each step

B. Divide and conquer by splitting the triangle into two halves and solving independently

C. Pure brute force recursion exploring all paths without memoization

D. Dynamic Programming using bottom-up tabulation to build minimum path sums

Solution

1. Step 1: Understand problem constraints and properties

   The problem requires finding a minimum path sum with overlapping subproblems and optimal substructure, which suits dynamic programming.

2. Step 2: Identify suitable algorithm

   Bottom-up DP tabulation efficiently computes minimum sums from the bottom row up, avoiding recomputation and ensuring optimality.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP tabulation solves overlapping subproblems efficiently [OK]

Hint: DP bottom-up tabulation ensures optimal substructure [OK]

Common Mistakes:

• Assuming greedy choice is always optimal
• Using brute force recursion without memoization
• Trying to split triangle independently ignoring dependencies

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. Suppose the Unique Paths problem is modified so that you can move right, down, or diagonally (down-right) at each step. Which of the following changes correctly adapts the space-optimized DP solution to count all unique paths?

hard

A. Use a 2D DP array where dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]

B. Update dp[j] as dp[j] + dp[j - 1] + dp[j - 2] in the inner loop

C. Keep the 1D dp array and update dp[j] = dp[j] + dp[j - 1] only, ignoring diagonal moves

D. Use recursion without memoization to handle the extra diagonal move

Solution

1. Step 1: Understand diagonal move impact

   Diagonal moves depend on the top-left neighbor dp[i-1][j-1], which cannot be tracked with a single 1D array.

2. Step 2: Choose correct DP structure

   A 2D DP array is needed to access dp[i-1][j-1] directly; update rule: dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1].

3. Step 3: Reject incorrect options

   Update dp[j] as dp[j] + dp[j - 1] + dp[j - 2] in the inner loop incorrectly accesses dp[j-2] in 1D array which doesn't represent diagonal; Keep the 1D dp array and update dp[j] = dp[j] + dp[j - 1] only, ignoring diagonal moves ignores diagonal; Use recursion without memoization to handle the extra diagonal move is inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Diagonal requires 2D DP for correct neighbor access [OK]

Hint: Diagonal moves require 2D DP for top-left neighbor [OK]

Common Mistakes:

• Trying to handle diagonal with 1D DP
• Ignoring diagonal moves in update