Minimum Falling Path Sum

🎯

Minimum Falling Path Sum

mediumDPAmazonGoogle

Imagine you are navigating a grid of numbers from top to bottom, trying to find the path that costs you the least energy, but you can only move straight down or diagonally down-left or down-right at each step.

💡 This problem is a classic example of grid dynamic programming where the challenge is to minimize a path sum with adjacency constraints. Beginners often struggle because they try greedy or brute force without recognizing overlapping subproblems and the need for memoization or tabulation.

📋

Problem Statement

Given an n x n integer matrix 'matrix', return the minimum sum of any falling path through matrix. A falling path starts at any element in the first row and chooses one element from each row. The next row's choice must be in a column that is either the same, or adjacent to the previous row's column (i.e., column j, j-1, or j+1).

1 ≤ n ≤ 1000-100 ≤ matrix[i][j] ≤ 100

💡

Example

Input"[[2,1,3],[6,5,4],[7,8,9]]"

Output13

One minimum falling path is 1 → 5 → 7 with sum 13.

• n = 1 → output is the single element itself
• All elements are negative → must still find minimum sum path
• Matrix with all equal elements → minimum path is n times that element
• Matrix with large n (e.g., 1000) → tests efficiency of solution

🔁

Why DP?

Why greedy fails:

A greedy approach that picks the minimum element in the next row without considering adjacency can fail. For example, picking the smallest element in the next row might not be adjacent to the current column, leading to invalid paths or suboptimal sums.

DP state:

dp[i][j] represents the minimum falling path sum to reach cell (i, j) from any cell in the first row following the adjacency rules.

Recurrence:dp[i][j] = matrix[i][j] + min(dp[i-1][j], dp[i-1][j-1], dp[i-1][j+1])

The minimum path sum to cell (i,j) is its own value plus the minimum of the three possible cells above it.

⚠️

Common Mistakes

Ignoring boundary checks for j-1 and j+1

Index out of range errors or incorrect results

✅ Add explicit checks for column boundaries before accessing dp

Not memoizing in recursive approach

Exponential time leading to TLE

✅ Add memo table to cache results

Overwriting dp array in place without backup

Using updated values prematurely leads to incorrect results

✅ Use a separate array for current row or iterate carefully

Confusing minimum path sum with maximum

Wrong answer due to using max instead of min

✅ Use min functions consistently

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's recursive structure and why naive recursion is inefficient due to repeated calculations.

Intuition

Try all possible falling paths starting from each element in the first row and recursively compute the minimum sum for each path.

Algorithm

1. Start from each element in the first row.
2. Recursively explore the three possible adjacent cells in the next row.
3. Calculate the sum of the current cell and the minimum of the recursive calls.
4. Return the minimum sum among all starting points.

💡 The recursion tree grows exponentially because each cell branches into up to three recursive calls.

Recurrence:f(i,j) = matrix[i][j] + min(f(i+1,j), f(i+1,j-1), f(i+1,j+1))

</>

Code

from math import inf

def minFallingPathSum(matrix):
    n = len(matrix)

    def dfs(i, j):
        if j < 0 or j >= n:
            return inf
        if i == n - 1:
            return matrix[i][j]
        return matrix[i][j] + min(dfs(i+1, j), dfs(i+1, j-1), dfs(i+1, j+1))

    return min(dfs(0, j) for j in range(n))

# Example usage
if __name__ == '__main__':
    matrix = [[2,1,3],[6,5,4],[7,8,9]]
    print(minFallingPathSum(matrix))  # Output: 13

Line Notes

def dfs(i, j):Defines recursive helper to compute min path sum from (i,j)

if j < 0 or j >= n:Bounds check to avoid invalid columns

if i == n - 1:Base case: last row returns its own value

return matrix[i][j] + min(dfs(i+1, j), dfs(i+1, j-1), dfs(i+1, j+1))Recursive call exploring all three adjacent next-row cells

public class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        Integer[][] memo = new Integer[n][n];
        int minSum = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            minSum = Math.min(minSum, dfs(matrix, 0, j, n, memo));
        }
        return minSum;
    }

    private int dfs(int[][] matrix, int i, int j, int n, Integer[][] memo) {
        if (j < 0 || j >= n) return Integer.MAX_VALUE;
        if (i == n - 1) return matrix[i][j];
        if (memo[i][j] != null) return memo[i][j];
        int left = dfs(matrix, i + 1, j - 1, n, memo);
        int down = dfs(matrix, i + 1, j, n, memo);
        int right = dfs(matrix, i + 1, j + 1, n, memo);
        memo[i][j] = matrix[i][j] + Math.min(left, Math.min(down, right));
        return memo[i][j];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] matrix = {{2,1,3},{6,5,4},{7,8,9}};
        System.out.println(sol.minFallingPathSum(matrix)); // Output: 13
    }
}

Line Notes

if (j < 0 || j >= n) return Integer.MAX_VALUE;Bounds check to avoid invalid columns

if (i == n - 1) return matrix[i][j];Base case returns cell value at last row

memo[i][j] = matrix[i][j] + Math.min(left, Math.min(down, right));Memoize minimum path sum for (i,j)

for (int j = 0; j < n; j++)Try all starting points in first row

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int dfs(const vector<vector<int>>& matrix, int i, int j, vector<vector<int>>& memo) {
    int n = matrix.size();
    if (j < 0 || j >= n) return INT_MAX;
    if (i == n - 1) return matrix[i][j];
    if (memo[i][j] != INT_MIN) return memo[i][j];
    int left = dfs(matrix, i + 1, j - 1, memo);
    int down = dfs(matrix, i + 1, j, memo);
    int right = dfs(matrix, i + 1, j + 1, memo);
    memo[i][j] = matrix[i][j] + min({left, down, right});
    return memo[i][j];
}

int minFallingPathSum(vector<vector<int>>& matrix) {
    int n = matrix.size();
    vector<vector<int>> memo(n, vector<int>(n, INT_MIN));
    int ans = INT_MAX;
    for (int j = 0; j < n; ++j) {
        ans = min(ans, dfs(matrix, 0, j, memo));
    }
    return ans;
}

int main() {
    vector<vector<int>> matrix = {{2,1,3},{6,5,4},{7,8,9}};
    cout << minFallingPathSum(matrix) << endl; // Output: 13
    return 0;
}

Line Notes

if (j < 0 || j >= n) return INT_MAX;Avoid invalid column indices

if (i == n - 1) return matrix[i][j];Base case returns last row cell value

if (memo[i][j] != INT_MIN) return memo[i][j];Return cached result to avoid recomputation

ans = min(ans, dfs(matrix, 0, j, memo));Try all starting points in first row

function minFallingPathSum(matrix) {
    const n = matrix.length;
    const memo = Array.from({ length: n }, () => Array(n).fill(null));

    function dfs(i, j) {
        if (j < 0 || j >= n) return Infinity;
        if (i === n - 1) return matrix[i][j];
        if (memo[i][j] !== null) return memo[i][j];
        const left = dfs(i + 1, j - 1);
        const down = dfs(i + 1, j);
        const right = dfs(i + 1, j + 1);
        memo[i][j] = matrix[i][j] + Math.min(left, down, right);
        return memo[i][j];
    }

    let result = Infinity;
    for (let j = 0; j < n; j++) {
        result = Math.min(result, dfs(0, j));
    }
    return result;
}

// Example usage
const matrix = [[2,1,3],[6,5,4],[7,8,9]];
console.log(minFallingPathSum(matrix)); // Output: 13

Line Notes

if (j < 0 || j >= n) return Infinity;Bounds check to prevent invalid indices

if (i === n - 1) return matrix[i][j];Base case returns last row value

if (memo[i][j] !== null) return memo[i][j];Memoization to avoid repeated work

for (let j = 0; j < n; j++)Try all possible starting columns in first row

⏱

Complexity

TimeO(3^n) without memoization

SpaceO(n) recursion stack depth

Each cell branches into up to 3 recursive calls, leading to exponential time.

💡 For n=10, this means up to 3^10 = 59049 calls, which is very slow.

Interview Verdict: TLE / Use only to introduce problem structure

This approach is too slow for large inputs but helps understand the problem's recursive nature.

🧠

Top-Down DP with Memoization

💡 Memoization caches results of recursive calls to avoid recomputation, drastically improving efficiency while keeping the recursive intuition.

Intuition

Use recursion but store results for each cell so that each state is computed once.

Algorithm

1. Initialize a memo table to store results for each cell.
2. Recursively compute minimum path sums, returning cached results if available.
3. For each cell, compute the minimum of the three adjacent cells in the next row plus current cell value.
4. Return the minimum among all starting points in the first row.

💡 Memoization prevents exponential blowup by caching results.

Recurrence:dp[i][j] = matrix[i][j] + min(dp[i+1][j], dp[i+1][j-1], dp[i+1][j+1])

</>

Code

from math import inf

def minFallingPathSum(matrix):
    n = len(matrix)
    memo = [[None]*n for _ in range(n)]

    def dfs(i, j):
        if j < 0 or j >= n:
            return inf
        if i == n - 1:
            return matrix[i][j]
        if memo[i][j] is not None:
            return memo[i][j]
        memo[i][j] = matrix[i][j] + min(dfs(i+1, j), dfs(i+1, j-1), dfs(i+1, j+1))
        return memo[i][j]

    return min(dfs(0, j) for j in range(n))

# Example usage
if __name__ == '__main__':
    matrix = [[2,1,3],[6,5,4],[7,8,9]]
    print(minFallingPathSum(matrix))  # Output: 13

Line Notes

memo = [[None]*n for _ in range(n)]Initialize memo table to store computed results

if memo[i][j] is not None:Return cached result to avoid recomputation

memo[i][j] = matrix[i][j] + min(...)Store computed minimum path sum for (i,j)

return min(dfs(0, j) for j in range(n))Try all starting points in first row

public class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        Integer[][] memo = new Integer[n][n];
        int minSum = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            minSum = Math.min(minSum, dfs(matrix, 0, j, n, memo));
        }
        return minSum;
    }

    private int dfs(int[][] matrix, int i, int j, int n, Integer[][] memo) {
        if (j < 0 || j >= n) return Integer.MAX_VALUE;
        if (i == n - 1) return matrix[i][j];
        if (memo[i][j] != null) return memo[i][j];
        int left = dfs(matrix, i + 1, j - 1, n, memo);
        int down = dfs(matrix, i + 1, j, n, memo);
        int right = dfs(matrix, i + 1, j + 1, n, memo);
        memo[i][j] = matrix[i][j] + Math.min(left, Math.min(down, right));
        return memo[i][j];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] matrix = {{2,1,3},{6,5,4},{7,8,9}};
        System.out.println(sol.minFallingPathSum(matrix)); // Output: 13
    }
}

Line Notes

Integer[][] memo = new Integer[n][n];Memo table to cache results

if (memo[i][j] != null) return memo[i][j];Return cached result if available

memo[i][j] = matrix[i][j] + Math.min(...)Store computed minimum path sum

for (int j = 0; j < n; j++)Try all starting columns in first row

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int dfs(const vector<vector<int>>& matrix, int i, int j, vector<vector<int>>& memo) {
    int n = matrix.size();
    if (j < 0 || j >= n) return INT_MAX;
    if (i == n - 1) return matrix[i][j];
    if (memo[i][j] != INT_MIN) return memo[i][j];
    int left = dfs(matrix, i + 1, j - 1, memo);
    int down = dfs(matrix, i + 1, j, memo);
    int right = dfs(matrix, i + 1, j + 1, memo);
    memo[i][j] = matrix[i][j] + min({left, down, right});
    return memo[i][j];
}

int minFallingPathSum(vector<vector<int>>& matrix) {
    int n = matrix.size();
    vector<vector<int>> memo(n, vector<int>(n, INT_MIN));
    int ans = INT_MAX;
    for (int j = 0; j < n; ++j) {
        ans = min(ans, dfs(matrix, 0, j, memo));
    }
    return ans;
}

int main() {
    vector<vector<int>> matrix = {{2,1,3},{6,5,4},{7,8,9}};
    cout << minFallingPathSum(matrix) << endl; // Output: 13
    return 0;
}

Line Notes

vector<vector<int>> memo(n, vector<int>(n, INT_MIN));Memo table initialized with sentinel values

if (memo[i][j] != INT_MIN) return memo[i][j];Return cached result if computed

memo[i][j] = matrix[i][j] + min({left, down, right});Store computed minimum path sum

ans = min(ans, dfs(matrix, 0, j, memo));Try all starting columns in first row

function minFallingPathSum(matrix) {
    const n = matrix.length;
    const memo = Array.from({ length: n }, () => Array(n).fill(null));

    function dfs(i, j) {
        if (j < 0 || j >= n) return Infinity;
        if (i === n - 1) return matrix[i][j];
        if (memo[i][j] !== null) return memo[i][j];
        const left = dfs(i + 1, j - 1);
        const down = dfs(i + 1, j);
        const right = dfs(i + 1, j + 1);
        memo[i][j] = matrix[i][j] + Math.min(left, down, right);
        return memo[i][j];
    }

    let result = Infinity;
    for (let j = 0; j < n; j++) {
        result = Math.min(result, dfs(0, j));
    }
    return result;
}

// Example usage
const matrix = [[2,1,3],[6,5,4],[7,8,9]];
console.log(minFallingPathSum(matrix)); // Output: 13

Line Notes

const memo = Array.from({ length: n }, () => Array(n).fill(null));Initialize memo table for caching

if (memo[i][j] !== null) return memo[i][j];Return cached result if available

memo[i][j] = matrix[i][j] + Math.min(left, down, right);Store computed minimum path sum

for (let j = 0; j < n; j++)Try all starting columns in first row

⏱

Complexity

TimeO(n^2)

SpaceO(n^2) for memoization and recursion stack

Each cell is computed once and stored, reducing exponential calls to polynomial.

💡 For n=1000, this means about 1,000,000 operations, which is feasible.

Interview Verdict: Accepted / Efficient for medium constraints

Memoization optimizes brute force to a practical solution for interview constraints.

🧠

Bottom-Up DP (Tabulation)

💡 Tabulation builds the solution iteratively from the base case up, which is often easier to debug and understand than recursion.

Intuition

Start from the first row and iteratively compute minimum path sums for each cell in subsequent rows using previously computed results.

Algorithm

1. Initialize dp array with first row equal to matrix's first row.
2. For each subsequent row, compute dp[i][j] as matrix[i][j] plus minimum of dp[i-1][j], dp[i-1][j-1], dp[i-1][j+1].
3. Handle boundary columns carefully to avoid invalid indices.
4. Return the minimum value in the last dp row.

💡 This approach avoids recursion and uses a table to store intermediate results.

Recurrence:dp[i][j] = matrix[i][j] + min(dp[i-1][j], dp[i-1][j-1], dp[i-1][j+1])

</>

Code

def minFallingPathSum(matrix):
    n = len(matrix)
    dp = [row[:] for row in matrix]

    for i in range(1, n):
        for j in range(n):
            best = dp[i-1][j]
            if j > 0:
                best = min(best, dp[i-1][j-1])
            if j < n - 1:
                best = min(best, dp[i-1][j+1])
            dp[i][j] = matrix[i][j] + best

    return min(dp[-1])

# Example usage
if __name__ == '__main__':
    matrix = [[2,1,3],[6,5,4],[7,8,9]]
    print(minFallingPathSum(matrix))  # Output: 13

Line Notes

dp = [row[:] for row in matrix]Copy matrix to dp to preserve original and initialize base case

for i in range(1, n):Iterate rows from second to last

best = dp[i-1][j]Start with vertical above cell

if j > 0: best = min(best, dp[i-1][j-1])Check left diagonal if valid

public class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[][] dp = new int[n][n];
        for (int j = 0; j < n; j++) {
            dp[0][j] = matrix[0][j];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int best = dp[i-1][j];
                if (j > 0) best = Math.min(best, dp[i-1][j-1]);
                if (j < n - 1) best = Math.min(best, dp[i-1][j+1]);
                dp[i][j] = matrix[i][j] + best;
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            ans = Math.min(ans, dp[n-1][j]);
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] matrix = {{2,1,3},{6,5,4},{7,8,9}};
        System.out.println(sol.minFallingPathSum(matrix)); // Output: 13
    }
}

Line Notes

int[][] dp = new int[n][n];Create dp table to store minimum sums

dp[0][j] = matrix[0][j];Initialize first row base case

int best = dp[i-1][j];Start with vertical above cell

if (j > 0) best = Math.min(best, dp[i-1][j-1]);Check left diagonal if valid

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minFallingPathSum(vector<vector<int>>& matrix) {
    int n = matrix.size();
    vector<vector<int>> dp = matrix;

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int best = dp[i-1][j];
            if (j > 0) best = min(best, dp[i-1][j-1]);
            if (j < n - 1) best = min(best, dp[i-1][j+1]);
            dp[i][j] = matrix[i][j] + best;
        }
    }

    return *min_element(dp[n-1].begin(), dp[n-1].end());
}

int main() {
    vector<vector<int>> matrix = {{2,1,3},{6,5,4},{7,8,9}};
    cout << minFallingPathSum(matrix) << endl; // Output: 13
    return 0;
}

Line Notes

vector<vector<int>> dp = matrix;Copy matrix to dp for base case and updates

for (int i = 1; i < n; ++i)Iterate rows from second to last

int best = dp[i-1][j];Start with vertical above cell

if (j > 0) best = min(best, dp[i-1][j-1]);Check left diagonal if valid

function minFallingPathSum(matrix) {
    const n = matrix.length;
    const dp = matrix.map(row => row.slice());

    for (let i = 1; i < n; i++) {
        for (let j = 0; j < n; j++) {
            let best = dp[i-1][j];
            if (j > 0) best = Math.min(best, dp[i-1][j-1]);
            if (j < n - 1) best = Math.min(best, dp[i-1][j+1]);
            dp[i][j] = matrix[i][j] + best;
        }
    }

    return Math.min(...dp[n-1]);
}

// Example usage
const matrix = [[2,1,3],[6,5,4],[7,8,9]];
console.log(minFallingPathSum(matrix)); // Output: 13

Line Notes

const dp = matrix.map(row => row.slice());Copy matrix to dp for base case and updates

for (let i = 1; i < n; i++)Iterate rows from second to last

let best = dp[i-1][j];Start with vertical above cell

if (j > 0) best = Math.min(best, dp[i-1][j-1]);Check left diagonal if valid

⏱

Complexity

TimeO(n^2)

SpaceO(n^2)

We fill an n x n dp table once, each cell computed in O(1).

💡 For n=1000, about 1,000,000 operations, efficient for interviews.

Interview Verdict: Accepted / Optimal iterative solution

Tabulation is often preferred for clarity and iterative control.

🧠

Space Optimized Bottom-Up DP

💡 Since dp[i][j] depends only on dp[i-1][*], we can reduce space from O(n^2) to O(n) by keeping only one previous row.

Intuition

Use a single 1D array to store minimum path sums for the previous row and update it for the current row.

Algorithm

1. Initialize a 1D dp array with the first row of the matrix.
2. For each subsequent row, create a temporary array to store current row results.
3. For each column, compute minimum path sum using previous dp array's adjacent values.
4. Update dp array with current row results.
5. Return the minimum value in dp after processing all rows.

💡 This approach saves memory by reusing a single array and careful iteration.

Recurrence:dp[j] = matrix[i][j] + min(dp_prev[j], dp_prev[j-1], dp_prev[j+1])

</>

Code

def minFallingPathSum(matrix):
    n = len(matrix)
    dp = matrix[0][:]

    for i in range(1, n):
        new_dp = [0]*n
        for j in range(n):
            best = dp[j]
            if j > 0:
                best = min(best, dp[j-1])
            if j < n - 1:
                best = min(best, dp[j+1])
            new_dp[j] = matrix[i][j] + best
        dp = new_dp

    return min(dp)

# Example usage
if __name__ == '__main__':
    matrix = [[2,1,3],[6,5,4],[7,8,9]]
    print(minFallingPathSum(matrix))  # Output: 13

Line Notes

dp = matrix[0][:]Initialize dp with first row values

new_dp = [0]*nTemporary array for current row computations

best = dp[j]Start with vertical above cell

dp = new_dpUpdate dp to current row results

public class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[] dp = new int[n];
        System.arraycopy(matrix[0], 0, dp, 0, n);

        for (int i = 1; i < n; i++) {
            int[] newDp = new int[n];
            for (int j = 0; j < n; j++) {
                int best = dp[j];
                if (j > 0) best = Math.min(best, dp[j - 1]);
                if (j < n - 1) best = Math.min(best, dp[j + 1]);
                newDp[j] = matrix[i][j] + best;
            }
            dp = newDp;
        }

        int ans = Integer.MAX_VALUE;
        for (int val : dp) ans = Math.min(ans, val);
        return ans;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] matrix = {{2,1,3},{6,5,4},{7,8,9}};
        System.out.println(sol.minFallingPathSum(matrix)); // Output: 13
    }
}

Line Notes

int[] dp = new int[n];1D dp array for previous row

System.arraycopy(matrix[0], 0, dp, 0, n);Initialize dp with first row

int[] newDp = new int[n];Temporary array for current row

dp = newDp;Update dp to current row results

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minFallingPathSum(vector<vector<int>>& matrix) {
    int n = matrix.size();
    vector<int> dp = matrix[0];

    for (int i = 1; i < n; ++i) {
        vector<int> new_dp(n);
        for (int j = 0; j < n; ++j) {
            int best = dp[j];
            if (j > 0) best = min(best, dp[j-1]);
            if (j < n - 1) best = min(best, dp[j+1]);
            new_dp[j] = matrix[i][j] + best;
        }
        dp = new_dp;
    }

    return *min_element(dp.begin(), dp.end());
}

int main() {
    vector<vector<int>> matrix = {{2,1,3},{6,5,4},{7,8,9}};
    cout << minFallingPathSum(matrix) << endl; // Output: 13
    return 0;
}

Line Notes

vector<int> dp = matrix[0];Initialize dp with first row values

vector<int> new_dp(n);Temporary array for current row

int best = dp[j];Start with vertical above cell

dp = new_dp;Update dp to current row results

function minFallingPathSum(matrix) {
    const n = matrix.length;
    let dp = matrix[0].slice();

    for (let i = 1; i < n; i++) {
        const newDp = new Array(n);
        for (let j = 0; j < n; j++) {
            let best = dp[j];
            if (j > 0) best = Math.min(best, dp[j - 1]);
            if (j < n - 1) best = Math.min(best, dp[j + 1]);
            newDp[j] = matrix[i][j] + best;
        }
        dp = newDp;
    }

    return Math.min(...dp);
}

// Example usage
const matrix = [[2,1,3],[6,5,4],[7,8,9]];
console.log(minFallingPathSum(matrix)); // Output: 13

Line Notes

let dp = matrix[0].slice();Initialize dp with first row values

const newDp = new Array(n);Temporary array for current row

let best = dp[j];Start with vertical above cell

dp = newDp;Update dp to current row results

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Only one 1D dp array of size n is maintained, reducing space from O(n^2).

💡 For n=1000, this reduces memory usage significantly while maintaining speed.

Interview Verdict: Accepted / Optimal space solution

Space optimization is a common interview follow-up and shows deep understanding.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding bottom-up DP or space-optimized DP is usually best for clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(3^n)	O(n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Top-Down DP with Memoization	O(n^2)	O(n^2)	Possible for large n	Yes	Good for explaining optimization
3. Bottom-Up DP (Tabulation)	O(n^2)	O(n^2)	No	Yes	Preferred for coding
4. Space Optimized Bottom-Up DP	O(n^2)	O(n)	No	Yes, with extra bookkeeping	Mention or code if asked for optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly during interviews.

How to Present

Clarify problem constraints and examples.Explain brute force recursion to show problem structure.Introduce memoization to optimize overlapping subproblems.Present bottom-up DP for iterative clarity.Mention space optimization as an advanced improvement.Code the bottom-up or space-optimized solution.Test with edge cases and discuss complexity.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Understanding of DP concepts, ability to optimize naive solutions, clarity in explaining tradeoffs, and coding correctness.

Common Follow-ups

• What if the matrix is very large? → Use space optimization.
• Can you reconstruct the path? → Store parent pointers during DP.
• What if moves can be to any column? → Different DP or prefix min optimization.
• What if negative cycles or infinite loops? → Not applicable here due to problem constraints.

💡 These follow-ups test your ability to adapt and extend your solution beyond the base problem.

🔍

Pattern Recognition

When to Use

1) Problem involves grid or matrix input; 2) Need to find min/max path sum; 3) Movement restricted to adjacent columns in next row; 4) Overlapping subproblems with optimal substructure.

Signature Phrases

'minimum sum of any falling path''choose one element from each row with adjacent column constraint'

NOT This Pattern When

Problems without adjacency constraints or with arbitrary jumps are different patterns.

Similar Problems

Triangle - similar DP on grid with path sumsMinimum Path Sum - simpler grid DP without adjacency constraints

Practice

1. Identify the bug in the following code snippet for minimum score triangulation of a polygon:

medium

A. Line missing dp[i][j] = float('inf') before minimization

B. Line initializing dp array with zeros

C. Loop boundaries for k from i+1 to j-1

D. Return statement returning dp[0][n-1]

Solution

1. Step 1: Check dp initialization inside loops

   dp[i][j] must be set to infinity before checking for minimal cost; otherwise, dp[i][j] starts at 0 and may never update correctly.

2. Step 2: Confirm other lines are correct

   dp array initialization, loop boundaries, and return statement are correct and standard.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without dp[i][j] = float('inf'), minimal cost calculation is incorrect [OK]

Hint: Always initialize dp[i][j] before minimization [OK]

Common Mistakes:

• Forgetting dp initialization
• Off-by-one in loops
• Mixing indices i,j,k

2. The following code attempts to solve the Triangle minimum path sum problem using bottom-up DP. Identify the line that contains a subtle bug causing incorrect results on some inputs.

medium

A. for i in range(len(triangle) - 2, -1, -1):

B. dp[j] = triangle[i][j] + min(dp[j + 1], dp[j])

C. dp = triangle[-1][:]

D. return dp[0]

Solution

1. Step 1: Examine dp update line

   The original code has dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]). The buggy code swaps the min arguments to min(dp[j + 1], dp[j]) which is harmless since min is commutative.

2. Step 2: Check for index out of bounds risk

   Accessing dp[j + 1] is safe because dp length is one more than current row length, so no out-of-bounds here.

3. Step 3: Identify subtle bug

   The subtle bug is that dp is updated in place from left to right, which can cause dp[j + 1] to be already updated when used in min, leading to incorrect results.

4. Step 4: Explanation of bug

   Because dp is updated from left to right, dp[j + 1] may have been updated in the current iteration, so min(dp[j], dp[j + 1]) uses a mixed state of dp values.

5. Step 5: Correct fix

   To fix, update dp from right to left so dp[j + 1] is not yet updated when used.

6. Final Answer:

   Option B -> Option B

7. Quick Check:

   Updating dp in wrong order causes subtle bugs [OK]

Hint: Bug usually in dp update line with min or indexing [OK]

Common Mistakes:

• Swapping min arguments (harmless but suspicious)
• Index out of bounds on dp[j+1]
• Updating dp in wrong order causing overwritten values

3. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the Unique Paths problem on an m x n grid?

medium

A. O(m^2 * n^2)

B. O(m + n)

C. O(m * n * min(m, n))

D. O(m * n)

Solution

1. Step 1: Identify loops in the code

   The solution uses two nested loops: outer loop runs m-1 times, inner loop runs n-1 times.

2. Step 2: Calculate total operations

   Total operations ≈ (m-1) * (n-1) -> O(m * n). No extra hidden loops or recursion stack.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Nested loops over m and n -> O(m*n) [OK]

Hint: Nested loops over m and n -> O(m*n) [OK]

Common Mistakes:

• Confusing with recursion exponential time
• Forgetting loops multiply complexity

4. What is the time complexity of the optimal interval DP solution for Zuma Game (Min Moves to Clear) with board length n and hand size m, considering the state space and transitions?

medium

A. O(n^4 * m^5)

B. O(n^2 * m^3)

C. O(n^3 * m^4)

D. O(5^(n+m))

Solution

1. Step 1: Identify DP state dimensions

   The DP state depends on intervals of the board (O(n^2)) and hand counts (up to 5 colors, each up to m), leading to O(n^3 * m^4) states due to interval splits and hand count combinations.

2. Step 2: Analyze transitions and recursion

   Each state considers splits and insertions, adding an extra factor of n and m, resulting in O(n^3 * m^4) time complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Complexity matches known analysis for interval DP with hand states [OK]

Hint: Interval splits and hand states multiply complexity [OK]

Common Mistakes:

• Confusing n^2 intervals with n^3 due to splits
• Ignoring hand state dimension leading to underestimation
• Mistaking brute force complexity for DP complexity

5. Suppose the Cherry Pickup problem is modified so that players can revisit cells multiple times (i.e., cycles allowed), and cherries are replenished after being picked (can be collected multiple times). Which of the following algorithmic changes correctly adapts the solution to this variant?

hard

A. Use the same 3D DP with memoization but remove the check that prevents revisiting cells.

B. Apply a greedy approach that always moves players to the next cell with the highest cherry count.

C. Use a 4D DP tracking both players' full positions and number of visits per cell to avoid double counting.

D. Switch to a shortest path algorithm like Dijkstra on a state graph representing both players' positions and steps, allowing cycles.

Solution

1. Step 1: Understand the impact of allowing revisits and replenished cherries

   Cycles and replenished cherries mean the problem is no longer acyclic and DP assumptions break down.

2. Step 2: Identify suitable algorithm

   Modeling the problem as a shortest path on a state graph with both players' positions and steps allows handling cycles and repeated cherry collection correctly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP fails with cycles; shortest path algorithms handle repeated states [OK]

Hint: Cycles break DP; use graph shortest path [OK]

Common Mistakes:

• Removing DP constraints without changing algorithm
• Adding dimensions to DP without handling cycles
• Using greedy which ignores global optimality