3919. Minimum Cost to Move Between Indices

SourceWeekly Contest 500 Q3DifficultyMediumRating1776

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