You are given an integer array nums where nums is strictly increasing.
For each index x, let closest(x) be the adjacent index y such that abs(nums[x] - nums[y]) is minimized. If both adjacent indices exist and give the same difference, choose the smaller index.
From any index x, you can move in two ways:
y with cost abs(nums[x] - nums[y]), orclosest(x) with cost 1.You are also given a 2D integer array queries, where each queries[i] = [li, ri].
For each query, calculate the minimum total cost to move from index li to index ri.
Return an integer array ans, where ans[i] is the answer for the ith query.
The absolute difference between two values x and y is defined as abs(x - y).
Example 1:
Input: nums = [-5,-2,3], queries = [[0,2],[2,0],[1,2]]
Output: [6,2,5]
Explanation:
[1, 0, 1] respectively.[0, 2], the path 0 → 1 → 2 uses a closest move from index 0 to 1 with cost 1 and a move from index 1 to 2 with cost |-2 - 3| = 5, giving total 1 + 5 = 6.[2, 0], the path 2 → 1 → 0 uses two closest moves from index 2 to 1 and from index 1 to 0, each with cost 1, giving total 2.[1, 2], the direct move from index 1 to index 2 has cost |-2 - 3| = 5, which is optimal.Thus, ans = [6, 2, 5].
Example 2:
Input: nums = [0,2,3,9], queries = [[3,0],[1,2],[2,0]]
Output: [4,1,3]
Explanation:
[1, 2, 1, 2] respectively.[3, 0], the path 3 → 2 → 1 → 0 uses closest moves from index 3 to 2 and from 2 to 1, each with cost 1, and a move from 1 to 0 with cost |2 - 0| = 2, giving total 1 + 1 + 2 = 4.[1, 2], the closest move from index 1 to 2 has cost 1.[2, 0], the path 2 → 1 → 0 uses a closest move from index 2 to 1 with cost 1 and a move from 1 to 0 with cost |2 - 0| = 2, giving total 1 + 2 = 3.Thus, ans = [4, 1, 3].
Constraints:
2 <= nums.length <= 105-109 <= nums[i] <= 109nums is strictly increasing1 <= queries.length <= 105queries[i] = [li, ri]0 <= li, ri < nums.lengthProblem Overview: You are given an array where each index represents a position you can stand on. From an index, you can move to neighboring indices or jump to other indices based on value relationships. Each move has a cost, and the goal is to reach the target index with the minimum total cost.
Approach 1: Explicit Graph + Dijkstra (O(n log n) time, O(n) space)
Treat every index as a node in a graph. Edges represent allowed moves such as i → i+1, i → i-1, or jumps to other indices with the same value. Since edges may have different costs, apply Dijkstra’s algorithm using a min‑heap. Maintain a distance array where dist[i] stores the minimum cost to reach index i. Each step extracts the lowest‑cost node from the heap and relaxes its neighbors. This approach is straightforward and works for any weighted transition rule, but the heap operations introduce an extra log n factor.
Approach 2: Value Grouping + Graph Traversal (O(n) time, O(n) space)
Instead of scanning the entire array to find jump targets, preprocess indices by value using a hash map from value → list of indices. When you land on index i, you instantly know all indices with the same value and can process them in one pass. After exploring a value group, clear the list so it isn’t processed again. This prevents repeated work and keeps the total traversal linear. This technique often appears in array graph problems involving repeated values and benefits from fast hash map lookups.
Approach 3: 0‑1 BFS with Deque (O(n) time, O(n) space)
If the movement costs are only 0 or 1, replace Dijkstra with 0‑1 BFS. Use a deque: push zero‑cost transitions to the front and cost‑one transitions to the back. This guarantees nodes are processed in increasing cost order without a heap. Combine this with value grouping to avoid revisiting identical-value jumps. The algorithm effectively becomes a shortest path search on an implicit graph and runs in linear time. Concepts overlap with breadth-first search and weighted graph traversal.
Recommended for interviews: The optimized BFS approach using value grouping is typically expected. Starting with the naive graph interpretation shows you understand the problem structure. Moving to the hashmap optimization and finally to 0‑1 BFS demonstrates strong command of shortest‑path techniques and practical graph optimization, common patterns in graph problems.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Explicit Graph + Dijkstra | O(n log n) | O(n) | General weighted transitions where costs vary |
| Value Grouping with Hash Map | O(n) | O(n) | Arrays with many repeated values and jump rules |
| 0-1 BFS with Deque | O(n) | O(n) | When edge weights are only 0 or 1 |
Practice Minimum Cost to Move Between Indices with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor