1289. Minimum Falling Path Sum II

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.

• Time : O(nm)
• Space : O(1)

c++

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        if(n == 1) return grid[0][0];
        pair<int,int> min1 = {0,INT_MAX}, min2 = {0,INT_MAX};
        for(int i = 0; i < n; i++) {
            pair<int,int> nxtmi1 = {INT_MAX,0}, nxtmi2 = {INT_MAX,0};
            for(int j = 0; j < m; j++) {
                pair<int,int> cur = {grid[i][j] + (min1.second != j?min1.first : min2.first), j};
                if(cur.first < nxtmi1.first) {
                    nxtmi2 = nxtmi1;
                    nxtmi1 = cur;
                } else if(cur.first < nxtmi2.first) {
                    nxtmi2 = cur;
                }
            }
            min1 = nxtmi1;
            min2 = nxtmi2;
        }
        return min1.first;
    }
};

• Time : O(nmlogm)
• Space : O(m)

c++

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        if(n == 1) return grid[0][0];

        multiset<int> dp(grid[0].begin(), grid[0].end());
        for(int i = 1; i < n; i++) {
            multiset<int> nxt;
            for(int j = 0; j < m; j++) {
                auto mi = dp.begin();
                if(*mi == grid[i-1][j]) mi = next(mi);
                nxt.insert(grid[i][j] += *mi);
            }
            dp.swap(nxt);
        }
        return *dp.begin();
    }
};