DP Solution Without Modifying Input — 24 Lines — O(n^2) / O(n)

Problem: https://leetcode.com/problems/minimum-falling-path-sum-ii/

Solution: https://leetcode.com/problems/minimum-falling-path-sum-ii/solutions/5081680/dp-solution-without-modifying-input-24-lines-o-n-2-o-n/

Algorithm

1. Find smallest two cells of first row.
2. Loop through remaining rows, rows i+1 to len-1.

• For each cell, if it’s not the same col index as the prev smallest, add smallest prev cell, low, else, add the second smallest prev, hi.
• Find next two lowest cells for each next row after adding lowest cells from prev row

3. Return last lowest cell

Complexity

• Time complexity: O(n2)
• Space complexity: O(n)

The lowest values of the prev row are stored in three properties, low, i, hi.

rowValues = {
  low // lowest value (from prev row)
  hi // second lowest value (from prev row
  i // lowest value's index (from prev row)
}

The values of each row are also temporarily stored in an identically-structured object.

const minFallingPathSum = (() => {
    "use strict";
    const findLeastTwo = (row, prev) => {
        const rowValues = { low: Infinity, hi: Infinity };
        for (let i = 0; i < row.length; i++) {
            let cell = row[i];
            if (prev.i !== -1) {
                cell += i === prev.i ? prev.hi : prev.low;
            }
            if (cell < rowValues.low) { 
                 Object.assign(rowValues, {hi:rowValues.low, low:cell, i:i});
            } else if (cell < rowValues.hi) {
                rowValues.hi = cell;
            }
        }
        Object.assign(prev, rowValues);
    };

    return grid => {
        const prev = { low: 0, hi: 0, i: -1 };
        for (const row of grid) findLeastTwo(row, prev);
        return prev.low;
    };
})();