1906. Minimum Absolute Difference Queries LeetCode Solution

Example 1:

Input: nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]]
Output: [2,1,4,1]
Explanation: The queries are processed as follows:
– queries[0] = [0,1]: The subarray is [1,3] and the minimum absolute difference is |1-3| = 2.
– queries[1] = [1,2]: The subarray is [3,4] and the minimum absolute difference is |3-4| = 1.
– queries[2] = [2,3]: The subarray is [4,8] and the minimum absolute difference is |4-8| = 4.
– queries[3] = [0,3]: The subarray is [1,3,4,8] and the minimum absolute difference is |3-4| = 1.

Example 2:

Input: nums = [4,5,2,2,7,10], queries = [[2,3],[0,2],[0,5],[3,5]]
Output: [-1,1,1,3]
Explanation: The queries are processed as follows:
– queries[0] = [2,3]: The subarray is [2,2] and the minimum absolute difference is -1 because all the
elements are the same.
– queries[1] = [0,2]: The subarray is [4,5,2] and the minimum absolute difference is |4-5| = 1.
– queries[2] = [0,5]: The subarray is [4,5,2,2,7,10] and the minimum absolute difference is |4-5| = 1.
– queries[3] = [3,5]: The subarray is [2,7,10] and the minimum absolute difference is |7-10| = 3.

Constraints:

2 <= nums.length <= 105
1 <= nums[i] <= 100
1 <= queries.length <= 2 * 104
0 <= li < ri < nums.length

Complexity Analysis

• Time Complexity: O(q \cdot 100 \cdot \log n) = O(q\log n)
• Space Complexity: O(n + q)

1906. Minimum Absolute Difference Queries LeetCode Solution in C++

class Solution {
 public:
  vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) {
    vector<vector<int>> numToIndices(101);

    for (int i = 0; i < nums.size(); ++i)
      numToIndices[nums[i]].push_back(i);

    if (numToIndices[nums[0]].size() == nums.size())
      return vector<int>(queries.size(), -1);

    vector<int> ans;

    for (const vector<int>& query : queries) {
      const int l = query[0];
      const int r = query[1];
      int prevNum = -1;
      int minDiff = 101;
      for (int num = 1; num <= 100; ++num) {
        const auto& indices = numToIndices[num];
        const auto it = ranges::lower_bound(indices, l);
        if (it == indices.cend() || *it > r)
          continue;
        if (prevNum != -1)
          minDiff = min(minDiff, num - prevNum);
        prevNum = num;
      }
      ans.push_back(minDiff == 101 ? -1 : minDiff);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

1906. Minimum Absolute Difference Queries LeetCode Solution in Java

class Solution {
  public int[] minDifference(int[] nums, int[][] queries) {
    int[] ans = new int[queries.length];
    List<Integer>[] numToIndices = new List[101];

    for (int i = 1; i <= 100; ++i)
      numToIndices[i] = new ArrayList<>();

    for (int i = 0; i < nums.length; ++i)
      numToIndices[nums[i]].add(i);

    if (numToIndices[nums[0]].size() == nums.length) {
      Arrays.fill(ans, -1);
      return ans;
    }

    for (int i = 0; i < queries.length; ++i) {
      final int l = queries[i][0];
      final int r = queries[i][1];
      int prevNum = -1;
      int minDiff = 101;
      for (int num = 1; num <= 100; ++num) {
        List<Integer> indices = numToIndices[num];
        final int j = firstGreaterEqual(indices, l);
        if (j == indices.size() || indices.get(j) > r)
          continue;
        if (prevNum != -1)
          minDiff = Math.min(minDiff, num - prevNum);
        prevNum = num;
      }
      ans[i] = minDiff == 101 ? -1 : minDiff;
    }

    return ans;
  }

  private int firstGreaterEqual(List<Integer> A, int target) {
    final int i = Collections.binarySearch(A, target);
    return i < 0 ? -i - 1 : i;
  }
}
// code provided by PROGIEZ

1906. Minimum Absolute Difference Queries LeetCode Solution in Python

class Solution:
  def minDifference(
      self,
      nums: list[int],
      queries: list[list[int]],
  ) -> list[int]:
    numToIndices = [[] for _ in range(101)]

    for i, num in enumerate(nums):
      numToIndices[num].append(i)

    if len(numToIndices[nums[0]]) == len(nums):
      return [-1] * len(queries)

    ans = []

    for l, r in queries:
      prevNum = -1
      minDiff = 101
      for num in range(1, 101):
        indices = numToIndices[num]
        i = bisect_left(indices, l)
        if i == len(indices) or indices[i] > r:
          continue
        if prevNum != -1:
          minDiff = min(minDiff, num - prevNum)
        prevNum = num
      ans.append(-1 if minDiff == 101 else minDiff)

    return ans
 # code by PROGIEZ

Additional Resources