Minimum Sideway Jumps LeetCode solution in JavaScript

1
/**
2
 * @param {number[]} obstacles
3
 * @return {number}
4
 */
5
// var solve = function(obstacles, lane, pos, dp) {
6
//     if (pos === obstacles.length - 1) {
7
//         return 0;
8
//     }
9
//     // Obstacle on next straight position
10
//     if (dp[lane][pos] !== -1) {
11
//         return dp[lane][pos];
12
//     }
13
//     if (obstacles[pos + 1] !== lane) {
14
//         return solve(obstacles, lane, pos + 1, dp);
15
//     } else {
16
//         let ans = Number.MAX_SAFE_INTEGER;
17
//         for (let i = 1; i <= 3; i++) {
18
//             if (i !== lane && obstacles[pos] !== i) {
19
//                 ans = Math.min(ans, 1 + solve(obstacles, i, pos + 1, dp)); // Updated pos here
20
//             }
21
//         }
22
//         dp[lane][pos] = ans;
23
//         return ans;
24
//     }
25
// };
26

27
// var minSideJumps = function(obstacles) {
28
//     let dp = Array.from({ length: 4 }, () => Array(obstacles.length).fill(-1));
29
//     return solve(obstacles, 2, 0, dp);
30
// };
31

32
// var minSideJumps = function(obstacles) {
33
//     let n = obstacles.length;
34
//     let dp = Array.from({ length: 4 }, () => Array(n).fill(Number.MAX_SAFE_INTEGER));
35

36
//     // Initialize the last column of dp to 0
37
//     dp[0][n - 1] = 0;
38
//     dp[1][n - 1] = 0;
39
//     dp[2][n - 1] = 0;
40
//     dp[3][n - 1] = 0;
41

42
//     for (let pos = n - 2; pos >= 0; pos--) {
43
//         for (let lane = 1; lane <= 3; lane++) {
44
//             if (obstacles[pos + 1] !== lane) {
45
//                 dp[lane][pos] = dp[lane][pos + 1];
46
//             } else {
47
//                 let ans = Number.MAX_SAFE_INTEGER;
48
//                 for (let i = 1; i <= 3; i++) {
49
//                     if (i !== lane && obstacles[pos] !== i) {
50
//                         ans = Math.min(ans, 1 + dp[i][pos + 1]);
51
//                     }
52
//                 }
53
//                 dp[lane][pos] = ans;
54
//             }
55
//         }
56
//     }
57

58
//     // Fix the return statement
59
//     return Math.min(dp[2][0], Math.min(1 + dp[1][0], 1 + dp[3][0]));
60
// };
61

62
var minSideJumps = function (obstacles) {
63
  let n = obstacles.length;
64
  let curr = Array(4).fill(Number.MAX_SAFE_INTEGER);
65
  let next = Array(4).fill(0);
66

67
  for (let pos = n - 2; pos >= 0; pos--) {
68
    for (let lane = 1; lane <= 3; lane++) {
69
      if (obstacles[pos + 1] !== lane) {
70
        curr[lane] = next[lane];
71
      } else {
72
        let ans = Number.MAX_SAFE_INTEGER;
73
        for (let i = 1; i <= 3; i++) {
74
          if (i !== lane && obstacles[pos] !== i) {
75
            ans = Math.min(ans, 1 + next[i]);
76
          }
77
        }
78
        curr[lane] = ans;
79
        next = curr;
80
      }
81
    }
82
  }
83
  return Math.min(next[2], Math.min(1 + next[1], 1 + next[0]));
84
};