Skip to content

1289. Minimum Falling Path Sum II 👍

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  int minFallingPathSum(vector<vector<int>>& grid) {
    const int n = grid.size();

    for (int i = 1; i < n; ++i) {
      const auto twoMinNumAndIndexs = getTwoMinNumAndIndexs(grid[i - 1]);
      const auto& [firstMinNum, firstMinIndex] = twoMinNumAndIndexs[0];
      const auto& [secondMinNum, _] = twoMinNumAndIndexs[1];
      for (int j = 0; j < n; ++j)
        if (j == firstMinIndex)
          grid[i][j] += secondMinNum;
        else
          grid[i][j] += firstMinNum;
    }

    return *min_element(begin(grid.back()), end(grid.back()));
  }

 private:
  vector<pair<int, int>> getTwoMinNumAndIndexs(const vector<int>& A) {
    vector<pair<int, int>> numAndIndexs;

    for (int i = 0; i < A.size(); ++i)
      numAndIndexs.emplace_back(A[i], i);

    sort(begin(numAndIndexs), end(numAndIndexs));
    return {numAndIndexs[0], numAndIndexs[1]};
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  public int minFallingPathSum(int[][] grid) {
    final int n = grid.length;

    for (int i = 1; i < n; ++i) {
      var twoMinNumAndIndexs = getTwoMinNumAndIndexs(grid[i - 1]);
      final int firstMinNum = twoMinNumAndIndexs[0].getKey();
      final int firstMinIndex = twoMinNumAndIndexs[0].getValue();
      final int secondMinNum = twoMinNumAndIndexs[1].getKey();
      for (int j = 0; j < n; ++j)
        if (j == firstMinIndex)
          grid[i][j] += secondMinNum;
        else
          grid[i][j] += firstMinNum;
    }

    return Arrays.stream(grid[n - 1]).min().getAsInt();
  }

  private Pair<Integer, Integer>[] getTwoMinNumAndIndexs(int[] A) {
    List<Pair<Integer, Integer>> numAndIndexs = new ArrayList<>();

    for (int i = 0; i < A.length; ++i)
      numAndIndexs.add(new Pair<>(A[i], i));

    Collections.sort(numAndIndexs, (a, b) -> a.getKey() - b.getKey());
    return new Pair[] {numAndIndexs.get(0), numAndIndexs.get(1)};
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def minFallingPathSum(self, grid: List[List[int]]) -> int:
    n = len(grid)

    for i in range(1, n):
      (firstMinNum, firstMinIndex), (secondMinNum, _) = sorted(
          {(a, i) for i, a in enumerate(grid[i - 1])})[:2]
      for j in range(n):
        if j == firstMinIndex:
          grid[i][j] += secondMinNum
        else:
          grid[i][j] += firstMinNum

    return min(grid[-1])