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
class Solution {
 public:
  int minFallingPathSum(vector<vector<int>>& grid) {
    const int n = grid.size();

    for (int i = 1; i < n; ++i) {
      const vector<pair<int, int>> 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 ranges::min(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);
    ranges::sort(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
class Solution {
  public int minFallingPathSum(int[][] grid) {
    final int n = grid.length;

    for (int i = 1; i < n; ++i) {
      Pair<Integer, Integer>[] twoMinNumAndIndexes = getTwoMinNumAndIndexes(grid[i - 1]);
      final int firstMinNum = twoMinNumAndIndexes[0].getKey();
      final int firstMinIndex = twoMinNumAndIndexes[0].getValue();
      final int secondMinNum = twoMinNumAndIndexes[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>[] getTwoMinNumAndIndexes(int[] arr) {
    List<Pair<Integer, Integer>> numAndIndexes = new ArrayList<>();
    for (int i = 0; i < arr.length; ++i)
      numAndIndexes.add(new Pair<>(arr[i], i));
    Collections.sort(numAndIndexes, Comparator.comparingInt(Pair::getKey));
    return new Pair[] {numAndIndexes.get(0), numAndIndexes.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])