โ† Amazon questions

Minimum skips to arrive at meeting on time

Filed under Amazon

Free read 2 of 3

Define dp[i][j] as the minimum time to travel i segments with j skips.

The question

Given an array of road segment times and a speed, find the minimum number of skips required to arrive at a meeting on time, where each skip allows you to ignore the delay of a segment.

Constraints

  • 1 <= dist.length <= 1000
  • 1 <= speed, hoursBefore <= 10^9
  • 0 <= dist[i] <= 10^5

Examples

Input
dist = [1,3,2], speed = 4, hoursBefore = 2
Output
1
Why
Skipping the second segment allows arrival within the time limit.

Approach

  1. Define dp[i][j] as the minimum time to travel i segments with j skips.

Solution

O(n^2) time, O(n) space

Python
def minSkips(dist, speed, hoursBefore):
    n = len(dist)
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    for d in dist:
        new_dp = [float('inf')] * (n + 1)
        for j in range(n + 1):
            if dp[j] == float('inf'): continue
            new_dp[j] = min(new_dp[j], (dp[j] + d + speed - 1) // speed * speed)
            if j + 1 <= n: new_dp[j+1] = min(new_dp[j+1], dp[j] + d)
        dp = new_dp
    for j in range(n + 1):
        if dp[j] <= hoursBefore * speed: return j
    return -1

Tips

  • What they are testing: Test with cases where no skips are possible or all skips are needed.
  • Common mistake: Using floating point arithmetic which leads to precision errors; use integer math instead.

Follow-ups

  • Optimize from memoization to tabulation
  • Provide a binary search approach for a modified version

Related Amazon questions

Collected from public candidate posts and coding forums. Updated Nov 2026.