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:
- If there is an obstacle in a lane, set the number of side jumps needed to reach that lane to infinity (
kInf
). - 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}