1906. Minimum Absolute Difference Queries

Problem Description

In this LeetCode problem, we're required to find the minimum absolute difference of subarrays within a given integer array nums. A subarray is specified through a range given in queries, where each query is in the form [l, r], meaning the subarray ranges from the index l to r inclusive.

The minimum absolute difference for a subarray is determined by finding the smallest absolute value of the difference between any two distinct elements within that subarray. It's important to note two key conditions:

1. We can only compare different elements, so the same elements should be disregarded when calculating the differences (e.g., |5 - 5|, which equals 0, should not be considered).
2. If all elements within the subarray are the same, the minimum absolute difference is -1 as there is no pair of different numbers to compare.

The task is to return an array of integers where each element is the result of computing the minimum absolute difference for the corresponding query.

Intuition

To solve this problem, an efficient approach is to use prefix sums. Prefix sums allow us to quickly calculate the sum of a range of numbers in an array, which is a useful strategy when you need to make multiple range queries.

Since we need to find the minimum absolute difference and not the sum, we modify the prefix sums approach to count the occurrences of each element in a range. This will help us to identify which elements are present in each subarray without having to traverse the subarray repeatedly for every query. We can process the nums array to create a prefix sum matrix, where each entry pre_sum[i][j] represents the number of times the number j has appeared in nums up to the i-th index.

Once we have this prefix sum matrix built, we can then handle the queries. For each query [l, r], we look at the prefix sum matrix to find which numbers are present in the subarray from l to r. We traverse the range of possible values, and when we find a number present in the subarray, we compare it with the last number found to calculate the difference and keep track of the smallest difference encountered.

If at least two different numbers are found in the subarray, we would have a valid minimum difference. If not, the result for that particular query would be -1, indicating that all elements were the same in the subarray.

Solution Approach

The implemented solution follows a few steps, using the concept of prefix sums and last seen elements:

1. Initialization: The first step involves initializing a prefix sum matrix pre_sum of size (m+1) x 101, where m is the number of elements in nums, and 101 is used because the numbers are constrained between 1 to 100. The pre_sum matrix is used to keep track of the count of each number up to a certain index.

2. Building the Prefix Sum Matrix: The code populates the pre_sum matrix using two nested loops:

   • The outer loop goes from 1 to m (inclusive), iterating over the input array nums.
   • The inner loop goes from 1 to 100, iterating over all possible number values within the constraints.

   At each iteration, the code checks if the number j is the same as the i-th element of nums. If it matches (nums[i - 1] == j), the code increments the count for that number at the current prefix index. This populates pre_sum such that pre_sum[i][j] represents the number of times the number j has appeared from the start of nums up to index i-1.

3. Handling Queries: For each query defined by [l, r], the code translates it to a range in pre_sum as [left, right+1] to use one-based indexing. It then initializes variables t to hold the maximum possible value (infinity at the start as a placeholder for no result) and last to -1 as a placeholder for the previously encountered number in the subarray.

4. Processing each Query: For each query, the code iterates from 1 to 100 to check which numbers are present in the subarray and to calculate their difference. If pre_sum[right][j] - pre_sum[left][j] > 0, it means that the number j is present in the subarray. We then calculate the difference with the last seen number and update t with the minimum difference. last is updated to the current number j to be used in the next iterations.

5. Handling impossible cases: After processing the differences, if t remains as infinity (the code uses inf which is a constant representing an infinite value), it means that no valid minimum absolute difference could be calculated (there were not at least two different numbers), and thus t is set to -1.

6. Storing the Result: The minimum difference t calculated for each query is then appended to the result list ans.

7. Returning the Result: Finally, after processing all queries, the list ans containing all the minimum differences for each query is returned.

Through these steps, the algorithm efficiently computes the minimum absolute difference for multiple subarray queries in an array using prefix sums, resulting in reduced time complexity compared to a brute-force approach.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach:

Consider the integer array nums = [1,3,4,8] and queries = [[0,1],[1,2],[2,3]]. We aim to find the minimum absolute difference for the subarrays specified by each pair of indices l and r in queries.

Step 1: Initialize the prefix sum matrix pre_sum which has the size (n+1) x 101 (where n is the length of nums, to handle zero indexing). Since nums has 4 elements, pre_sum will be a 5x101 matrix as shown below:

1pre_sum = [[0]*101 for i in range(5)]  // 5 rows, 101 columns filled with 0

Step 2: Build the prefix sum matrix by iterating over nums and updating the counts for each number between 1 and 100.

After building, let's say the matrix looks like this (trimmed for brevity):

1pre_sum:
2[0, ..., 0]  // Base row for ease of calculation, all zeroes
3[0, 1, 0, 0, 0, 0, 0, 0, 0, ..., 0] // nums[0] (1) has appeared once up to index 0
4[0, 1, 0, 1, 0, 0, 0, 0, 0, ..., 0] // nums[1] (3) has appeared once up to index 1
5[0, 1, 0, 1, 1, 0, 0, 0, 0, ..., 0] // nums[2] (4) has appeared once up to index 2
6[0, 1, 0, 1, 1, 0, 0, 0, 1, ..., 0] // nums[3] (8) has appeared once up to index 3

Step 3: Handle the queries [0, 1], [1, 2], and [2, 3].

For the query [0, 1], the relevant subarray is [1,3]. Looking at the pre_sum matrix:

1pre_sum[1+1][1] - pre_sum[0][1] = 1 - 0 = 1, so `1` appears in the subarray.
2pre_sum[1+1][3] - pre_sum[0][3] = 1 - 0 = 1, so `3` appears in the subarray.
3...

Since both 1 and 3 are present, we calculate the absolute difference: |1 - 3| = 2. So for the first query, the minimum absolute difference is 2.

For the query [1, 2], the relevant subarray is [3,4]. Using the similar approach as above, we find that 3 and 4 are present, and the minimum absolute difference is |3 - 4| = 1. So for the second query, the minimum absolute difference is 1.

For the query [2, 3], the relevant subarray is [4,8]. Similarly, 4 and 8 are present, and the minimum absolute difference is |4 - 8| = 4. So for the third query, the minimum absolute difference is 4.

Step 4: After processing each query, we compile the results into the answer list ans = [2, 1, 4].

Step 5: Return ans.

By utilizing the prefix sum approach, we avoid recalculating the presence of each number for every subarray query, which saves computation time. The final answer gives the minimum absolute difference for each of the subarrays specified by queries.

Solution Implementation

Time and Space Complexity

Time Complexity

The given code involves two main parts: calculating the prefix sums for each number in the range [1, 100] for each index in nums, and then processing each query to find the minimum difference between consecutive numbers present within the query range.

1. Calculating Prefix Sums: The code constructs a 2-D array pre_sum of size (m+1) x 101, where each entry pre_sum[i][j] represents the number of occurrences of the number j up to the i-th position in nums. Iterating through all values of nums and all numbers [1, 100] to populate this array has a complexity of O(m * 100) since we iterate through 100 numbers for each of the m elements in nums.

2. Processing Queries: For each of the n queries, the code looks for the smallest difference between consecutive numbers that are present in the specified range. Since the numbers range from 1 to 100, we iterate 100 times for each query to determine this. Therefore, the complexity for processing all queries is O(n * 100).

Combining both parts, the total time complexity is O(m * 100 + n * 100), which simplifies to O(m + n) considering that 100 is a constant factor and can be omitted in Big O notation.

Space Complexity

The space complexity is determined by the storage required for the pre_sum array and the output array ans:

1. Prefix Sum Array (pre_sum): The size of the pre_sum array is (m+1) x 101, so the space complexity contributed by this array is O(m * 101), which is O(m) as 101 is a constant factor.

2. Output Array (ans): The size of the output array is n, correlating directly with the number of queries. Therefore, it contributes O(n) to space complexity.

Thus, the total space complexity of the code is O(m + n) combining the prefix sum array and the output array.

Learn more about how to find time and space complexity quickly using problem constraints.