Minimum Falling Path Sum II

hard dp matrix

Problem

Given an n × n integer matrix grid, return the minimum sum of a falling path where any two consecutive elements must come from different columns.

Inputgrid = [[1,2,3],[4,5,6],[7,8,9]]

Output13

A path: 1 → 5 → 7 = 13. Each next cell is in a different column.

grid (JSON, n × n)

def min_falling_path_sum(grid):
    n = len(grid)
    m1, m2, idx1 = 0, 0, -1
    for r in range(n):
        nm1, nm2, nidx = float('inf'), float('inf'), -1
        for c in range(n):
            best = (m2 if c == idx1 else m1) + grid[r][c]
            if best < nm1:
                nm2 = nm1; nm1 = best; nidx = c
            elif best < nm2:
                nm2 = best
        m1, m2, idx1 = nm1, nm2, nidx
    return m1

function minFallingPathSum(grid) {
  const n = grid.length;
  let m1 = 0, m2 = 0, idx1 = -1;
  for (let r = 0; r < n; r++) {
    let nm1 = Infinity, nm2 = Infinity, nidx = -1;
    for (let c = 0; c < n; c++) {
      const best = (c === idx1 ? m2 : m1) + grid[r][c];
      if (best < nm1) { nm2 = nm1; nm1 = best; nidx = c; }
      else if (best < nm2) { nm2 = best; }
    }
    m1 = nm1; m2 = nm2; idx1 = nidx;
  }
  return m1;
}

class Solution {
    public int minFallingPathSum(int[][] grid) {
        int n = grid.length;
        int m1 = 0, m2 = 0, idx1 = -1;
        for (int r = 0; r < n; r++) {
            int nm1 = Integer.MAX_VALUE, nm2 = Integer.MAX_VALUE, nidx = -1;
            for (int c = 0; c < n; c++) {
                int best = (c == idx1 ? m2 : m1) + grid[r][c];
                if (best < nm1) { nm2 = nm1; nm1 = best; nidx = c; }
                else if (best < nm2) { nm2 = best; }
            }
            m1 = nm1; m2 = nm2; idx1 = nidx;
        }
        return m1;
    }
}

int minFallingPathSum(vector<vector<int>>& grid) {
    int n = (int)grid.size();
    int m1 = 0, m2 = 0, idx1 = -1;
    for (int r = 0; r < n; r++) {
        int nm1 = INT_MAX, nm2 = INT_MAX, nidx = -1;
        for (int c = 0; c < n; c++) {
            int best = (c == idx1 ? m2 : m1) + grid[r][c];
            if (best < nm1) { nm2 = nm1; nm1 = best; nidx = c; }
            else if (best < nm2) { nm2 = best; }
        }
        m1 = nm1; m2 = nm2; idx1 = nidx;
    }
    return m1;
}

Explanation

A falling path picks one cell per row, but consecutive cells must be in different columns. A naive DP would, for every cell, scan all columns above except its own — that's slow. The clever trick is realizing you only ever need the two smallest values from the previous row.

Why two? For any cell in column c, the best parent is the row's minimum — unless that minimum sits in column c itself, in which case you must fall back to the row's second smallest. So we carry just m1 (smallest), m2 (second smallest), and idx1 (the column of m1).

For each cell we compute best = (m2 if c == idx1 else m1) + grid[r][c], then update the new row's two smallest as we go. After the row finishes, those become the carried values for the next row.

Example: grid = [[1,2,3],[4,5,6],[7,8,9]]. A valid path is 1 → 5 → 7 (each in a new column) summing to 13, which is the smallest m1 after the last row.

Since each cell does constant work and we keep only a few carried numbers, the time is O(n²) with O(1) extra space.

Time: O(n²) Space: O(1)