medium Minimum Absolute Difference Queries

Problem Statement

The minimum absolute difference of an array is defined as the smallest value of |a[i] - a[j]|, where 0 <= i < j < a.length and a[i] != a[j]. If all elements in the subarray are identical, the minimum absolute difference is -1.

For example, the minimum absolute difference of the array [1,7,3,4,5] is |3 - 4| = 1.

You are given an nums array of integers and the array queries where queries[i] = [l_i, r_i]. For each query i, calculate the minimum absolute difference of the subarray nums[l_i...r_i] (inclusive).

Return an array ans where ans[i] is the answer to the i^th 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.

Examples

1. Example 1:

   • Input: nums = [7, 1, 3, 3, 5], queries = [[0, 2], [1, 4], [2, 4]]
   • Expected Output: [2, 2, 2]
   • Explanation:
     • For the first query [0, 2], the subarray is [7, 1, 3]. The minimum absolute difference is |1 - 3| = 2.
     • For the second query [1, 4], the subarray is [1, 3, 3, 5]. The minimum absolute difference is |3 - 3| = 0 but since the values must be different, the smallest difference is |1 - 3| = 2.
     • For the third query [2, 4], the subarray is [3, 3, 5]. The minimum absolute difference is |3 - 5| = 2.

2. Example 2:

   • Input: nums = [4, 8, 2, 6, 10], queries = [[0, 3], [2, 4], [0, 4]]
   • Expected Output: [2, 4, 2]
   • Explanation:
     • For the first query [0, 3], the subarray is [4, 8, 2, 6]. The minimum absolute difference is |4 - 6| = 2.
     • For the second query [2, 4], the subarray is [2, 6, 10]. The minimum absolute difference is |6 - 10| = 4.
     • For the third query [0, 4], the subarray is [4, 8, 2, 6, 10]. The minimum absolute difference is |4 - 6| = 2.

3. Example 3:

   • Input: nums = [12, 3, 15, 9, 3], queries = [[0, 2], [1, 3], [0, 4]]
   • Expected Output: [3, 6, 3]
   • Explanation:
     • For the first query [0, 2], the subarray is [12, 3, 15]. The minimum absolute difference is |12 - 15| = 3.
     • For the second query [1, 3], the subarray is [3, 15, 9]. The minimum absolute difference is |9 - 15| = 6.
     • For the third query [0, 4], the subarray is [12, 3, 15, 9, 3]. The minimum absolute difference is |12 - 15| = 3.

Constraints:

• 2 <= nums.length <= 10⁵
• 1 <= nums[i] <= 100
• 1 <= queries.length <= 2 * 10⁴
• 0 <= l_i < r_i < nums.length

Solution

To solve this problem, we utilize Mo's algorithm. This approach is effective for answering multiple range queries on an array efficiently. First, we define a Query class to represent each query, including its start and end indices along with its original position in the input list. We then calculate a block size, which is the square root of the array's length, to help in organizing the queries. The queries are sorted first by the block of their starting index and then by their ending index within each block. This sorting minimizes the adjustments needed when moving from one query to the next, reducing the overall processing time.

Once the queries are sorted, we process them by adjusting the current range of elements to match the range specified by each query. We maintain a frequency count of the elements within this range to help quickly calculate the minimum absolute difference between any two distinct elements. By incrementally adjusting the range and updating the frequency counts, we can efficiently compute the required minimum difference for each query. The results are then stored in an array corresponding to the original order of the queries, which is returned as the final output.

Step-by-Step Algorithm

1. Initialization:

   • Define a Query class to hold the start (leftIndex), end (rightIndex), and original index (queryIndex) of each query.
   • Initialize an empty list called queryList to store the queries in the desired order.
   • Calculate the block size as the square root of the length of the nums array. This block size helps in efficiently sorting and processing the queries using Mo's algorithm.

2. Preparing and Sorting Queries:

   • Iterate through each query in the queries array.
   • For each query, create a new Query object with the corresponding leftIndex, rightIndex, and the query's original index.
   • Add the Query object to queryList.
   • Sort queryList based on the block of leftIndex. If two queries belong to the same block, further sort them by rightIndex. Sorting ensures minimal adjustments to the range during query processing.

3. Setting up the Frequency Array and Pointers:

   • Initialize an array called frequencyCount of size 101, which will track the frequency of each number (assuming numbers range from 1 to 100) within the current range.
   • Initialize two pointers, leftPointer and rightPointer, both starting at the beginning of the first query’s range. Set the first element’s frequency in frequencyCount.

4. Processing Each Query:

   • Iterate over each Query in the sorted queryList.
   • For each Query, adjust the range [leftPointer, rightPointer] to match the query’s leftIndex and rightIndex.
     • Adjusting the Left Pointer:
       • If leftPointer is greater than leftIndex, decrement leftPointer and update the frequency of the element at the new leftPointer.
       • If leftPointer is less than leftIndex, increment leftPointer and update the frequency of the element at the old leftPointer.
     • Adjusting the Right Pointer:
       • If rightPointer is less than rightIndex, increment rightPointer and update the frequency of the element at the new rightPointer.
       • If rightPointer is greater than rightIndex, decrement rightPointer and update the frequency of the element at the old rightPointer.
   • After adjusting the range, calculate the minimum absolute difference within the current range:
     • Initialize a variable previousNumber to -1 to track the last seen number with a non-zero frequency.
     • Initialize minDifference to Integer.MAX_VALUE to store the smallest difference found.
     • Traverse through the frequencyCount array from 1 to 100. For each number with a non-zero frequency:
       • If previousNumber is not -1, calculate the absolute difference between the current number and previousNumber.
       • Update minDifference if the calculated difference is smaller.
       • Set previousNumber to the current number.
   • If no valid difference is found (i.e., all elements are identical), set the result to -1. Otherwise, store the minDifference in the results array.

5. Returning the Results:

   • Return the results array, which contains the answer for each query in the order they were provided.

Algorithm Walkthrough

Input: nums = [7, 1, 3, 3, 5], queries = [[0, 2], [1, 4], [2, 4]]

1. Initialization:

   • Define the Query class.
   • Calculate the block size as ( \sqrt{5} \approx 2 ).

2. Preparing and Sorting Queries:

   • Convert queries to queryList:
     • Query 1: Query(0, 2, 0)
     • Query 2: Query(1, 4, 1)
     • Query 3: Query(2, 4, 2)
   • Sort queryList:
     • All queries belong to the first block (leftIndex / blockSize = 0), so they are further sorted by rightIndex.
     • queryList = [Query(0, 2, 0), Query(1, 4, 1), Query(2, 4, 2)]

3. Setting up the Frequency Array and Pointers:

   • Initialize frequencyCount to [0] * 101.
   • Set leftPointer and rightPointer to 0.
   • Increment the frequency of nums[0] (which is 7), so frequencyCount[7] = 1.

4. Processing Queries

a. Processing Query 1 (Query(0, 2, 0)):

• Initial Range: leftPointer = 0, rightPointer = 0.
• Initial Frequency Map: {7: 1}
• Adjusting Range:
  • Increment rightPointer to 1, include nums[1] = 1.
  • Updated Frequency Map: {7: 1, 1: 1}
  • Increment rightPointer to 2, include nums[2] = 3.
  • Updated Frequency Map: {7: 1, 1: 1, 3: 1}
• Calculating the Minimum Difference:
  • Traverse the map:
    • First number: 1 (no previous number yet).
    • Next number: 3. Absolute difference: |3 - 1| = 2. Set minDifference = 2.
    • Next number: 7. Absolute difference: |7 - 3| = 4. minDifference remains 2.
  • Result for Query 1: 2

b. Processing Query 2 (Query(1, 4, 1)):

• Initial Range: leftPointer = 0, rightPointer = 2.
• Initial Frequency Map: {7: 1, 1: 1, 3: 1}
• Adjusting Range:
  • Increment leftPointer to 1, remove nums[0] = 7.
  • Updated Frequency Map: {1: 1, 3: 1}
  • Increment rightPointer to 3, include nums[3] = 3.
  • Updated Frequency Map: {1: 1, 3: 2}
  • Increment rightPointer to 4, include nums[4] = 5.
  • Updated Frequency Map: {1: 1, 3: 2, 5: 1}
• Calculating the Minimum Difference:
  • Traverse the map:
    • First number: 1 (no previous number yet).
    • Next number: 3. Absolute difference: |3 - 1| = 2. Set minDifference = 2.
    • Next number: 5. Absolute difference: |5 - 3| = 2. minDifference remains 2.
  • Result for Query 2: 2

c. Processing Query 3 (Query(2, 4, 2)):

• Initial Range: leftPointer = 1, rightPointer = 4.
• Initial Frequency Map: {1: 1, 3: 2, 5: 1}
• Adjusting Range:
  • Increment leftPointer to 2, remove nums[1] = 1.
  • Updated Frequency Map: {3: 2, 5: 1}
• Calculating the Minimum Difference:
  • Traverse the map:
    • First number: 3 (no previous number yet).
    • Next number: 5. Absolute difference: |5 - 3| = 2. Set minDifference = 2.
  • Result for Query 3: 2

1. Final Results:
   • The results array is [2, 2, 2].

import java.util.*;

class Solution {

  // A class to represent a query
  static class Query {

    int leftIndex, rightIndex, queryIndex;

    // Constructor to initialize a query
    Query(int leftIndex, int rightIndex, int queryIndex) {
      this.leftIndex = leftIndex;
      this.rightIndex = rightIndex;
      this.queryIndex = queryIndex;
    }
  }

  // Method to adjust the current range [L, R] to match the query's range [li, ri]
  private void adjustRange(
    int[] leftPointer,
    int[] rightPointer,
    Query currentQuery,
    int[] frequencyCount,
    int[] nums
  ) {
    // Expanding or contracting the left side of the range
    while (leftPointer[0] > currentQuery.leftIndex) {
      leftPointer[0]--;
      frequencyCount[nums[leftPointer[0]]]++;
    }

    while (leftPointer[0] < currentQuery.leftIndex) {
      frequencyCount[nums[leftPointer[0]]]--;
      leftPointer[0]++;
    }

    // Expanding or contracting the right side of the range
    while (rightPointer[0] < currentQuery.rightIndex) {
      rightPointer[0]++;
      frequencyCount[nums[rightPointer[0]]]++;
    }

    while (rightPointer[0] > currentQuery.rightIndex) {
      frequencyCount[nums[rightPointer[0]]]--;
      rightPointer[0]--;
    }
  }

  // Method to find the minimum absolute difference for each query
  public int[] minDiff(int[] nums, int[][] queries) {
    int q = queries.length; // Number of queries
    List<Query> queryList = new ArrayList<>();

    // Prepare the list of queries with their respective indices
    for (int i = 0; i < q; i++) {
      int[] query = queries[i];
      queryList.add(new Query(query[0], query[1], i));
    }

    // Calculate block size for Mo's algorithm
    int blockSize = (int) Math.sqrt(nums.length);

    // Sort the queries first by block, then by right index within the block
    queryList.sort((a, b) -> {
      if (a.leftIndex / blockSize != b.leftIndex / blockSize) return (
        a.leftIndex / blockSize - b.leftIndex / blockSize
      );
      return a.rightIndex - b.rightIndex;
    });

    // Initialize frequency array to keep track of occurrences in the current range
    int[] frequencyCount = new int[101]; // Assume numbers are in the range 1 to 100
    int[] results = new int[q]; // Array to store results for each query

    // Initialize pointers for the current range
    int[] leftPointer = { queryList.get(0).leftIndex };
    int[] rightPointer = { queryList.get(0).leftIndex };
    frequencyCount[nums[queryList.get(0).leftIndex]]++; // Initialize with the first element

    // Process each query
    for (Query query : queryList) {
      // Adjust the range to match the current query's range
      adjustRange(leftPointer, rightPointer, query, frequencyCount, nums);

      // Calculate the minimum absolute difference in the current range
      int previousNumber = -1; // To store the last number we encountered in the range
      int minDifference = Integer.MAX_VALUE; // To store the minimum difference

      // Traverse through the possible numbers and calculate the minimum difference
      for (int j = 1; j <= 100; j++) {
        if (frequencyCount[j] > 0) {
          if (previousNumber != -1) {
            minDifference = Math.min(
              minDifference,
              Math.abs(j - previousNumber)
            );
          }
          previousNumber = j; // Update previous number to the current one
        }
      }

      // If no valid difference found, return -1, else return the minimum difference
      results[query.queryIndex] = (minDifference == Integer.MAX_VALUE)
        ? -1
        : minDifference;
    }

    return results; // Return the results array containing answers for all queries
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    int[] nums1 = { 7, 1, 3, 3, 5 };
    int[][] queries1 = { { 0, 2 }, { 1, 4 }, { 2, 4 } };
    int[] result1 = solution.minDiff(nums1, queries1);
    System.out.println(Arrays.toString(result1)); // Expected output: [2, 2, 2]

    // Example 2
    int[] nums2 = { 4, 8, 2, 6, 10 };
    int[][] queries2 = { { 0, 3 }, { 2, 4 }, { 0, 4 } };
    int[] result2 = solution.minDiff(nums2, queries2);
    System.out.println(Arrays.toString(result2)); // Expected output: [2, 4, 2]

    // Example 3
    int[] nums3 = { 12, 3, 15, 9, 3 };
    int[][] queries3 = { { 0, 2 }, { 1, 3 }, { 0, 4 } };
    int[] result3 = solution.minDiff(nums3, queries3);
    System.out.println(Arrays.toString(result3)); // Expected output: [3, 6, 3]
  }
}

Complexity Analysis

Time Complexity

1. Sorting the Queries: The queries are sorted by their blocks and by their right index within the block. Sorting takes , where (q) is the number of queries.

2. Processing Each Query:

   • The Mo's algorithm takes time.
   • For each adjustment, the algorithm may need to update the frequency count for a few elements and find the minimum difference, which requires iterating over at most 100 possible numbers (since the number values are in the range 1 to 100). This part takes , which is effectively .

The overall time complexity is , according to Mo's algorithm.

Space Complexity

• Frequency Array: The frequency array frequencyCount uses space, which simplifies to (O(1)) since the number values are bounded.
• Result Array: The result array results uses space to store the answer for each query.
• Query List: The list of queries (queryList) uses space.
• Other Variables: The left and right pointers use space.