Minimum Falling Path Sum II - LeetCode Daily Challenge

Problem Statement

Given an n x n integer matrix grid, return the minimum sum of a falling path with non-zero shifts.

A falling path with non-zero shifts is a choice of exactly one element from each row of grid such that no two elements chosen in adjacent rows are in the same column.

Input: grid = [[1,2,3],[4,5,6],[7,8,9]]
Output: 13
Explanation: 
The possible falling paths are:
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
The falling path with the smallest sum is [1,5,7], so the answer is 13.

Example 2

Input: grid = [[7]]
Output: 7

Try here before watching the video.

Video Solution

Java Code

class Solution {

    private int getMinSum(int[][] grid, int row, int prevCol, int[][] dp) {
        
        if(row == grid.length) return 0;

        if(dp[row][prevCol] != Integer.MAX_VALUE) return dp[row][prevCol];

        int minSum = Integer.MAX_VALUE;
        for(int i = 0; i < grid[0].length; i++) {
            if(i == prevCol) continue;
            minSum = Math.min(minSum, grid[row][i] + getMinSum(grid, row + 1, i, dp));
        }
        return dp[row][prevCol] = minSum;
    }

    public int minFallingPathSum(int[][] grid) {

        int[][] dp = new int[grid.length][grid[0].length];
        for(int i = 0; i < grid.length; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }

        int minSum = Integer.MAX_VALUE;
        for(int i = 0; i < grid[0].length; i++) {
            minSum = Math.min(minSum, grid[0][i] + getMinSum(grid, 1, i, dp));
        }

        return minSum;
    }
}

C++ Code

#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

class Solution {
private:
    int getMinSum(vector<vector<int>>& grid, int row, int prevCol, vector<vector<int>>& dp) {
        if (row == grid.size()) return 0;
        if (dp[row][prevCol] != numeric_limits<int>::max()) return dp[row][prevCol];

        int minSum = numeric_limits<int>::max();
        for (int i = 0; i < grid[0].size(); i++) {
            if (i == prevCol) continue;
            minSum = min(minSum, grid[row][i] + getMinSum(grid, row + 1, i, dp));
        }
        return dp[row][prevCol] = minSum;
    }

public:
    int minFallingPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        
        vector<vector<int>> dp(n, vector<int>(m, numeric_limits<int>::max()));

        int minSum = numeric_limits<int>::max();
        for (int i = 0; i < m; i++) {
            minSum = min(minSum, grid[0][i] + getMinSum(grid, 1, i, dp));
        }

        return minSum;
    }
};

Python Code

from typing import List

class Solution:
    def getMinSum(self, grid: List[List[int]], row: int, prevCol: int, dp: List[List[int]]) -> int:
        if row == len(grid):
            return 0
        if dp[row][prevCol] != float('inf'):
            return dp[row][prevCol]
        
        minSum = float('inf')
        for i in range(len(grid[0])):
            if i == prevCol:
                continue
            minSum = min(minSum, grid[row][i] + self.getMinSum(grid, row + 1, i, dp))
        
        dp[row][prevCol] = minSum
        return dp[row][prevCol]

    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        
        dp = [[float('inf')] * m for _ in range(n)]

        minSum = float('inf')
        for i in range(m):
            minSum = min(minSum, grid[0][i] + self.getMinSum(grid, 1, i, dp))
        
        return minSum

Go Code

func getMinSum(grid [][]int, row, prevCol int, dp [][]int) int {
    if row == len(grid) {
        return 0
    }
    if dp[row][prevCol] != math.MaxInt32 {
        return dp[row][prevCol]
    }

    minSum := math.MaxInt32
    for i := 0; i < len(grid[0]); i++ {
        if i == prevCol {
            continue
        }
        minSum = min(minSum, grid[row][i] + getMinSum(grid, row+1, i, dp))
    }
    dp[row][prevCol] = minSum
    return dp[row][prevCol]
}

func minFallingPathSum(grid [][]int) int {
    n := len(grid)
    m := len(grid[0])

    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, m)
        for j := 0; j < m; j++ {
            dp[i][j] = math.MaxInt32
        }
    }

    minSum := math.MaxInt32
    for i := 0; i < m; i++ {
        minSum = min(minSum, grid[0][i] + getMinSum(grid, 1, i, dp))
    }

    return minSum
}

Javascript Code

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minFallingPathSum = function(grid) {
    const n = grid.length;
    const m = grid[0].length;
    
    const dp = Array.from({ length: n }, () => Array(m).fill(Number.MAX_SAFE_INTEGER));

    function getMinSum(row, prevCol) {
        if (row === n) return 0;
        if (dp[row][prevCol] !== Number.MAX_SAFE_INTEGER) return dp[row][prevCol];

        let minSum = Number.MAX_SAFE_INTEGER;
        for (let i = 0; i < m; i++) {
            if (i === prevCol) continue;
            minSum = Math.min(minSum, grid[row][i] + getMinSum(row + 1, i));
        }
        dp[row][prevCol] = minSum;
        return dp[row][prevCol];
    }

    let minSum = Number.MAX_SAFE_INTEGER;
    for (let i = 0; i < m; i++) {
        minSum = Math.min(minSum, grid[0][i] + getMinSum(1, i));
    }

    return minSum;
};