Minimum absolute difference queries

Array Prefix Sum

45.7% acceptance

Feb 25, 2026

552

The minimum absolute difference of an array a is defined as the minimum value of |a[i] - a[j]|, where 0 <= i < j < a.length and a[i] != a[j]. If all elements of a are the same, the minimum absolute difference is -1. For example, the minimum absolute difference of the array [5,2,3,7,2] is |2 - 3| = 1. Note that it is not 0 because a[i] and a[j] must be different. You are given an integer array nums and the array queries where queries[i] = [li, ri]. For each query i, compute the minimum absolute difference of the subarray nums[li...ri] containing the elements of nums between the 0-based indices li and ri (inclusive). Return an array ans where ans[i] is the answer to the ith query. A subarray is a contiguous sequence of elements in an array. The value of |x| is defined as: x if x >= 0. -x if x < 0.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_difference(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
    let n = nums.len();
    // prefix[i][v] = count of value v in nums[0..i]
    let mut prefix = vec![[0i32; 101]; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i];
      prefix[i + 1][nums[i] as usize] += 1;
    }
    queries.iter().map(|q| {
      let (l, r) = (q[0] as usize, q[1] as usize);
      let mut min_diff = i32::MAX;
      let mut prev = -1i32;
      for v in 1..=100 {
        if prefix[r + 1][v] - prefix[l][v] > 0 {
          if prev != -1 {
            min_diff = min_diff.min(v as i32 - prev);
          }
          prev = v as i32;
        }
      }
      if min_diff == i32::MAX { -1 } else { min_diff }
    }).collect()
  }
}