Minimum Falling Path Sum II - Practice Coding Problems

Minimum Falling Path Sum II - Problem

Imagine you're a treasure hunter navigating through a dangerous multi-level dungeon! 🏴‍☠️ You have an n x n grid where each cell contains a treasure value (which could be negative - representing traps!). Your goal is to collect treasures by moving from the top row to the bottom row, picking exactly one treasure from each level. Here's the catch: you cannot pick treasures directly below each other - you must shift to a different column in each move. This is called a "falling path with non-zero shifts." Your mission: Find the path that gives you the minimum sum of treasures collected. Example: If you have a 3x3 grid:
[[1,2,3], [4,5,6], [7,8,9]]
One valid path could be: pick 1 (row 0, col 0) → pick 5 (row 1, col 1) → pick 9 (row 2, col 2), giving sum = 15.

Input & Output

example_1.py — Basic 3x3 Grid

$ Input: grid = [[1,2,3],[4,5,6],[7,8,9]]

› Output: 13

💡 Note: The minimum falling path is [1,5,9] → but this violates the non-zero shift constraint. Valid paths include [1,4,8]=13, [1,6,7]=14, [2,4,9]=15, [2,6,7]=15, [3,4,8]=15, [3,5,7]=15. The minimum is 13.

example_2.py — Single Element

$ Input: grid = [[7]]

› Output: 7

💡 Note: With only one element, there's no choice but to take that element. No shifts are needed since there's only one row.

example_3.py — Negative Values

$ Input: grid = [[2,1,3],[6,5,4],[7,8,9]]

› Output: 13

💡 Note: Optimal path: [1,6,9] = 16? No, that's same column! Try [1,4,7] = 12? No, positions are [0,1], [2,2], [2,0] - invalid. Valid: [1,6,7]=14, [1,4,8]=13. Minimum is 13.

Constraints

n == grid.length == grid[i].length
1 ≤ n ≤ 200
-99 ≤ grid[i][j] ≤ 99
Non-zero shifts required - cannot pick elements in same column from adjacent rows

Visualization

Tap to expand

Understanding the Visualization

Track Best Options

For each level, identify the minimum and second minimum treasure values

Smart Path Choice

When moving to next level, choose the best available option (avoiding same column)

Accumulate Optimally

Build up the best path by always making locally optimal choices

Final Treasure Count

The minimum value in the last row gives us the optimal treasure sum

Key Takeaway

🎯 Key Insight: By tracking only the minimum and second minimum values from each row, we can make optimal decisions in constant time per cell, achieving the best possible time complexity of O(n²) while using minimal space.

Asked in

G Google 28 a Amazon 22 f Meta 15 ⊞ Microsoft 12

The optimal solution uses dynamic programming with min/second min tracking. Key insight: for each cell, we only need the minimum value from the previous row that's in a different column. If our column matches the minimum's column, use the second minimum instead. This achieves O(n²) time and O(1) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming (Bottom-Up)	O(n³)	O(n²)	Build up optimal solutions row by row using tabulation
Optimized DP (Space Optimized)	O(n²)	O(1)	Track only first and second minimum from previous row for optimal solution
Brute Force (Recursive Exploration)	O(n^(n+1))	O(n)	Try every possible path combination using recursion

Dynamic Programming (Bottom-Up) — Algorithm Steps

Initialize DP table with the first row values
For each subsequent row, calculate minimum path sum for each cell
For each cell, consider all valid previous positions (different columns)
Take minimum sum from all valid previous positions
Return minimum value from the last row

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set up DP table with first row values

Fill Table

Calculate minimum path for each cell

Consider Paths

Check all valid previous positions

Final Result

Take minimum from last row

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int minFallingPathSum(int** grid, int n) {
    if (n == 1) return grid[0][0];
    
    // Allocate DP table
    int** dp = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        dp[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            dp[i][j] = INT_MAX;
        }
    }
    
    // Initialize first row
    for (int j = 0; j < n; j++) {
        dp[0][j] = grid[0][j];
    }
    
    // Fill DP table
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int prevJ = 0; prevJ < n; prevJ++) {
                if (prevJ != j) {
                    int sum = dp[i-1][prevJ] + grid[i][j];
                    if (sum < dp[i][j]) {
                        dp[i][j] = sum;
                    }
                }
            }
        }
    }
    
    int result = INT_MAX;
    for (int j = 0; j < n; j++) {
        if (dp[n-1][j] < result) {
            result = dp[n-1][j];
        }
    }
    
    // Free memory
    for (int i = 0; i < n; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return result;
}

int main() {
    int n = 3;
    int** grid = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        grid[i] = (int*)malloc(n * sizeof(int));
    }
    
    int data[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            grid[i][j] = data[i][j];
        }
    }
    
    printf("%d\n", minFallingPathSum(grid, n));
    
    for (int i = 0; i < n; i++) {
        free(grid[i]);
    }
    free(grid);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

For each of n² cells, we check n possible previous positions

⚠ Quadratic Growth

Space Complexity

O(n²)

DP table requires n² space to store intermediate results

⚠ Quadratic Space

38.4K Views

Medium-High Frequency

~25 min Avg. Time

1.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming (Bottom-Up) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler