Show problems as
Classic problem #1824MediumArrayDynamic ProgrammingGreedy

Minimum Sideway Jumps

Real-world version: Sideways Jumps Down the Three-Track Chute
Tracked in this browser only
Read Minimum Sideway Jumps on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Three tracks numbered 1, 2 and 3 run side by side from point 0 to the last point of a chute. blocks[i] names the one track shut at point i, or is 0 when no track is shut there.

A trolley starts at point 0 on track 2 and rolls forward to the last point. It cannot roll onto a point where its own track is shut.

At any point the trolley may jump sideways to either of the other two tracks, so long as that track is not shut at that point. A jump from track 1 straight to track 3 counts as one jump. Rolling forward costs nothing.

Return the fewest jumps needed to reach the last point on any track. A way through always exists.

Examples

Example 1

Input
blocks = [0, 2, 0]
Output
1

Track 2 is shut at the middle point, so a single jump onto either other track carries the trolley through.

Example 2

Input
blocks = [0, 2, 2, 2, 2, 2, 0]
Output
1

Track 2 is shut at every point along the way, so one jump at the start onto another track is enough and nothing further is needed.

Example 3

Input
blocks = [0, 3, 2, 1, 0]
Output
2

Track 3 is shut at the first point so the trolley jumps to track 1. Track 1 is shut at the third point and track 2 is shut where the trolley stands, so the second jump has to go straight across from track 1 to track 3.

Constraints

  • 2 <= blocks.length <= 500001
  • 0 <= blocks[i] <= 3
  • blocks[0] == 0
  • the last entry of blocks is 0

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_side_jumps(blocks: list[int]) -> int:
Java
public int minSideJumps(int[] blocks)

More on the same topics