Problem Description

You have a road with 3 lanes that spans from point 0 to point n (total of n+1 points). A frog starts at point 0 in lane 2 (middle lane) and wants to reach point n.

The lanes are numbered 1, 2, and 3. Along the road, there may be obstacles blocking certain lanes at specific points. These obstacles are given in an array obstacles where:

• obstacles[i] indicates which lane has an obstacle at point i
• obstacles[i] = 0 means no obstacle at point i
• obstacles[i] = 1, 2, or 3 means there's an obstacle in lane 1, 2, or 3 respectively at point i
• Each point has at most one obstacle (only one lane can be blocked per point)
• Points 0 and n are guaranteed to have no obstacles

The frog can move in two ways:

1. Forward movement: Jump from point i to point i+1 on the same lane (only if there's no obstacle at point i+1 on that lane)
2. Side jump: Jump to a different lane at the same point (only if the target lane has no obstacle at that point)

The goal is to find the minimum number of side jumps needed for the frog to reach point n. The frog can end at any lane at point n.

For example, if the frog is at point 3 in lane 3 and wants to avoid an obstacle, it can side jump to lane 1 or lane 2 at the same point 3 (if those lanes are clear).

Intuition

The key insight is that at each point, we need to track the minimum number of side jumps required to reach each of the three lanes. This naturally leads to a dynamic programming approach.

Think of it this way: as the frog moves forward from point to point, at each position we want to know "what's the minimum cost (side jumps) to be in each lane at this point?"

Starting from point 0, the frog is in lane 2 with 0 side jumps. To be in lane 1 or lane 3 at point 0, it needs 1 side jump. So we initialize with [1, 0, 1] representing the cost for lanes 1, 2, and 3 respectively.

As we move forward to each new point, two scenarios can happen for each lane:

1. If there's an obstacle in a lane: It's impossible to be in that lane, so we set its cost to infinity
2. If the lane is clear: The frog can either:
   • Come from the same lane at the previous point (no additional side jumps)
   • Side jump from another lane at the current point (adds 1 to the minimum cost among all lanes)

The beauty of this approach is that we don't need to track the entire path - we only need to know the minimum cost to reach each lane at the current point. This reduces our state space significantly.

Since we only need information from the current point to calculate the next point, we can optimize space by using just a single array of size 3 instead of a 2D array. We update this array as we process each point, always maintaining the minimum side jumps needed to reach each lane at the current position.

The final answer is simply the minimum value among all three lanes at point n, since the frog can end at any lane.

Learn more about Greedy and Dynamic Programming patterns.

Solution Approach

We implement a dynamic programming solution using a 1D array to track the minimum side jumps needed to reach each lane at the current point.

Initialization:

• Create an array f = [1, 0, 1] representing the initial cost to be in lanes 1, 2, and 3 at point 0
• Lane 2 (index 1) has cost 0 since the frog starts there
• Lanes 1 and 3 (indices 0 and 2) have cost 1 since they require one side jump from the starting position

Processing each point: For each point from 1 to n (using obstacles[1:] to skip point 0):

1. Handle obstacles: If there's an obstacle at the current point in lane j+1 (where j is the 0-indexed lane), set f[j] = inf to indicate this lane is unreachable at this point.

2. Calculate minimum cost with side jump: Find the minimum cost among all reachable lanes and add 1 for a potential side jump: x = min(f) + 1

3. Update costs for clear lanes: For each lane j that doesn't have an obstacle:

   • The frog can either stay in the same lane (cost remains f[j])
   • Or side jump from the cheapest lane (cost becomes x)
   • Take the minimum: f[j] = min(f[j], x)

Key optimization: Instead of using a 2D array f[i][j] to track costs at each point, we use a single array f[j] and update it in place as we move forward. This works because:

• When processing point i, f[j] initially contains the cost from point i-1
• We update f[j] to reflect the cost at point i
• We only need the previous point's information to calculate the current point

Return value: After processing all points, return min(f) - the minimum cost among all three lanes at the final point n.

The time complexity is O(n) where n is the number of points, and the space complexity is O(1) since we only use a fixed-size array of 3 elements.

Example Walkthrough

Let's walk through a small example where obstacles = [0, 1, 2, 3, 0]. This means we have 5 points (0 to 4), and the frog needs to travel from point 0 to point 4.

Initial Setup:

• Point 0: No obstacle (given as 0)
• Point 1: Obstacle in lane 1
• Point 2: Obstacle in lane 2
• Point 3: Obstacle in lane 3
• Point 4: No obstacle (given as 0)

The frog starts at point 0 in lane 2. Our DP array f = [1, 0, 1] represents:

• Lane 1: needs 1 side jump from starting position
• Lane 2: frog is already here (0 jumps)
• Lane 3: needs 1 side jump from starting position

Point 1 (obstacle in lane 1):

1. Mark lane 1 as blocked: f[0] = inf → f = [inf, 0, 1]
2. Find minimum with side jump: x = min(0, 1) + 1 = 1
3. Update clear lanes:
   • Lane 2: min(0, 1) = 0 (stay in lane 2 from point 0)
   • Lane 3: min(1, 1) = 1 (either stay in lane 3 or jump from lane 2)
   Result: f = [inf, 0, 1]

Point 2 (obstacle in lane 2):

1. Mark lane 2 as blocked: f[1] = inf → f = [inf, inf, 1]
2. Find minimum with side jump: x = min(1) + 1 = 2
3. Update clear lanes:
   • Lane 1: min(inf, 2) = 2 (must side jump from lane 3)
   • Lane 3: min(1, 2) = 1 (stay in lane 3)
   Result: f = [2, inf, 1]

Point 3 (obstacle in lane 3):

1. Mark lane 3 as blocked: f[2] = inf → f = [2, inf, inf]
2. Find minimum with side jump: x = min(2) + 1 = 3
3. Update clear lanes:
   • Lane 1: min(2, 3) = 2 (stay in lane 1)
   • Lane 2: min(inf, 3) = 3 (must side jump from lane 1)
   Result: f = [2, 3, inf]

Point 4 (no obstacle):

1. No lanes blocked
2. Find minimum with side jump: x = min(2, 3) + 1 = 3
3. Update all lanes:
   • Lane 1: min(2, 3) = 2 (stay in lane 1)
   • Lane 2: min(3, 3) = 3 (stay in lane 2)
   • Lane 3: min(inf, 3) = 3 (side jump from lane 1 or 2)
   Final result: f = [2, 3, 3]

Answer: min(f) = 2

The optimal path requires 2 side jumps: Start in lane 2 → stay in lane 2 at point 1 → side jump to lane 3 at point 1 → continue in lane 3 to point 2 → side jump to lane 1 at point 2 → continue in lane 1 to point 4.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array obstacles.

The algorithm iterates through the obstacles array once (starting from index 1), performing a constant amount of work for each element. Within each iteration, there are two inner loops that each iterate exactly 3 times (a constant), performing O(1) operations such as comparisons, assignments, and finding the minimum of 3 values. Since the outer loop runs n-1 times and each iteration takes O(1) time, the overall time complexity is O(n).

Space Complexity: O(1)

The algorithm uses only a fixed amount of extra space regardless of the input size. It maintains:

• An array f of size 3 to store the minimum jumps needed to reach each lane
• A variable x to temporarily store the minimum value plus 1
• Loop variables j and v

Since the space used does not grow with the input size n, the space complexity is constant, O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Obstacle Indexing

A frequent mistake is misunderstanding how obstacles are indexed. The obstacles array uses 1-based lane numbering (lanes 1, 2, 3), while the DP array uses 0-based indexing (indices 0, 1, 2).

Incorrect approach:

if obstacle == lane:  # Wrong! Comparing 1-based with 0-based
    dp[lane] = float('inf')

Correct approach:

if obstacle == lane + 1:  # Convert 0-based index to 1-based lane number
    dp[lane] = float('inf')

2. Setting Infinity Before Computing Minimum

The order of operations matters. You must set blocked lanes to infinity BEFORE calculating the minimum cost for side jumps. Otherwise, you might incorrectly consider an impossible path.

Incorrect approach:

min_jumps = min(dp) + 1  # Computing minimum first
for lane in range(3):
    if obstacle == lane + 1:
        dp[lane] = float('inf')  # Setting infinity after

Correct approach:

# First mark blocked lanes
for lane in range(3):
    if obstacle == lane + 1:
        dp[lane] = float('inf')
      
# Then compute minimum from valid lanes
min_jumps = min(dp) + 1

3. Forgetting to Skip Non-Obstacle Lanes in Update

When updating DP values, you must skip lanes that have obstacles at the current position. Updating a blocked lane would incorrectly make it appear reachable.

Incorrect approach:

for lane in range(3):
    dp[lane] = min(dp[lane], min_jumps_with_side_jump)  # Updates even blocked lanes

Correct approach:

for lane in range(3):
    if obstacle != lane + 1:  # Only update if lane is clear
        dp[lane] = min(dp[lane], min_jumps_with_side_jump)

4. Processing Point 0

The problem states the frog starts at point 0, which has no obstacles. Processing obstacles[0] is unnecessary and could cause errors if not handled properly.

Solution: Use obstacles[1:] to skip the first element and start processing from point 1.

5. Not Understanding the Side Jump Logic

The key insight is that min(dp) + 1 represents taking the optimal path to the current point and then making one side jump if needed. Some might incorrectly add 1 to every lane's cost, which would count multiple jumps.

Remember: The frog can reach a lane either by:

• Continuing straight from the previous point (cost: dp[lane])
• Jumping from the best available lane (cost: min(dp) + 1)

We take the minimum of these two options.