LeetCode 3919 - Minimum Cost to Move Between Indices

We are given a strictly increasing array nums. Each position represents an index in the array, and we want to move between indices as cheaply as possible. For every index x, a special neighbor called closest(x) is defined.

leetcodemediumarraygreedyprefix-sum

LeetCode Problem 3919

Difficulty: 🟡 Medium
Topics: Array, Greedy, Prefix Sum

Solution

LeetCode 3919 - Minimum Cost to Move Between Indices

Problem Understanding

We are given a strictly increasing array nums. Each position represents an index in the array, and we want to move between indices as cheaply as possible.

For every index x, a special neighbor called closest(x) is defined. Since the array is strictly increasing, each index can only have up to two adjacent neighbors:

  • x - 1
  • x + 1

Among those adjacent neighbors, we choose the one whose value difference with nums[x] is smallest. If both differences are equal, we choose the smaller index.

From any index x, we have two possible types of moves:

  1. Move directly to any index y at cost:
abs(nums[x] - nums[y])
  1. Move to closest(x) at cost:
1

For each query [li, ri], we must compute the minimum total cost required to travel from index li to index ri.

The constraints are very large:

  • n ≤ 100,000
  • q ≤ 100,000

This immediately rules out running a shortest path algorithm independently for every query.

The array being strictly increasing is extremely important because it means:

  • abs(nums[i] - nums[j]) = nums[j] - nums[i] whenever j > i
  • Adjacent differences completely determine every closest relationship
  • The graph structure becomes highly predictable

Important edge cases include:

  • Moving left versus moving right.
  • Boundary indices, which only have one adjacent neighbor.
  • Ties when both adjacent differences are equal.
  • Queries where li == ri, whose answer must be zero.
  • Very large coordinate values up to 10^9, requiring 64 bit arithmetic internally.

Approaches

Brute Force

A direct interpretation is to build the graph.

Each index has:

  • One special edge to closest(i) with weight 1.
  • Edges to every other index with weight abs(nums[i] - nums[j]).

Then for every query we could run Dijkstra's algorithm.

This produces the correct answer because Dijkstra finds the shortest path in a weighted graph with nonnegative edge weights.

However, the graph contains:

O(n²)

edges due to the direct move option between every pair of indices.

With n = 100,000, this is completely infeasible in both memory and time.

Key Insight

The crucial observation is that the array is sorted.

Suppose we want to move from a smaller index to a larger index.

Any direct jump from i to j costs:

nums[j] - nums[i]

because the array is increasing.

Consider moving only through adjacent indices.

For every adjacent pair (i, i+1):

  • If closest(i) = i+1, then moving right across that edge costs 1.
  • Otherwise the cheapest way to cross is the direct difference:
nums[i+1] - nums[i]

The optimal path from left to right never needs to overshoot and come back. The minimum cost becomes the sum of independent costs of crossing each adjacent boundary.

Similarly, for moving from right to left:

  • If closest(i) = i-1, crossing costs 1.
  • Otherwise crossing costs nums[i] - nums[i-1].

Therefore every query reduces to a range sum problem.

We precompute:

  • Forward crossing costs.
  • Backward crossing costs.
  • Prefix sums of both arrays.

Then every query is answered in O(1) time.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(q · n² log n) O(n²) Build full graph and run shortest path
Optimal O(n + q) O(n) Precompute crossing costs and prefix sums

Algorithm Walkthrough

Step 1: Compute the closest index for every position

For every index:

  • Index 0 must choose 1.
  • Index n-1 must choose n-2.
  • Interior indices compare:
nums[i] - nums[i-1]
nums[i+1] - nums[i]

The smaller difference determines the closest neighbor.

If the differences are equal, choose the smaller index, namely i-1.

Step 2: Build forward crossing costs

For every adjacent boundary between i and i+1:

If:

closest(i) = i+1

then moving across this boundary costs 1.

Otherwise the cheapest crossing cost is:

nums[i+1] - nums[i]

Store this value in:

forward[i]

Step 3: Build backward crossing costs

For every adjacent boundary between i-1 and i:

If:

closest(i) = i-1

then moving left costs 1.

Otherwise it costs:

nums[i] - nums[i-1]

Store this value in:

backward[i]

Step 4: Build prefix sums

Construct:

prefForward
prefBackward

where:

prefForward[k]

contains the total forward crossing cost before position k.

Likewise for prefBackward.

These prefix sums allow constant time range queries.

Step 5: Answer queries

For a query (l, r):

If:

l < r

the answer is:

prefForward[r] - prefForward[l]

because we cross boundaries:

l, l+1, ..., r-1

If:

l > r

the answer is:

prefBackward[l] - prefBackward[r]

because we cross boundaries:

r+1, r+2, ..., l

If:

l == r

the answer is zero.

Why it works

For any movement direction, every path from one side of an adjacent boundary to the other must pay at least the minimum crossing cost of that boundary. Because the array is strictly increasing, crossing different boundaries becomes independent, and the optimal route is obtained by summing the minimum crossing cost of each boundary exactly once. The forward and backward arrays store these optimal boundary crossing costs, so their prefix sums produce the minimum total cost for every query.

Python Solution

class Solution:
    def minCost(self, nums: list[int], queries: list[list[int]]) -> list[int]:
        n = len(nums)

        closest = [0] * n

        closest[0] = 1
        closest[n - 1] = n - 2

        for i in range(1, n - 1):
            left_diff = nums[i] - nums[i - 1]
            right_diff = nums[i + 1] - nums[i]

            if left_diff <= right_diff:
                closest[i] = i - 1
            else:
                closest[i] = i + 1

        forward = [0] * (n - 1)
        for i in range(n - 1):
            if closest[i] == i + 1:
                forward[i] = 1
            else:
                forward[i] = nums[i + 1] - nums[i]

        backward = [0] * n
        for i in range(1, n):
            if closest[i] == i - 1:
                backward[i] = 1
            else:
                backward[i] = nums[i] - nums[i - 1]

        pref_forward = [0] * (n + 1)
        for i in range(n - 1):
            pref_forward[i + 1] = pref_forward[i] + forward[i]

        pref_backward = [0] * (n + 1)
        for i in range(1, n):
            pref_backward[i + 1] = pref_backward[i] + backward[i]

        answer = []

        for left, right in queries:
            if left < right:
                answer.append(
                    pref_forward[right] - pref_forward[left]
                )
            elif left > right:
                answer.append(
                    pref_backward[left + 1] - pref_backward[right + 1]
                )
            else:
                answer.append(0)

        return answer

The implementation follows the algorithm directly.

The first section computes the closest array using only adjacent differences. Since the array is strictly increasing, the difference to the left neighbor and the difference to the right neighbor are easy to compute.

The next two sections construct the forward and backward crossing cost arrays. These arrays encode the cheapest cost needed to cross each adjacent boundary in a specific direction.

After that, prefix sums are built. Once prefix sums exist, every query becomes a simple subtraction of two prefix values.

Finally, each query is processed independently in constant time.

Go Solution

func minCost(nums []int, queries [][]int) []int {
	n := len(nums)

	closest := make([]int, n)

	closest[0] = 1
	closest[n-1] = n - 2

	for i := 1; i < n-1; i++ {
		leftDiff := nums[i] - nums[i-1]
		rightDiff := nums[i+1] - nums[i]

		if leftDiff <= rightDiff {
			closest[i] = i - 1
		} else {
			closest[i] = i + 1
		}
	}

	forward := make([]int64, n-1)
	for i := 0; i < n-1; i++ {
		if closest[i] == i+1 {
			forward[i] = 1
		} else {
			forward[i] = int64(nums[i+1] - nums[i])
		}
	}

	backward := make([]int64, n)
	for i := 1; i < n; i++ {
		if closest[i] == i-1 {
			backward[i] = 1
		} else {
			backward[i] = int64(nums[i] - nums[i-1])
		}
	}

	prefForward := make([]int64, n+1)
	for i := 0; i < n-1; i++ {
		prefForward[i+1] = prefForward[i] + forward[i]
	}

	prefBackward := make([]int64, n+1)
	for i := 1; i < n; i++ {
		prefBackward[i+1] = prefBackward[i] + backward[i]
	}

	ans := make([]int, len(queries))

	for idx, q := range queries {
		l, r := q[0], q[1]

		var cost int64

		if l < r {
			cost = prefForward[r] - prefForward[l]
		} else if l > r {
			cost = prefBackward[l+1] - prefBackward[r+1]
		} else {
			cost = 0
		}

		ans[idx] = int(cost)
	}

	return ans
}

The Go version mirrors the Python implementation closely.

The primary difference is that prefix sums and intermediate costs are stored using int64. Although the final answer fits within the problem constraints, using 64 bit arithmetic prevents overflow when summing many large differences.

Slices are used for all arrays, and no special handling for nil slices is required because all arrays are allocated with known sizes.

Worked Examples

Example 1

nums = [-5, -2, 3]

Differences:

Index Left Diff Right Diff Closest
0 - 3 1
1 3 5 0
2 5 - 1

So:

closest = [1, 0, 1]

Forward costs:

Boundary Cost
0→1 1
1→2 5 
forward = [1, 5]
prefForward = [0, 1, 6, 6]

Backward costs:

Boundary Cost
1→0 1
2→1 1 
backward = [0, 1, 1]
prefBackward = [0, 0, 1, 2]

Query [0,2]:

prefForward[2] - prefForward[0]
= 6 - 0
= 6

Query [2,0]:

prefBackward[3] - prefBackward[1]
= 2 - 0
= 2

Query [1,2]:

prefForward[2] - prefForward[1]
= 6 - 1
= 5

Result:

[6, 2, 5]

Example 2

nums = [0,2,3,9]

Closest indices:

closest = [1,2,1,2]

Forward costs:

[1,1,6]

Prefix:

[0,1,2,8,8]

Backward costs:

[0,2,1,1]

Prefix:

[0,0,2,3,4]

Query [3,0]:

4 - 0 = 4

Query [1,2]:

2 - 1 = 1

Query [2,0]:

3 - 0 = 3

Result:

[4,1,3]

Complexity Analysis

Measure Complexity Explanation
Time O(n + q) One preprocessing pass and O(1) per query
Space O(n) Closest arrays, cost arrays, and prefix sums

The preprocessing stage scans the array a constant number of times, which requires linear time. Each query is answered using a constant number of prefix sum lookups and subtractions. Therefore the total running time is O(n + q). The auxiliary arrays used during preprocessing require linear space.

Test Cases

sol = Solution()

# Example 1
assert sol.minCost(
    [-5, -2, 3],
    [[0, 2], [2, 0], [1, 2]]
) == [6, 2, 5]

# Example 2
assert sol.minCost(
    [0, 2, 3, 9],
    [[3, 0], [1, 2], [2, 0]]
) == [4, 1, 3]

# Smallest valid array
assert sol.minCost(
    [1, 10],
    [[0, 1], [1, 0]]
) == [1, 1]

# Same start and end
assert sol.minCost(
    [1, 5, 10],
    [[0, 0], [1, 1], [2, 2]]
) == [0, 0, 0]

# Equal adjacent differences, tie goes left
assert sol.minCost(
    [0, 5, 10],
    [[2, 0]]
) == [2]

# Large gaps
assert sol.minCost(
    [0, 1, 1000, 2000],
    [[0, 3]]
) == [1001]

# Forward travel across many boundaries
assert sol.minCost(
    [0, 2, 3, 4, 100],
    [[0, 4]]
) == [98]

# Backward travel across many boundaries
assert sol.minCost(
    [0, 2, 3, 4, 100],
    [[4, 0]]
) == [4]

# Mixed queries
assert sol.minCost(
    [0, 3, 7, 20],
    [[0, 3], [3, 0], [1, 2]]
) == [17, 4, 4]

Test Summary

Test Why
Example 1 Verifies sample behavior
Example 2 Verifies sample behavior in both directions
Two elements Smallest valid input size
Same index queries Checks zero cost answers
Equal adjacent differences Validates tie-breaking rule
Large gaps Ensures difference costs are handled correctly
Long forward path Tests multiple forward boundary crossings
Long backward path Tests multiple backward boundary crossings
Mixed queries Exercises both directions simultaneously

Edge Cases

Query Starts and Ends at the Same Index

When li == ri, no movement is necessary. A common bug is accidentally performing a prefix subtraction that crosses an invalid range. The implementation explicitly checks for this condition and returns zero immediately.

Equal Adjacent Differences

Suppose:

nums = [0, 5, 10]

For index 1, both neighboring differences equal 5. The problem specifies that ties must choose the smaller index. The implementation uses:

if left_diff <= right_diff

which correctly selects the left neighbor during ties.

Boundary Indices

The first and last indices only have one adjacent neighbor. Attempting to apply the normal interior logic would cause out of bounds access. The implementation handles index 0 and index n-1 separately before processing interior indices.

Very Large Values

Array values may be as large as 10^9 in magnitude. Summing many differences across a path can exceed 32 bit integer limits. The Go implementation stores accumulated costs in int64, ensuring safe arithmetic during prefix sum computation.