3919. Minimum Cost to Move Between Indices
Asked at Visa
Difficulty
Medium
Time
O(n + q)
Space
O(n)
Pattern
Array
Companies
1
Problem
You get an array nums that is strictly increasing (every value is bigger than the one before it). You also get a list of queries; each query is a pair of indices [l, r].
From any index x you have two kinds of moves. First, you may jump to any index y and pay abs(nums[x] - nums[y]). Second, you may step to closest(x) and pay a flat cost of 1. Here closest(x) means the neighbor of x (index x-1 or x+1) whose value is nearest to nums[x]. If both neighbors are equally near, pick the smaller index. At the two ends there is only one neighbor, so that one is closest.
For each query, find the minimum total cost to travel from index l to index r. Return an array with one answer per query, in the same order.
Two kinds of moves
Constraints
- ●
2 <= nums.length <= 10^5 - ●
-10^9 <= nums[i] <= 10^9 - ●
nums is strictly increasing - ●
1 <= queries.length <= 10^5 - ●
queries[i] = [li, ri] - ●
0 <= li, ri < nums.length
Examples
nums = [-5,-2,3], queries = [[0,2],[2,0],[1,2]][6,2,5]nums = [0,2,3,9], queries = [[3,0],[1,2],[2,0]][4,1,3]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Visa | Medium | View all Visa questions → |
How to Think About It
Because nums is strictly increasing, a direct jump from l to r costs the same as walking every adjacent step at full price: nums[r] - nums[l].
So the only real saving is the 1-cost "closest" step. Walking one index at a time lets you use a 1-cost step whenever the neighbor you are heading to is the current index's closest.
Key insight: moving right from i to i + 1 costs 1 if closest(i) == i + 1, otherwise nums[i+1] - nums[i]. Moving left from i to i - 1 costs 1 if closest(i) == i - 1, otherwise the gap. Since every gap is at least 1, walking step by step is never worse than jumping.
Build two prefix-sum arrays — rightward step costs and leftward step costs — and answer each query by a subtraction.
Walkthrough for nums = [-5,-2,3]: closest = [1,0,1]. Right steps: 0->1 costs 1 (closest), 1->2 costs 5. Left steps: 2->1 costs 1, 1->0 costs 1. So 0->2 = 6, 2->0 = 2, 1->2 = 5.
Optimal Approach
Step 1: Compute closest(i): the only neighbor at the ends; otherwise the neighbor with the smaller gap, choosing the left one on ties.
Step 2: right[i+1] = right[i] + (1 if closest(i) == i+1 else nums[i+1] - nums[i]).
Step 3: left[i+1] = left[i] + (1 if closest(i+1) == i else nums[i+1] - nums[i]) — the cost of stepping from i+1 down to i.
Step 4: For a query (l, r): if l <= r, answer right[r] - right[l]; else left[l] - left[r].
Time: O(n + q). Space: O(n).
Walk one index at a time
What Trips People Up in Real Interviews
Running a shortest-path search per query. With 10^5 queries that is far too slow — prove that step-by-step walking is optimal first.
Using a single prefix array for both directions. closest is not symmetric, so the leftward and rightward step costs differ.
Breaking ties toward the right neighbor. The statement picks the smaller index on ties.
Overflow in C++/Java: gaps reach 2 * 10^9 and sums reach 10^14, so use 64-bit prefix sums.
Solution Code
O(n + q) timedef minCost(nums, queries):
n = len(nums)
def closest(i):
if i == 0:
return 1
if i == n - 1:
return n - 2
return i - 1 if nums[i] - nums[i - 1] <= nums[i + 1] - nums[i] else i + 1
right = [0] * n
left = [0] * n
for i in range(n - 1):
gap = nums[i + 1] - nums[i]
right[i + 1] = right[i] + (1 if closest(i) == i + 1 else gap)
left[i + 1] = left[i] + (1 if closest(i + 1) == i else gap)
res = []
for l, r in queries:
if l <= r:
res.append(right[r] - right[l])
else:
res.append(left[l] - left[r])
return resFrequently Asked Questions
What is the Minimum Cost to Move Between Indices problem?
Minimum Cost to Move Between Indices gives you a strictly increasing array. From index `x` you can jump to any index `y` for `|nums[x] - nums[y]|`, or step to `closest(x)` — the adjacent index with the smaller value gap — for a flat cost of 1. Answer many queries for the cheapest route from `l` to `r`. Once you see that the best route never skips an index, prefix sums answer each query in `O(1)`.
How do you solve Minimum Cost to Move Between Indices?
The optimal approach runs in O(n + q) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Minimum Cost to Move Between Indices?
Minimum Cost to Move Between Indices is asked at Visa. It is a medium difficulty problem.
What are common mistakes on Minimum Cost to Move Between Indices?
- Running a shortest-path search per query. With `10^5` queries that is far too slow — prove that step-by-step walking is optimal first.
- Using a single prefix array for both directions. `closest` is not symmetric, so the leftward and rightward step costs differ.
- Breaking ties toward the right neighbor. The statement picks the smaller index on ties.
- Overflow in C++/Java: gaps reach `2 * 10^9` and sums reach `10^14`, so use 64-bit prefix sums.