Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Minimum Cost to Move Between Indices solution and explanation

MediumArrayGreedyPrefix Sum5 min read49.4% acceptanceUpdated 27 Jul 2026
Practise Minimum Cost to Move Between Indices
22:28
Minimum Cost to Move Between Indices | Leetcode 3919Techdose · 22:28 · 627 viewsWatch on YouTube
8 more videos on this problem
  1. Minimum Cost to Move Between Indices | Leetcode 3919Techdose · 22:28 · 627 views
  2. Leetcode 3919 | Minimum Cost to Move Between Indices | Leetcode weekly contest 500CodeWithMeGuys · 22:47 · 481 views
  3. 3919. Minimum Cost to Move Between Indices (Solution)James Peralta · 27:31 · 269 views
  4. LeetCode Problem 3919 | Minimum Cost to Move Between IndicesRepovive TV · 19:20 · 174 views
  5. 3919. Minimum Cost to Move Between Indices | Weekly Contest 500 | Question 3 | Leetcode Contest SolAlgoTribe · 19:37 · 159 views
  6. 3919. Minimum Cost to Move Between Indices | Leetcode | Weekly Contest 500 | Problem 3Nidhi Jain · 21:21 · 91 views
  7. 3919. Minimum Cost to Move Between Indices |LeetCode Weekly 500 Greedy & PrefixSum Complete Dry RunBEASTCODES · 26:28 · 68 views
  8. Leetcode Weekly Contest 500 Q3: leetcode 3919. Minimum Cost to Move Between IndicesUnbound Coder · 14:12 · 37 views
  9. LeetCode 3919. Minimum Cost to Move Between Indices | Weekly Contest 500yoBro · 0:41 · 2 views

The problem

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

class Solution:
    def minCost(self, nums: list[int], queries: list[list[int]]) -> list[int]:
        n = len(nums)
        s1 = [0] * n
        s2 = [0] * n
        for i in range(1, n):
            c1 = (
                nums[i] - nums[i - 1]
                if i > 1 and nums[i - 1] - nums[i - 2] <= nums[i] - nums[i - 1]
                else 1
            )
            c2 = (
                nums[i] - nums[i - 1]
                if i < n - 1 and nums[i] - nums[i - 1] > nums[i + 1] - nums[i]
                else 1
            )
            s1[i] = s1[i - 1] + c1
            s2[i] = s2[i - 1] + c2
        m = len(queries)
        ans = [0] * m
        for i, (l, r) in enumerate(queries):
            ans[i] = s1[r] - s1[l] if l < r else s2[l] - s2[r]
        return ans
class Solution {
    public int[] minCost(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] s1 = new int[n];
        int[] s2 = new int[n];
        for (int i = 1; i < n; i++) {
            int c1 = (i > 1 && nums[i - 1] - nums[i - 2] <= nums[i] - nums[i - 1])
                ? nums[i] - nums[i - 1]
                : 1;
            int c2 = (i < n - 1 && nums[i] - nums[i - 1] > nums[i + 1] - nums[i])
                ? nums[i] - nums[i - 1]
                : 1;
            s1[i] = s1[i - 1] + c1;
            s2[i] = s2[i - 1] + c2;
        }
        int m = queries.length;
        int[] ans = new int[m];
        for (int i = 0; i < m; i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            ans[i] = (l < r) ? s1[r] - s1[l] : s2[l] - s2[r];
        }
        return ans;
    }
}
class Solution {
public:
    vector<int> minCost(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<int> s1(n, 0);
        vector<int> s2(n, 0);
        for (int i = 1; i < n; i++) {
            int c1 = (i > 1 && nums[i - 1] - nums[i - 2] <= nums[i] - nums[i - 1]) ? nums[i] - nums[i - 1] : 1;
            int c2 = (i < n - 1 && nums[i] - nums[i - 1] > nums[i + 1] - nums[i]) ? nums[i] - nums[i - 1] : 1;
            s1[i] = s1[i - 1] + c1;
            s2[i] = s2[i - 1] + c2;
        }
        int m = queries.size();
        vector<int> ans(m);
        for (int i = 0; i < m; i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            ans[i] = (l < r) ? s1[r] - s1[l] : s2[l] - s2[r];
        }
        return ans;
    }
};
function minCost(nums: number[], queries: number[][]): number[] {
    const n = nums.length;
    const s1: number[] = new Array(n).fill(0);
    const s2: number[] = new Array(n).fill(0);
    for (let i = 1; i < n; i++) {
        const c1 =
            i > 1 && nums[i - 1] - nums[i - 2] <= nums[i] - nums[i - 1] ? nums[i] - nums[i - 1] : 1;
        const c2 =
            i < n - 1 && nums[i] - nums[i - 1] > nums[i + 1] - nums[i] ? nums[i] - nums[i - 1] : 1;
        s1[i] = s1[i - 1] + c1;
        s2[i] = s2[i - 1] + c2;
    }
    const m = queries.length;
    const ans: number[] = new Array(m);
    for (let i = 0; i < m; i++) {
        const l = queries[i][0];
        const r = queries[i][1];
        ans[i] = l < r ? s1[r] - s1[l] : s2[l] - s2[r];
    }
    return ans;
}
func minCost(nums []int, queries [][]int) []int {
	n := len(nums)
	s1 := make([]int, n)
	s2 := make([]int, n)
	for i := 1; i < n; i++ {
		c1 := 1
		if i > 1 && nums[i-1]-nums[i-2] <= nums[i]-nums[i-1] {
			c1 = nums[i] - nums[i-1]
		}
		c2 := 1
		if i < n-1 && nums[i]-nums[i-1] > nums[i+1]-nums[i] {
			c2 = nums[i] - nums[i-1]
		}
		s1[i] = s1[i-1] + c1
		s2[i] = s2[i-1] + c2
	}
	m := len(queries)
	ans := make([]int, m)
	for i := 0; i < m; i++ {
		l := queries[i][0]
		r := queries[i][1]
		if l < r {
			ans[i] = s1[r] - s1[l]
		} else {
			ans[i] = s2[l] - s2[r]
		}
	}
	return ans
}
Try this approach in the editor

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

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.

Comments

Now write it yourselfClose this page and solve Minimum Cost to Move Between Indices in the editor, without looking.
Practise Minimum Cost to Move Between Indices