Skip to main content
Talentd

Minimum Cost to Move Between Indices - Solution & Explanation

MediumArrayGreedyPrefix Sum7 min read
Practice this problem

Problem Statement

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:

  • To any index y with cost abs(nums[x] - nums[y]), or
  • To closest(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:​​​​​​​​​​​​​​​​​​​​

  • The closest indices are [1, 0, 1] respectively.
  • For [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.
  • For [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.
  • For [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:

  • The closest indices are [1, 2, 1, 2] respectively.
  • For [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.
  • For [1, 2], the closest move from index 1 to 2 has cost 1.
  • For [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] <= 109
  • nums is strictly increasing
  • 1 <= queries.length <= 105
  • queries[i] = [li, ri]​​​​​​​
  • 0 <= li, ri < nums.length

Approach Overview

Problem 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.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Explicit Graph + DijkstraO(n log n)O(n)General weighted transitions where costs vary
Value Grouping with Hash MapO(n)O(n)Arrays with many repeated values and jump rules
0-1 BFS with DequeO(n)O(n)When edge weights are only 0 or 1

Video Solution

Minimum Cost to Move Between Indices | Leetcode 3919 • Techdose • 627 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Minimum Cost to Move Between Indices easy or hard?
The problem is generally rated Medium. The challenge comes from recognizing the array as an implicit graph and choosing the right shortest-path technique such as 0-1 BFS or Dijkstra depending on edge weights.
Minimum Cost to Move Between Indices Python/Java solution
Most implementations use BFS-style traversal with a hashmap and deque. Python solutions typically use collections.deque and defaultdict, while Java implementations rely on ArrayDeque and HashMap. Both achieve O(n) time with careful value-group processing.
How to solve Minimum Cost to Move Between Indices in O(n)?
Use a deque-based 0-1 BFS. Push zero-cost moves to the front of the deque and cost-one moves to the back. Maintain a hashmap mapping each value to its indices so jumps can be processed in constant time, and clear the group after processing to avoid repeated work.
What is the best approach for Minimum Cost to Move Between Indices?
The most efficient approach models the array as a graph and uses 0-1 BFS with a deque. Neighbor moves are processed with cost 1 while special jumps are processed with cost 0. Combined with a hashmap that groups indices by value, the algorithm runs in O(n) time and O(n) space.
Is Minimum Cost to Move Between Indices asked at Google/Amazon/Meta?
Shortest path problems on arrays and implicit graphs appear frequently in interviews at companies like Amazon, Google, and Meta. Variants involving BFS, Dijkstra, or 0-1 BFS are common because they test graph modeling and optimization skills.
What data structure is used in Minimum Cost to Move Between Indices?
Key data structures include a deque for 0-1 BFS, a hashmap mapping values to index lists, and an array for tracking minimum distances. In the Dijkstra variant, a priority queue replaces the deque.
What is the time complexity of Minimum Cost to Move Between Indices?
The optimal solution runs in O(n) time when using 0-1 BFS and value grouping because each index and value group is processed once. A more general implementation using Dijkstra’s algorithm runs in O(n log n) due to priority queue operations.

Ready to solve this problem?

Practice Minimum Cost to Move Between Indices with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays