DEV Community

Karleb
Karleb

Posted on

#1289. Minimum Falling Path Sum II

https://leetcode.com/problems/minimum-falling-path-sum-ii/description/?envType=daily-question&envId=2024-04-26

var minFallingPathSum = function(grid) {
    const minFallingPathSumHelper = function(row, grid) {
        if (row === grid.length) {
            return new Triplet(0, 0, 0);
        }

        const nextRowTriplet = minFallingPathSumHelper(row + 1, grid);
        let currentTriplet = new Triplet(Number.MAX_SAFE_INTEGER, Number.MAX_SAFE_INTEGER, -1);

        for (let col = 0; col < grid[0].length; col++) {
            const value = grid[row][col] + (
                col !== nextRowTriplet.minSumIndex ? nextRowTriplet.minSum : nextRowTriplet.secondMinSum
            );
            if (value <= currentTriplet.minSum) {
                currentTriplet.secondMinSum = currentTriplet.minSum;
                currentTriplet.minSum = value;
                currentTriplet.minSumIndex = col;
            } else if (value < currentTriplet.secondMinSum) {
                currentTriplet.secondMinSum = value;
            }
        }

        return currentTriplet;
    };

    const n = grid.length;
    return minFallingPathSumHelper(0, grid).minSum;
};

class Triplet {
    constructor(minSum, secondMinSum, minSumIndex) {
        this.minSum = minSum;
        this.secondMinSum = secondMinSum;
        this.minSumIndex = minSumIndex;
    }
};


Enter fullscreen mode Exit fullscreen mode

I do not fully understand this solution. It's a hard problem but not so hard. I really love this solution that I got from leetcode.

Top comments (0)