Today I have done leetcode's April LeetCoding Challenge with cpp.

April LeetCoding Challenge 26

Description

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.

Example 1:

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

Constraints:

• n == grid.length == grid[i].length
• 1 <= n <= 200
• -99 <= grid[i][j] <= 99

Solution

class Solution {
public:
  int minFallingPathSum(vector<vector<int>>& grid) {
    vector<int> minimum = {0, 0};
    int minIndex = -1;
    int cols = grid.front().size();
    for(const auto &row : grid) {
      // cout << minimum[0] << ' ' << minimum[1] << ' ' << minIndex << endl;
      int newIndex = -1;
      vector<int> newMinimum = {INT_MAX, INT_MAX};
      for(int j = 0; j < cols; ++j) {
        int mmin = row[j] + minimum[j == minIndex];
        if(mmin < newMinimum[0]) {
          newMinimum[1] = newMinimum[0];
          newMinimum[0] = mmin;
          newIndex = j;
        } else if(mmin < newMinimum[1]) {
          newMinimum[1] = mmin;
        }
      }
      swap(minimum, newMinimum);
      minIndex = newIndex;
    }
    return minimum[0];
  }
};