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. 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 bottom-up DP code for the Strange Printer problem. What is the final returned value when the input string is "aba"?

easy

A. 3

B. 4

C. 1

D. 2

Solution

1. Step 1: Compress input string "aba"

   Compression does not change string since no consecutive duplicates: s = "aba", n=3.

2. Step 2: Trace dp table filling

   Base cases: dp[0][0]=1, dp[1][1]=1, dp[2][2]=1. For length=2: - dp[0][1]: dp[0][0]+1=2, s[0]!=s[1], so dp[0][1]=2 - dp[1][2]: dp[1][1]+1=2, s[1]!=s[2], so dp[1][2]=2 For length=3: - dp[0][2]: dp[0][1]+1=3 Check k=0: s[0]==s[2] ('a'=='a'), dp[0][0]+dp[1][1]=1+1=2 < 3, so dp[0][2]=2

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Output matches known minimal turns for "aba" [OK]

Hint: Check dp merging when s[k] == s[j] reduces turns [OK]

Common Mistakes:

• Forgetting to merge intervals when characters match

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. You need to find the number of distinct ways to move from the top-left corner to the bottom-right corner of an m x n grid, moving only down or right at each step. Which algorithmic approach guarantees an efficient and optimal solution for this problem?

easy

A. Pure brute force recursion exploring all possible paths without memoization

B. Greedy algorithm that always moves towards the direction with fewer remaining steps

C. Dynamic Programming that builds solutions from smaller subproblems using a grid-based state representation

D. Divide and conquer by splitting the grid into quadrants and combining results

Solution

1. Step 1: Understand problem constraints

   The problem requires counting all unique paths with only right and down moves, which naturally forms overlapping subproblems.

2. Step 2: Identify suitable approach

   Dynamic Programming efficiently solves overlapping subproblems by storing intermediate results, unlike greedy or pure recursion which are either incorrect or inefficient.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP uses subproblem reuse -> optimal and efficient [OK]

Hint: Counting paths with overlapping subproblems -> DP [OK]

Common Mistakes:

• Thinking greedy can find all paths
• Using pure recursion without memoization

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