1289. Minimum Falling Path Sum II LeetCode Solution
In this guide, you will get 1289. Minimum Falling Path Sum II LeetCode Solution with the best time and space complexity. The solution to Minimum Falling Path Sum II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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
Complexity Analysis
Time Complexity: O(mn)
Space Complexity: O(mn)
1289. Minimum Falling Path Sum II LeetCode Solution in C++
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]};
}
}; /* code provided by PROGIEZ */
1289. Minimum Falling Path Sum II LeetCode Solution in Java
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.comparing(Pair::getKey));
return new Pair[] {numAndIndexes.get(0), numAndIndexes.get(1)};
}
} // code provided by PROGIEZ
1289. Minimum Falling Path Sum II LeetCode Solution in Python
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]) # code by PROGIEZ
