Day 29 -Minimum Falling Path Sum II

class Solution {
public int minFallingPathSum(int[][] arr) {
if (arr == null
|| arr.length == 0
|| arr[0].length == 0)
return 0;

int n = arr.length;

int min1, min2, minCol = 0;
for (int i = n - 2; i >= 0; i--) {
min1 = Integer.MAX_VALUE;
min2 = Integer.MAX_VALUE;

for (int j = 0; j < n; j++) {
if (arr[i + 1][j] < min1) {
min2 = min1;
min1 = arr[i + 1][j];
minCol = j;
} else if (arr[i + 1][j] < min2) {
min2 = arr[i + 1][j];
}
}

for (int j = 0; j < n; j++) {
if (j == minCol) arr[i][j] += min2;
else arr[i][j] += min1;
}
}

int result = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
result = Math.min(result, arr[0][i]);
}

return result;
}
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store