Minimum Cost to Move Between Indices
Asked at Visa
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).
Asked At
| 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).
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.