LeetCode 1883 - Minimum Skips to Arrive at Meeting On Time

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

You are given a sequence of roads that must be traveled in order. Each road has a distance, and you travel at a fixed speed. Because speed is constant, the travel time for road i is:

$$\frac{dist[i]}{speed}$$

The tricky part of the problem is the mandatory resting rule. After finishing every road except the last one, you must wait until the next integer hour before starting the next road.

For example:

If you finish a road at time 2.3, you must wait until time 3.0
If you finish exactly at time 5.0, you continue immediately
No waiting is required after the final road

You are allowed to skip some of these rests. A skipped rest means you immediately continue driving instead of rounding up to the next integer hour.

The goal is to determine the minimum number of skips needed so that the total travel time is at most hoursBefore.

If even skipping every rest cannot get you there on time, you return -1.

The input consists of:

dist, an array of road distances
speed, the constant driving speed
hoursBefore, the deadline

The constraints are important:

n <= 1000
Distances can be large
Floating point precision can become dangerous
A brute force search over all subsets of skipped rests would be impossible because there are up to 2^(n-1) combinations

The problem strongly suggests dynamic programming because:

Decisions are sequential
Each road introduces a choice:
skip the rest
do not skip the rest
We want an optimal minimum value

Several edge cases are important:

The trip may already fit without skips
Even skipping every rest may still exceed the deadline
Exact integer hour arrivals must not incorrectly round upward
Floating point rounding errors can easily break correctness
The final road does not require rounding

Approaches

Brute Force Approach

A straightforward approach is to try every possible combination of skipped rests.

There are n - 1 possible rest stops where a skip decision can be made. For each stop:

either skip
or do not skip

This creates 2^(n-1) possibilities.

For each combination:

Simulate the journey
Apply waiting rules
Compute the total time
Check whether arrival is within hoursBefore
Track the minimum number of skips

This works because it exhaustively checks every valid strategy.

However, it is far too slow. With n = 1000, the number of combinations becomes astronomically large.

Key Insight

The important observation is that the only thing that matters after processing some roads is:

how many skips we used
the minimum possible time achieved

This naturally leads to dynamic programming.

Define:

$$dp[i][k]$$

as the minimum total time needed to finish the first i roads using exactly k skips.

For every road, we have two transitions:

Do not skip the rest:

add travel time
round up to next integer hour if not the last road

Skip the rest:

add travel time directly
no rounding

Instead of floating point arithmetic, we store time in units of distance rather than hours.

If actual time is:

$$\frac{x}{speed}$$

we store x.

This avoids precision problems entirely.

The rounding operation becomes:

$$\left\lceil \frac{x}{speed} \right\rceil \cdot speed$$

which can be computed using integer arithmetic.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n \cdot n)	O(1)	Tries every skip combination
Optimal Dynamic Programming	O(n^2)	O(n^2)	Tracks minimum travel time for each skip count

Algorithm Walkthrough

Define a DP table where dp[k] represents the minimum accumulated distance-time units after processing some roads with exactly k skips used.
Instead of storing floating point hours, store scaled values:

$$\text{scaled time} = \text{actual time} \times speed$$

This keeps everything as integers and eliminates precision issues. 3. Initialize:

dp[0] = 0
all other states are infinity

Process roads one by one.
For each road and each possible skip count, consider two choices.
First choice, do not skip the rest:

add the road distance
if this is not the final road, round up to the next multiple of speed

The rounding formula is:

$\left\lceil \frac{x}{speed} \right\rceil \cdot speed$

Using integer arithmetic:

$$\frac{x + speed - 1}{speed} \times speed$$ 7. Second choice, skip the rest:

simply add the road distance
no rounding occurs

Store the minimum value for every (road, skips) state.
After processing all roads, check the smallest skip count whose total time satisfies:

$$dp[k] \le hoursBefore \times speed$$ 10. Return that minimum skip count. 11. If no state satisfies the deadline, return -1.

Why it works

The DP invariant is:

$$dp[i][k]$$

always stores the minimum possible accumulated scaled time after completing the first i roads using exactly k skips.

Every valid strategy for road i must either:

skip the rest
or wait until the next integer hour

The transition step explores both possibilities and keeps only the minimum achievable time. Since all valid decisions are considered and optimal substructure holds, the algorithm correctly computes the minimum skips needed.

Python Solution

from typing import List
import math

class Solution:
    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:
        n = len(dist)
        INF = float('inf')

        dp = [INF] * (n + 1)
        dp[0] = 0

        for i in range(n):
            next_dp = [INF] * (n + 1)

            for skips in range(i + 1):
                if dp[skips] == INF:
                    continue

                current = dp[skips] + dist[i]

                # Do not skip rest
                if i < n - 1:
                    wait_time = ((current + speed - 1) // speed) * speed
                else:
                    wait_time = current

                next_dp[skips] = min(next_dp[skips], wait_time)

                # Skip rest
                next_dp[skips + 1] = min(
                    next_dp[skips + 1],
                    current
                )

            dp = next_dp

        limit = hoursBefore * speed

        for skips in range(n + 1):
            if dp[skips] <= limit:
                return skips

        return -1

The implementation uses a one dimensional DP array for space optimization.

dp[k] stores the minimum scaled travel time achievable using exactly k skips after processing some prefix of roads.

For every road:

current represents the accumulated scaled time after traveling that road
The first transition applies mandatory waiting by rounding upward
The second transition skips the rest entirely

The final road is treated specially because no waiting occurs afterward.

Using scaled integer time instead of floating point hours is the most important implementation detail. It prevents subtle precision bugs that frequently occur in this problem.

The algorithm finally checks the smallest skip count whose total scaled time does not exceed:

$$hoursBefore \times speed$$

Go Solution

package main

import "math"

func minSkips(dist []int, speed int, hoursBefore int) int {
	n := len(dist)
	inf := math.MaxInt64

	dp := make([]int, n+1)

	for i := 1; i <= n; i++ {
		dp[i] = inf
	}

	dp[0] = 0

	for i := 0; i < n; i++ {
		nextDP := make([]int, n+1)

		for j := 0; j <= n; j++ {
			nextDP[j] = inf
		}

		for skips := 0; skips <= i; skips++ {
			if dp[skips] == inf {
				continue
			}

			current := dp[skips] + dist[i]

			// Do not skip rest
			waitTime := current
			if i < n-1 {
				waitTime = ((current + speed - 1) / speed) * speed
			}

			if waitTime < nextDP[skips] {
				nextDP[skips] = waitTime
			}

			// Skip rest
			if current < nextDP[skips+1] {
				nextDP[skips+1] = current
			}
		}

		dp = nextDP
	}

	limit := hoursBefore * speed

	for skips := 0; skips <= n; skips++ {
		if dp[skips] <= limit {
			return skips
		}
	}

	return -1
}

The Go implementation follows the same DP logic as the Python solution.

A few Go specific details are worth noting:

math.MaxInt64 is used as infinity
Slices are used for DP storage
Integer arithmetic safely handles rounding
No floating point values are used
Go integer division naturally truncates toward zero, which makes the ceiling formula work correctly

Worked Examples

Example 1

dist = [1,3,2]
speed = 4
hoursBefore = 2

Limit:

$$2 \times 4 = 8$$

Scaled times are stored directly.

Initial State

Skips	DP Value
0	0

Process Road 0, distance = 1

Without skip:

$$0 + 1 = 1$$

Round upward:

$$\left\lceil \frac{1}{4} \right\rceil \times 4 = 4$$

With skip:

$$1$$

Skips	DP Value
0	4
1	1

Process Road 1, distance = 3

From dp[0] = 4:

no skip:

$$4 + 3 = 7 \rightarrow 8$$

skip:

$$7$$

From dp[1] = 1:

no skip:

$$1 + 3 = 4 \rightarrow 4$$

skip:

$$4$$

Updated table:

Skips	DP Value
0	8
1	4
2	4

Process Road 2, distance = 2

Final road, no rounding.

From dp[0] = 8:

$$8 + 2 = 10$$

From dp[1] = 4:

$$4 + 2 = 6$$

From dp[2] = 4:

$$4 + 2 = 6$$

Final:

Skips	DP Value
0	10
1	6
2	6

Deadline is 8.

Minimum valid skips:

$$1$$

Answer:

Example 2

dist = [7,3,5,5]
speed = 2
hoursBefore = 10

Scaled deadline:

$$10 \times 2 = 20$$

After processing all roads:

Skips	Final Time
0	23
1	21
2	20
3	20

Smallest feasible skip count is:

Example 3

dist = [7,3,5,5]
speed = 1
hoursBefore = 10

Even with all skips:

$$7 + 3 + 5 + 5 = 20$$

Deadline:

$$10$$

Impossible to satisfy.

Answer:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2)	For each road, we iterate through all possible skip counts
Space	O(n)	Only two DP rows are stored at a time

The algorithm processes every road and every possible skip count combination once. Since there are at most n roads and n possible skip counts, the total complexity becomes quadratic.

The space optimization comes from using rolling arrays instead of a full two dimensional DP table.

Test Cases

sol = Solution()

# Provided examples
assert sol.minSkips([1,3,2], 4, 2) == 1  # One skip required
assert sol.minSkips([7,3,5,5], 2, 10) == 2  # Two skips required
assert sol.minSkips([7,3,5,5], 1, 10) == -1  # Impossible case

# Already possible without skips
assert sol.minSkips([1,1,1], 3, 3) == 0  # No skips needed

# Single road, no waiting involved
assert sol.minSkips([10], 5, 2) == 0  # Exact fit

# Single road impossible
assert sol.minSkips([11], 5, 2) == -1  # Cannot arrive in time

# Exact integer arrival times
assert sol.minSkips([4,4,4], 4, 3) == 0  # No rounding needed

# Must skip every rest
assert sol.minSkips([1,1,1], 2, 2) == 2  # Need all skips

# Large waiting penalties
assert sol.minSkips([5,1,1], 3, 3) == 1  # One strategic skip

# Many small roads
assert sol.minSkips([1]*10, 2, 6) == 4  # Multiple skips required

# Boundary style case
assert sol.minSkips([100000]*1000, 1000000, 100) >= -1  # Stress test

Test Summary

Test	Why
`[1,3,2]`	Validates basic skip behavior
`[7,3,5,5], speed=2`	Demonstrates multiple skips
`[7,3,5,5], speed=1`	Confirms impossible detection
`[1,1,1]` with generous time	Ensures zero skips works
Single road exact fit	Validates no post-final wait
Single road impossible	Checks minimal impossible case
Exact integer travel times	Ensures no unnecessary rounding
Need all skips	Tests maximum skip usage
Large waiting penalties	Confirms strategic skipping
Many small roads	Exercises DP transitions heavily
Large stress input	Validates performance limits

Edge Cases

One important edge case occurs when arrival times land exactly on integer hour boundaries. A careless implementation might incorrectly round upward even when no waiting is necessary. For example, finishing at exactly 3.0 hours should allow immediate continuation. The implementation handles this correctly using integer ceiling arithmetic, which naturally preserves exact multiples of speed.

Another critical edge case is the final road. The waiting rule applies only between roads, not after the destination is reached. Many incorrect solutions accidentally round after the final road as well, producing inflated travel times. The implementation explicitly skips rounding when processing the last road.

A third important edge case involves floating point precision. Since travel times are fractional, repeated additions and ceiling operations can accumulate floating point errors. A value that should mathematically equal 2.0 may become 2.000000001, causing incorrect extra waiting. The implementation completely avoids this problem by storing scaled integer times instead of floating point hours.

A fourth edge case occurs when the trip is impossible even after skipping every rest. In that situation, every DP state exceeds the allowed deadline. The final validation loop correctly returns -1 if no feasible skip count exists.