Cheapest City Hops
MediumArrays ยท Uber
Given distinct integers levels and a list of queries [s, t], return the minimum total cost to travel from city s to city t for each query.
A hop from city a to city b costs |levels[a] - levels[b]|, except that it costs 1 when b is the single city whose level is closest to levels[a]. If two cities are equally close to a, no hop from a is discounted. Hops are directed, and cities may be visited any number of times.
Example 1
- Input:
- levels = [8, 3, 5, 12], queries = [[0, 1], [1, 3], [3, 0]]
- Output:
- [2, 8, 1]
- Explanation
- City 0 reaches city 1 through city 2 for 1 + 1 = 2, since each hop goes to the closest level. A direct hop would cost 5.
Example 2
- Input:
- levels = [0, 4, 8], queries = [[0, 2], [1, 2], [2, 0]]
- Output:
- [5, 4, 2]
- Explanation
- City 1 is equally close to both others, so its hops are not discounted.
Example 3
- Input:
- levels = [10, 4], queries = [[0, 1], [1, 1]]
- Output:
- [1, 0]
Constraints
1 <= levels.length <= 200000-10^9 <= levels[i] <= 10^9, and all values are distinct1 <= queries.length <= 2000000 <= s, t < levels.length