Leetcode 1824. Minimum Sideway Jumps Solution

Problem

In this problem, there is a 3 lane road of length n that consists of n + 1 points labeled from 0 to n. A frog starts at point 0 in the second lane and wants to jump to point n. There could be obstacles along the way, which are described by an array obstacles of length n + 1. For each index i, obstacles[i] describes which lane has an obstacle at the point i (ranging from 0 to 3). If obstacles[i] is 0, there are no obstacles at point i. There will be at most one obstacle in the 3 lanes at each point.

The frog can only travel from point i to point i + 1 on the same lane if there is not an obstacle on the lane at point i + 1. To avoid obstacles, the frog can also perform a side jump to jump to another lane (even if they are not adjacent) at the same point if there is no obstacle on the new lane.

The goal is to return the minimum number of side jumps the frog needs to reach any lane at point n starting from lane 2 at point 0.

Approach

The solution for this problem uses a dynamic programming approach. The main idea is to calculate the minimum number of side jumps to reach each lane at each point.

We first create a vector dp, which contains the minimum number of side jumps needed to reach each lane. Initialize the dp vector with the values kInf, 1, 0, 1, which represent the initial state of the frog (lane 2 at point 0).

For each obstacle, we update the dp vector in the following way:

1. If there is an obstacle in a lane, set the number of side jumps needed to reach that lane to infinity (kInf).
2. For each lane without an obstacle (i): For each other lane (j): Calculate the minimum number of side jumps needed to reach lane i from lane j. Update the dp vector accordingly.

After updating the dp vector for all obstacles, the minimum number of side jumps needed to reach any lane at point n will be the minimum value in the dp vector.

Let's walk through an example with obstacles [0,1,2,3,0].

1Input: obstacles = [0,1,2,3,0]
2At point 0: No side jumps needed.
3At point 1: Obstacle in lane 1, update dp to [kInf, kInf, 0, 1]
4At point 2: Obstacle in lane 2, update dp to [kInf, kInf, kInf, 1]
5At point 3: Obstacle in lane 3, update dp to [kInf, kInf, kInf, kInf]
6At point 4: No obstacle, update dp to [kInf, 2, 1, 2]
7
8Output: 2 (The optimal solution consists of two side jumps)

Solution

1class Solution {
2 public:
3  int minSideJumps(vector<int>& obstacles) {
4    constexpr int kInf = 1e6;
5
6    // dp[i] := min jump to reach lane i
7    vector<int> dp{kInf, 1, 0, 1};
8
9    for (const int obstacle : obstacles) {
10      if (obstacle > 0)
11        dp[obstacle] = kInf;
12      for (int i = 1; i <= 3; ++i)  // Current
13        if (i != obstacle)
14          for (int j = 1; j <= 3; ++j)  // Prev
15            dp[i] = min({dp[i], dp[j] + (i == j ? 0 : 1)});
16    }
17
18    return *min_element(begin(dp), end(dp));
19  }
20};
21```### Python Solution
22
23```python
24class Solution:
25    def minSideJumps(self, obstacles: List[int]) -> int:
26        kInf = int(1e6)
27        dp = [kInf, 1, 0, 1]  # dp[i]: min jump to reach lane i
28        
29        for obstacle in obstacles:
30            if obstacle > 0:
31                dp[obstacle] = kInf
32            for i in range(1, 4):  # Current
33                if i != obstacle:
34                    for j in range(1, 4):  # Prev
35                        dp[i] = min(dp[i], dp[j] + (0 if i == j else 1))
36                        
37        return min(dp)

JavaScript Solution

1class Solution {
2  minSideJumps(obstacles) {
3    const kInf = 1e6;
4    
5    // dp[i]: min jump to reach lane i
6    let dp = [kInf, 1, 0, 1];
7
8    obstacles.forEach(obstacle => {
9      if (obstacle > 0)
10        dp[obstacle] = kInf;
11      for (let i = 1; i <= 3; i++) { // Current
12        if (i !== obstacle) {
13          for (let j = 1; j <= 3; j++) { // Prev
14            dp[i] = Math.min(dp[i], dp[j] + (i === j ? 0 : 1));
15          }
16        }
17      }
18    });
19
20    return Math.min(...dp);
21  }
22}

Java Solution

1class Solution {
2    public int minSideJumps(int[] obstacles) {
3        int kInf = (int) 1e6;
4        
5        // dp[i]: min jump to reach lane i
6        int[] dp = {kInf, 1, 0, 1};
7        
8        for (int obstacle : obstacles) {
9            if (obstacle > 0) {
10                dp[obstacle] = kInf;
11            }
12            for (int i = 1; i <= 3; i++) { // Current
13                if (i != obstacle) {
14                    for (int j = 1; j <= 3; j++) { // Prev
15                        dp[i] = Math.min(dp[i], dp[j] + (i == j ? 0 : 1));
16                    }
17                }
18            }
19        }
20
21        return Math.min(dp[1], Math.min(dp[2], dp[3]));
22    }
23}