Minimum Falling Path Sum LeetCode solution in JavaScript

1
//recursion
2

3
var minFallingPathSum = function (matrix) {
4
  let n = matrix.length;
5

6
  let ans = Number.MAX_VALUE;
7
  for (let j = 0; j < n; j++) {
8
    ans = Math.min(ans, solve(n - 1, j, n, matrix));
9
  }
10
  return ans;
11
};
12

13
function solve(i, j, n, arr) {
14
  if (j < 0 || j >= n) return Number.MAX_VALUE;
15
  if (i == 0) return arr[0][j];
16

17
  let s = arr[i][j] + solve(i - 1, j, n, arr);
18
  let ld = arr[i][j] + solve(i - 1, j - 1, n, arr);
19
  let rd = arr[i][j] + solve(i - 1, j + 1, n, arr);
20

21
  return Math.min(s, Math.min(ld, rd));
22
}
23

24
// recursion to memoization
25

26
var minFallingPathSum = function (matrix) {
27
  let n = matrix.length;
28

29
  // create a dp array to store the calculated value.
30
  let dp = new Array(n);
31
  for (let i = 0; i < n; i++) {
32
    dp[i] = new Array(n);
33
  }
34

35
  let ans = Number.MAX_VALUE;
36
  for (let j = 0; j < n; j++) {
37
    //pass dp into the recursive function.
38
    ans = Math.min(ans, solve(n - 1, j, n, matrix, dp));
39
  }
40
  return ans;
41
};
42

43
function solve(i, j, n, arr, dp) {
44
  if (j < 0 || j >= n) return Number.MAX_VALUE;
45
  if (i == 0) return arr[0][j];
46

47
  // before calculating any further recursive call check if it has been already calculated or not.
48
  if (dp[i][j] != undefined) return dp[i][j];
49

50
  let s = arr[i][j] + solve(i - 1, j, n, arr, dp);
51
  let ld = arr[i][j] + solve(i - 1, j - 1, n, arr, dp);
52
  let rd = arr[i][j] + solve(i - 1, j + 1, n, arr, dp);
53

54
  // in last store the calculated value in dp array.
55
  return (dp[i][j] = Math.min(s, Math.min(ld, rd)));
56
}
57

58
// tabulation
59

60
var minFallingPathSum = function (matrix) {
61
  let n = matrix.length;
62

63
  let dp = new Array(n);
64
  for (let i = 0; i < n; i++) {
65
    dp[i] = new Array(n);
66
  }
67

68
  // base case - here any one from the first row of matrix array can be a base case
69
  for (let j = 0; j < n; j++) {
70
    dp[0][j] = matrix[0][j];
71
  }
72

73
  // go from next row and calculate value for each column
74
  for (let i = 1; i < n; i++) {
75
    for (let j = 0; j < n; j++) {
76
      let s = matrix[i][j] + dp[i - 1][j];
77
      let ld = matrix[i][j];
78
      if (j > 0)
79
        ld += dp[i - 1][j - 1]; // condition to restrict getting out of bound value from matrix.
80
      else ld = Number.MAX_VALUE;
81

82
      let rd = matrix[i][j];
83
      if (j < n - 1) rd += dp[i - 1][j + 1];
84
      else rd = Number.MAX_VALUE;
85

86
      dp[i][j] = Math.min(s, Math.min(ld, rd));
87
    }
88
  }
89

90
  let maxi = dp[n - 1][0];
91
  for (let j = 1; j < n; j++) {
92
    maxi = Math.min(maxi, dp[n - 1][j]);
93
  }
94
  return maxi;
95
};
96

97
// further space optimized
98

99
var minFallingPathSum = function (matrix) {
100
  let n = matrix.length;
101

102
  // create a dp array to store the calculated value.
103
  let prev = new Array(n);
104

105
  for (let j = 0; j < n; j++) {
106
    prev[j] = matrix[0][j];
107
  }
108

109
  for (let i = 1; i < n; i++) {
110
    let cur = new Array(n);
111
    for (let j = 0; j < n; j++) {
112
      let s = matrix[i][j] + prev[j];
113
      let ld = matrix[i][j];
114
      if (j > 0) ld += prev[j - 1];
115
      else ld = Number.MAX_VALUE;
116

117
      let rd = matrix[i][j];
118
      if (j < n - 1) rd += prev[j + 1];
119
      else rd = Number.MAX_VALUE;
120

121
      cur[j] = Math.min(s, Math.min(ld, rd));
122
    }
123
    prev = cur;
124
  }
125

126
  let maxi = prev[0];
127
  for (let j = 1; j < n; j++) {
128
    maxi = Math.min(maxi, prev[j]);
129
  }
130
  return maxi;
131
};