Minimum cost to move between indices

50.2% acceptance

May 13, 2026

You are given an integer array nums where nums is strictly increasing. For each index x, let closest(x) be the adjacent index 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).

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
    let n = nums.len();
    let g: Vec<i64> = (0..n - 1).map(|i| (nums[i + 1] as i64 - nums[i] as i64)).collect();
    let dir = |i: usize| -> i32 {
      if i == 0 { 1 }
      else if i == n - 1 { -1 }
      else if g[i - 1] <= g[i] { -1 } else { 1 }
    };
    let mut prefix_right = vec![0i64; n];
    for i in 0..n - 1 {
      let cost = if dir(i) == 1 { 1 } else { g[i] };
      prefix_right[i + 1] = prefix_right[i] + cost;
    }
    let mut prefix_left = vec![0i64; n];
    for i in 1..n {
      let cost = if dir(i) == -1 { 1 } else { g[i - 1] };
      prefix_left[i] = prefix_left[i - 1] + cost;
    }
    let mut ans = Vec::with_capacity(queries.len());
    for q in queries {
      let l = q[0] as usize;
      let r = q[1] as usize;
      let cost = if l == r {
        0
      } else if l < r {
        prefix_right[r] - prefix_right[l]
      } else {
        prefix_left[l] - prefix_left[r]
      };
      ans.push(cost as i32);
    }
    ans
  }
}