3919. Minimum Cost to Move Between Indices

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums that is strictly increasing (each element is strictly greater than the one before it).

For each index x, we define closest(x) as the adjacent index y (meaning y = x - 1 or y = x + 1) such that the value abs(nums[x] - nums[y]) is as small as possible. If both adjacent indices exist and produce the same absolute difference, then we pick the smaller index.

Starting from any index x, you are allowed to move in one of two ways:

Move to any index y (not necessarily adjacent) at a cost of abs(nums[x] - nums[y]), or
Move to closest(x) at a cost of 1.

You are also given a 2D integer array queries, where each queries[i] = [li, ri].

For each query, you must compute the minimum total cost required to move from index li to index ri.

Return an integer array ans, where ans[i] holds the answer for the i-th query.

The absolute difference between two values x and y is defined as abs(x - y).

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Prefix Sums?

This problem maps to Prefix Sums through a short path in the full flowchart.

Precomputing prefix sums answers range queries in constant time.

Open in Flowchart

Intuition

The key observation starts with the direct move. Since nums is strictly increasing, moving directly from any index x to index y costs abs(nums[x] - nums[y]). By the triangle property of absolute differences, the cost of jumping directly from x to y equals the sum of consecutive gaps between them. For example, going from index a to index b (with a < b) directly costs nums[b] - nums[a], which is exactly (nums[a+1] - nums[a]) + (nums[a+2] - nums[a+1]) + ... + (nums[b] - nums[b-1]). This means a single big jump and a series of step-by-step adjacent jumps using the "direct move" rule cost the same. So the direct move can always be broken down into a chain of adjacent steps, and we never lose anything by thinking only in terms of moving one index at a time.

Given this, the only real choice we have at each adjacent step is whether to use the direct adjacent move (costing the gap nums[i] - nums[i-1]) or the closest shortcut (costing just 1). For each adjacent transition, we simply pick the cheaper of the two: min(gap, 1) when the shortcut is available in that direction.

The subtle part is figuring out when the closest shortcut is usable for a given step. The shortcut from index x goes to closest(x), and we need to check whether that closest neighbor lies in the direction we want to travel.

For a forward move (from a smaller index to a larger one, l < r), the step from i-1 to i can use the cost-1 shortcut only if closest(i-1) = i. This happens when the gap on the right (nums[i] - nums[i-1]) is strictly smaller than the gap on the left (nums[i-1] - nums[i-2]), or when there is no left neighbor. We capture this in the cost array s1.
For a backward move (from a larger index to a smaller one, l > r), the step from i back to i-1 can use the cost-1 shortcut only if closest(i) = i-1. This happens when the gap on the left (nums[i] - nums[i-1]) is strictly smaller than the gap on the right (nums[i+1] - nums[i]), or when there is no right neighbor. We capture this in the cost array s2.

Because each adjacent step's cost is fixed and independent of the path, we can precompute prefix sums of these per-step costs. s1[i] accumulates the cheapest forward-step cost up to index i, and s2[i] accumulates the cheapest backward-step cost. Then any query becomes a constant-time range lookup: a forward query l < r is answered by s1[r] - s1[l], and a backward query l > r is answered by s2[l] - s2[r]. This turns each query into an O(1) operation after an O(n) preprocessing pass.

Pattern Learn more about Greedy and Prefix Sum patterns.

Solution Approach

The implementation uses prefix sums to precompute per-step costs in two directions, allowing each query to be answered in O(1) time.

Step 1: Set up the cost arrays.

We define two arrays of length n:

s1[i] — prefix sum of the cheapest forward step cost (moving from index i-1 to i).
s2[i] — prefix sum of the cheapest backward step cost (moving from index i back to i-1).

Both start as zero arrays, and we fill them in a single loop from i = 1 to n - 1.

Step 2: Compute the per-step cost for the forward direction (c1).

For the step crossing the gap between i-1 and i, the shortcut costs 1 only if closest(i-1) = i, i.e. the right gap is at least as cheap as the left gap. The code uses:

c1 = (
    nums[i] - nums[i - 1]
    if i > 1 and nums[i - 1] - nums[i - 2] <= nums[i] - nums[i - 1]
    else 1
)

Reading this carefully: when i > 1 and the left gap nums[i-1] - nums[i-2] is <= the right gap nums[i] - nums[i-1], the shortcut is not beneficial in the forward direction, so we pay the full gap nums[i] - nums[i-1]. Otherwise (no left neighbor, or the right gap is strictly cheaper so the shortcut applies), we pay just 1.

Step 3: Compute the per-step cost for the backward direction (c2).

For the same step, the backward shortcut costs 1 only if closest(i) = i-1, i.e. the left gap is strictly smaller than the right gap. The code uses:

c2 = (
    nums[i] - nums[i - 1]
    if i < n - 1 and nums[i] - nums[i - 1] > nums[i + 1] - nums[i]
    else 1
)

Here, when i < n - 1 and the left gap nums[i] - nums[i-1] is strictly greater than the right gap nums[i+1] - nums[i], the closest neighbor of i is not i-1, so the shortcut is unavailable and we pay the full gap. Otherwise we pay 1.

Step 4: Accumulate the prefix sums.

s1[i] = s1[i - 1] + c1
s2[i] = s2[i - 1] + c2

After the loop, s1[i] equals the minimum total cost to travel forward from index 0 to index i, and s2[i] equals the minimum total cost to travel backward from index i to index 0.

Step 5: Answer each query with a range difference.

for i, (l, r) in enumerate(queries):
    ans[i] = s1[r] - s1[l] if l < r else s2[l] - s2[r]

If l < r (forward move), the answer is the sum of forward step costs from l to r, given by s1[r] - s1[l].
If l > r (backward move), the answer is the sum of backward step costs from r to l, given by s2[l] - s2[r].
If l == r, both branches yield 0, matching the fact that no movement is needed.

Complexity analysis.

Time: O(n + m), where n is the length of nums and m is the number of queries. Building the prefix sums takes O(n), and each query is resolved in O(1).
Space: O(n) for the two prefix-sum arrays (excluding the output array).

The pattern here is the classic prefix-sum precomputation: because every adjacent step has a fixed, path-independent cost, we collapse all possible movement decisions into two cost arrays and reduce every query to a simple subtraction.

Example Walkthrough

Let's trace through the solution with a small concrete example.

Input:

nums = [1, 3, 6, 7]
queries = [[0, 3], [3, 0], [2, 1]]

First, let's compute the adjacent gaps so we can reason about closest:

Gap between index 0 and 1: 3 - 1 = 2
Gap between index 1 and 2: 6 - 3 = 3
Gap between index 2 and 3: 7 - 6 = 1

Step 1–4: Build the prefix-sum arrays s1 (forward) and s2 (backward).

Both arrays have length 4 and start as s1 = [0, 0, 0, 0], s2 = [0, 0, 0, 0]. We loop from i = 1 to 3.

i = 1 (step crossing the gap between index 0 and 1, gap = 2):

Forward c1: Condition i > 1 is False (no left neighbor). So the shortcut applies → c1 = 1.
Backward c2: Check i < n-1 (1 < 3 ✓) and left gap > right gap → 2 > 3? No. So shortcut applies → c2 = 1.
Update: s1[1] = 0 + 1 = 1, s2[1] = 0 + 1 = 1.

i = 2 (step crossing the gap between index 1 and 2, gap = 3):

Forward c1: i > 1 ✓, check left gap <= right gap → 2 <= 3? Yes. Shortcut is not beneficial forward → pay full gap c1 = 3.
Backward c2: i < n-1 (2 < 3 ✓), check left gap > right gap → 3 > 1? Yes. So closest(2) ≠ 1 → pay full gap c2 = 3.
Update: s1[2] = 1 + 3 = 4, s2[2] = 1 + 3 = 4.

i = 3 (step crossing the gap between index 2 and 3, gap = 1):

Forward c1: i > 1 ✓, check left gap <= right gap → 3 <= 1? No. Right gap is strictly cheaper, shortcut applies → c1 = 1.
Backward c2: i < n-1 is False (no right neighbor). Shortcut applies → c2 = 1.
Update: s1[3] = 4 + 1 = 5, s2[3] = 4 + 1 = 5.

Final arrays:

s1 = [0, 1, 4, 5]
s2 = [0, 1, 4, 5]

Step 5: Answer each query.

Query [0, 3] (forward, since 0 < 3):

ans = s1[3] - s1[0] = 5 - 0 = 5.
Sanity check: From 0→1 the shortcut gives cost 1 (cheaper than gap 2). From 1→2 the gap 3 is cheaper to pay directly (shortcut unavailable forward). From 2→3 the shortcut gives cost 1 (cheaper than gap 1, tie-friendly). Total 1 + 3 + 1 = 5. ✓

Query [3, 0] (backward, since 3 > 0):

ans = s2[3] - s2[0] = 5 - 0 = 5.
Sanity check: Travelling 3→2→1→0, the per-step backward costs are 1 + 3 + 1 = 5. ✓

Query [2, 1] (backward, since 2 > 1):

ans = s2[2] - s2[1] = 4 - 1 = 3.
Sanity check: The single backward step 2→1 crosses the gap of 3. Since closest(2) = 3 (the right gap 1 is smaller than the left gap 3), the shortcut points the wrong way, so we must pay the full gap 3. ✓

Result:

ans = [5, 5, 3]

This demonstrates the core idea: every adjacent step has a fixed, path-independent cost (min(gap, 1) only when closest points in the travel direction). By precomputing these costs as prefix sums in both directions, each query collapses into a single O(1) subtraction.

Solution Implementation

1class Solution:
2    def minCost(self, nums: list[int], queries: list[list[int]]) -> list[int]:
3        n = len(nums)
4
5        # forward_prefix[i]: prefix sum of forward-direction costs up to index i
6        # backward_prefix[i]: prefix sum of backward-direction costs up to index i
7        forward_prefix = [0] * n
8        backward_prefix = [0] * n
9
10        for i in range(1, n):
11            gap = nums[i] - nums[i - 1]  # difference between consecutive elements
12
13            # Forward cost: use the raw gap when the previous slope
14            # (nums[i-1] - nums[i-2]) is no steeper than the current gap,
15            # i.e. the trend keeps increasing consistently; otherwise cost is 1.
16            forward_cost = (
17                gap
18                if i > 1 and nums[i - 1] - nums[i - 2] <= gap
19                else 1
20            )
21
22            # Backward cost: use the raw gap when the current gap is strictly
23            # larger than the next gap (nums[i+1] - nums[i]); otherwise cost is 1.
24            backward_cost = (
25                gap
26                if i < n - 1 and gap > nums[i + 1] - nums[i]
27                else 1
28            )
29
30            forward_prefix[i] = forward_prefix[i - 1] + forward_cost
31            backward_prefix[i] = backward_prefix[i - 1] + backward_cost
32
33        m = len(queries)
34        answer = [0] * m
35
36        for idx, (left, right) in enumerate(queries):
37            if left < right:
38                # Moving rightward: use forward prefix sums
39                answer[idx] = forward_prefix[right] - forward_prefix[left]
40            else:
41                # Moving leftward (or equal): use backward prefix sums
42                answer[idx] = backward_prefix[left] - backward_prefix[right]
43
44        return answer
45

1class Solution {
2    /**
3     * Computes the answer for each query based on prefix-sum arrays.
4     *
5     * @param nums    the input integer array
6     * @param queries each query is a pair [left, right]
7     * @return an array holding the result for every query
8     */
9    public int[] minCost(int[] nums, int[][] queries) {
10        int n = nums.length;
11
12        // prefixForward[i]  : prefix sum used when the query goes left -> right (l < r)
13        // prefixBackward[i] : prefix sum used when the query goes right -> left (l >= r)
14        int[] prefixForward = new int[n];
15        int[] prefixBackward = new int[n];
16
17        for (int i = 1; i < n; i++) {
18            // Cost contribution for the forward direction.
19            // If the previous step's increment is no larger than the current one,
20            // pay the current difference; otherwise pay a fixed cost of 1.
21            int forwardCost = (i > 1 && nums[i - 1] - nums[i - 2] <= nums[i] - nums[i - 1])
22                ? nums[i] - nums[i - 1]
23                : 1;
24
25            // Cost contribution for the backward direction.
26            // If the current step's increment is larger than the next one,
27            // pay the current difference; otherwise pay a fixed cost of 1.
28            int backwardCost = (i < n - 1 && nums[i] - nums[i - 1] > nums[i + 1] - nums[i])
29                ? nums[i] - nums[i - 1]
30                : 1;
31
32            // Build the running prefix sums.
33            prefixForward[i] = prefixForward[i - 1] + forwardCost;
34            prefixBackward[i] = prefixBackward[i - 1] + backwardCost;
35        }
36
37        int queryCount = queries.length;
38        int[] answers = new int[queryCount];
39
40        for (int i = 0; i < queryCount; i++) {
41            int left = queries[i][0];
42            int right = queries[i][1];
43
44            // For a forward query (left < right) use the forward prefix sums;
45            // otherwise use the backward prefix sums.
46            answers[i] = (left < right)
47                ? prefixForward[right] - prefixForward[left]
48                : prefixBackward[left] - prefixBackward[right];
49        }
50
51        return answers;
52    }
53}
54

1class Solution {
2public:
3    vector<int> minCost(vector<int>& nums, vector<vector<int>>& queries) {
4        int n = nums.size();
5
6        // prefixForward[i]:  prefix sum of costs when traveling in the forward
7        //                    direction (left -> right), i.e. from index 0 up to i.
8        // prefixBackward[i]: prefix sum of costs when traveling in the backward
9        //                    direction (right -> left), i.e. from index 0 up to i.
10        vector<int> prefixForward(n, 0);
11        vector<int> prefixBackward(n, 0);
12
13        for (int i = 1; i < n; i++) {
14            // Cost for the forward direction at position i.
15            // If the previous step's gap is no larger than the current gap,
16            // we pay the current gap; otherwise the cheaper cost of 1.
17            int forwardCost =
18                (i > 1 && nums[i - 1] - nums[i - 2] <= nums[i] - nums[i - 1])
19                    ? nums[i] - nums[i - 1]
20                    : 1;
21
22            // Cost for the backward direction at position i.
23            // If the current gap is larger than the next gap,
24            // we pay the current gap; otherwise the cheaper cost of 1.
25            int backwardCost =
26                (i < n - 1 && nums[i] - nums[i - 1] > nums[i + 1] - nums[i])
27                    ? nums[i] - nums[i - 1]
28                    : 1;
29
30            // Accumulate the prefix sums.
31            prefixForward[i] = prefixForward[i - 1] + forwardCost;
32            prefixBackward[i] = prefixBackward[i - 1] + backwardCost;
33        }
34
35        int queryCount = queries.size();
36        vector<int> ans(queryCount);
37
38        for (int i = 0; i < queryCount; i++) {
39            int left = queries[i][0];
40            int right = queries[i][1];
41
42            // If left < right, we move forward and use prefixForward.
43            // Otherwise we move backward and use prefixBackward.
44            ans[i] = (left < right)
45                         ? prefixForward[right] - prefixForward[left]
46                         : prefixBackward[left] - prefixBackward[right];
47        }
48
49        return ans;
50    }
51};
52

1function minCost(nums: number[], queries: number[][]): number[] {
2    const n = nums.length;
3
4    // prefixForward[i]: prefix sum of forward-direction step costs up to index i
5    const prefixForward: number[] = new Array(n).fill(0);
6    // prefixBackward[i]: prefix sum of backward-direction step costs up to index i
7    const prefixBackward: number[] = new Array(n).fill(0);
8
9    for (let i = 1; i < n; i++) {
10        // Cost of moving forward (left -> right) onto index i.
11        // If the gap is non-decreasing compared to the previous gap, the cost is
12        // the current gap value; otherwise it is a flat cost of 1.
13        const forwardCost =
14            i > 1 && nums[i - 1] - nums[i - 2] <= nums[i] - nums[i - 1]
15                ? nums[i] - nums[i - 1]
16                : 1;
17
18        // Cost of moving backward (right -> left) across index i.
19        // If the current gap is strictly larger than the next gap, the cost is
20        // the current gap value; otherwise it is a flat cost of 1.
21        const backwardCost =
22            i < n - 1 && nums[i] - nums[i - 1] > nums[i + 1] - nums[i]
23                ? nums[i] - nums[i - 1]
24                : 1;
25
26        prefixForward[i] = prefixForward[i - 1] + forwardCost;
27        prefixBackward[i] = prefixBackward[i - 1] + backwardCost;
28    }
29
30    const queryCount = queries.length;
31    const answer: number[] = new Array(queryCount);
32
33    for (let i = 0; i < queryCount; i++) {
34        const left = queries[i][0];
35        const right = queries[i][1];
36
37        // If moving rightward, use the forward prefix sums;
38        // otherwise use the backward prefix sums for the range.
39        answer[i] =
40            left < right
41                ? prefixForward[right] - prefixForward[left]
42                : prefixBackward[left] - prefixBackward[right];
43    }
44
45    return answer;
46}
47

Time and Space Complexity

Time Complexity: O(n + m)

The algorithm consists of two main phases:

Prefix sum construction: The first loop iterates from i = 1 to n - 1, performing constant-time work at each step (computing c1, c2, and updating the prefix arrays s1 and s2). This contributes O(n), where n = len(nums).
Query processing: The second loop iterates over all m queries, where m = len(queries). For each query, the answer is computed in O(1) time using the precomputed prefix sums (s1[r] - s1[l] or s2[l] - s2[r]). This contributes O(m).

Since the two phases are sequential and independent, the total time complexity is O(n) + O(m) = O(n + m).

Space Complexity: O(n)

The auxiliary space usage breaks down as follows:

Two prefix sum arrays s1 and s2, each of size n, requiring O(n) space.
The output array ans of size m, requiring O(m) space.

If the output array is not counted toward auxiliary space (as is common, since it is the required result), the extra space is O(n). Counting the output, the total space is O(n + m). The dominant auxiliary space is therefore O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Misapplying the tie-breaking rule and mixing up the strict vs. non-strict comparisons for the two directions

The single most error-prone part of this problem is determining when the shortcut (cost 1) is available for each direction. The forward and backward steps use different comparison operators (<= vs. >), and the asymmetry comes directly from the tie-breaking rule: "if both adjacent indices produce the same difference, pick the smaller index."

It is extremely tempting to write symmetric conditions (e.g., use <= for both, or < for both), but doing so silently produces wrong answers on inputs that contain ties between the left gap and the right gap.

Why the asymmetry exists

Consider crossing the gap between i-1 and i, where:

left gap = nums[i-1] - nums[i-2]
this gap = nums[i] - nums[i-1]
right gap = nums[i+1] - nums[i]

For the forward step (i-1 → i), the shortcut applies only if closest(i-1) == i. The neighbor i is chosen over i-2 when thisGap < leftGap, or when thisGap == leftGap (tie → smaller index i-2... wait, careful!). Actually for closest(i-1), the candidates are i-2 (smaller index) and i (larger index). On a tie the smaller index i-2 wins, so closest(i-1) == i requires thisGap < leftGap strictly. Hence the shortcut is unavailable (pay the full gap) when leftGap <= thisGap — exactly the <= in the code.

For the backward step (i → i-1), the shortcut applies only if closest(i) == i-1. The candidates for closest(i) are i-1 (smaller index) and i+1 (larger index). On a tie the smaller index i-1 wins, so closest(i) == i-1 holds when thisGap <= rightGap. The shortcut is therefore unavailable (pay the full gap) only when thisGap > rightGap strictly — exactly the > in the code.

Buggy version (symmetric comparisons):

# WRONG: treats both directions identically and ignores tie-breaking
forward_cost  = gap if i > 1 and nums[i-1] - nums[i-2] < gap  else 1   # should be <=
backward_cost = gap if i < n-1 and gap >= nums[i+1] - nums[i] else 1   # should be >

On equal-gap inputs (e.g. nums = [1, 3, 5, 7], where every gap is 2) this yields shortcuts/full-costs on the wrong side and gives incorrect query totals.

Solution / how to avoid it

Anchor every comparison to the tie-breaking rule: a tie always resolves to the smaller index, so the larger-index neighbor needs a strict win to be closest.
Forward shortcut available ⇔ thisGap < leftGap (strict) ⇒ full-cost condition is leftGap <= thisGap.
Backward shortcut available ⇔ thisGap <= rightGap (non-strict) ⇒ full-cost condition is thisGap > rightGap (strict).
Always guard the boundaries (i > 1 for the left neighbor, i < n - 1 for the right neighbor); when a neighbor doesn't exist there is no competing gap, so the closest neighbor is the only one available and the shortcut cost 1 applies.

A quick sanity check on a fully uniform array like nums = [1, 3, 5, 7] with queries [[0,3],[3,0]] is the cheapest way to confirm you got the strict/non-strict operators right—if either direction is off, the symmetric totals will diverge from the expected values.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: