3919. Minimum Cost to Move Between Indices

Description

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] = [l_i, r_i].

For each query, calculate the minimum total cost to move from index l_i to index r_i.

Return an integer array ans, where ans[i] is the answer for the i^th 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 <= 10⁵
-10⁹ <= nums[i] <= 10⁹
nums is strictly increasing
1 <= queries.length <= 10⁵
queries[i] = [l_i, r_i]
0 <= l_i, r_i < nums.length

Solutions

Solution 1

Thinking

The array is strictly increasing and there are up to \(10^5\) queries, so we cannot simulate each walk on \([l,r]\). The cost of one adjacent step is determined by a local triple of gaps, and the left-to-right rule is not the same as the opposite direction.

Precompute a rightward cost \(c_1\) and a leftward cost \(c_2\) on every adjacent edge, then store their prefix sums \(s_1\) and \(s_2\). A query with \(l<r\) reads \(s_1[r]-s_1[l]\); otherwise it reads \(s_2[l]-s_2[r]\).

Each query is then \(O(1)\) after an \(O(n)\) preprocess.

Python3JavaC++GoTypeScript

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;
    }
};

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
}

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;
}

3919. Minimum Cost to Move Between Indices

Description

Solutions

Solution 1

Comments