1906. Minimum Absolute Difference Queries

MediumArrayHash Table

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:

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).
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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

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:

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.
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.
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.
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.
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.
Storing the Result: The minimum difference t calculated for each query is then appended to the result list ans.
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.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

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:

pre_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):

pre_sum:
[0, ..., 0]  // Base row for ease of calculation, all zeroes
[0, 1, 0, 0, 0, 0, 0, 0, 0, ..., 0] // nums[0] (1) has appeared once up to index 0
[0, 1, 0, 1, 0, 0, 0, 0, 0, ..., 0] // nums[1] (3) has appeared once up to index 1
[0, 1, 0, 1, 1, 0, 0, 0, 0, ..., 0] // nums[2] (4) has appeared once up to index 2
[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:

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

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

1from math import inf
2
3class Solution:
4    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:
5        # Get the lengths of the input list and the queries
6        num_count = len(nums)
7        query_count = len(queries)
8      
9        # Initialize a prefix sum array with zeros
10        # This array will store the counts of each number from 1 to 100 up to index i
11        prefix_sum = [[0] * 101 for _ in range(num_count + 1)]
12      
13        # Calculate prefix sums
14        for i in range(1, num_count + 1):
15            for j in range(1, 101):
16                # Check if the current num is equal to the current value j
17                count_increment = 1 if nums[i - 1] == j else 0
18                prefix_sum[i][j] = prefix_sum[i - 1][j] + count_increment
19
20        # Prepare a list to store the answers to each query
21        results = []
22      
23        # Process each query
24        for i in range(query_count):
25            # Define the range for the current query
26            left, right = queries[i][0], queries[i][1] + 1
27          
28            # Initialize the minimum difference to positive infinity
29            min_diff = inf
30            # Initialize the last seen number variable
31            last_seen = -1
32          
33            # Loop through the range of possible values 1 to 100
34            for j in range(1, 101):
35                # If the number j is present in the current segment (between left and right)
36                if prefix_sum[right][j] - prefix_sum[left][j] > 0:
37                    # If this is not the first number we've seen, update the min_diff
38                    if last_seen != -1:
39                        min_diff = min(min_diff, j - last_seen)
40                    # Update last_seen with the current number
41                    last_seen = j
42          
43            # If min_diff is still infinity, it means no numbers are present, so set the result to -1
44            if min_diff == inf:
45                min_diff = -1
46          
47            # Append the result of the current query to the results list
48            results.append(min_diff)
49          
50        # Return the list of results
51        return results
52

1class Solution {
2    public int[] minDifference(int[] nums, int[][] queries) {
3        int numsLength = nums.length, queriesLength = queries.length;
4        // Initialize an array to store the prefix sums for each number from 1 to 100.
5        int[][] prefixSums = new int[numsLength + 1][101];
6      
7        // Fill the prefixSums array with the counts of each number up to the current index.
8        for (int i = 1; i <= numsLength; ++i) {
9            for (int num = 1; num <= 100; ++num) {
10                int presence = nums[i - 1] == num ? 1 : 0;
11                prefixSums[i][num] = prefixSums[i - 1][num] + presence;
12            }
13        }
14
15        // Initialize an array to hold the answers to each query.
16        int[] answer = new int[queriesLength]; 
17        for (int i = 0; i < queriesLength; ++i) {
18            int startRange = queries[i][0], endRange = queries[i][1] + 1;
19            int minDifference = Integer.MAX_VALUE;
20            int lastNum = -1; // Store the last seen number to calculate the difference.
21          
22            // Iterate from 1 through 100 to find the minimum difference between successive numbers.
23            for (int j = 1; j <= 100; ++j) {
24                // Check if the number j is present in the subrange [startRange, endRange)
25                if (prefixSums[endRange][j] > prefixSums[startRange][j]) {
26                    // Only update the minDifference if this is not the first number found.
27                    if (lastNum != -1) {
28                        minDifference = Math.min(minDifference, j - lastNum);
29                    }
30                    lastNum = j; // Update the lastNum to the current number.
31                }
32            }
33          
34            // If no numbers were found, set the minimum difference as -1.
35            if (minDifference == Integer.MAX_VALUE) {
36                minDifference = -1;
37            }
38            answer[i] = minDifference; // Set the answer for the current query.
39        }
40        return answer; // Return the array of answers for all queries.
41    }
42}
43

1#include <vector>
2#include <climits> // For INT_MAX
3using namespace std;
4
5class Solution {
6public:
7    vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) {
8        // Get the size of the nums vector and the number of queries
9        int numsSize = nums.size(), queriesSize = queries.size();
10        // Initialize a 2D prefix sum array
11        int prefixSum[numsSize + 1][101] = {0};
12
13        // Populate the prefix sum array
14        for (int i = 1; i <= numsSize; ++i) {
15            for (int j = 1; j <= 100; ++j) {
16                // If the current number equals j, set t to 1; otherwise, set t to 0
17                int t = (nums[i - 1] == j) ? 1 : 0;
18                // Calculate the prefix sum for number j up to index i
19                prefixSum[i][j] = prefixSum[i - 1][j] + t;
20            }
21        }
22
23        // Initialize the answer vector to store the minimum differences
24        vector<int> answer(queriesSize);
25
26        // Process each query
27        for (int i = 0; i < queriesSize; ++i) {
28            int left = queries[i][0];
29            int right = queries[i][1] + 1; // Add 1 to right to make it exclusive
30
31            // Variable to store the minimum difference
32            int minDiff = 101;
33            // Variable to store the last seen element
34            int lastSeen = -1;
35
36            // Loop over every possible integer
37            for (int j = 1; j <= 100; ++j) {
38                // Check if integer j is between left and right
39                if (prefixSum[right][j] - prefixSum[left][j] > 0) {
40                    // Update minDiff if there was a last seen integer
41                    if (lastSeen != -1) {
42                        minDiff = min(minDiff, j - lastSeen);
43                    }
44                    // Update lastSeen with the current integer
45                    lastSeen = j;
46                }
47            }
48
49            // If minDiff remains 101, it means no two different numbers were found so set minDiff to -1
50            if (minDiff == 101) {
51                minDiff = -1;
52            }
53
54            // Store the result in the answer vector
55            answer[i] = minDiff;
56        }
57
58        // Return the calculated minimum differences for each query
59        return answer;
60    }
61};
62

1function minDifference(nums: number[], queries: number[][]): number[] {
2    const numLength = nums.length;      // Total number of elements in nums array
3    const queryLength = queries.length; // Total number of queries
4    const maxValue = 100;               // Maximum value that nums can have
5
6    // Prefix sum array to store the frequencies of each number up to index i
7    const prefixSum: number[][] = [new Array(maxValue + 1).fill(0)];
8
9    // Populate the prefix sum array
10    for (let i = 0; i < numLength; ++i) {
11        let currentNumber = nums[i];
12        // Copy the previous frequency array and update the current number frequency
13        prefixSum.push(prefixSum[i].slice());
14        prefixSum[i + 1][currentNumber] += 1;
15    }
16
17    const results = []; // Array to store the minimum differences for each query
18
19    // Iterate through each query to calculate minimum differences
20    for (let [left, right] of queries) {
21        let lastOccurrence = -1; // Last seen number (initialize to -1)
22        let minDiff = Infinity;  // Minimum difference found (initialize to infinity)
23
24        // Iterate through all possible values in the range [1, maxValue]
25        for (let value = 1; value <= maxValue; ++value) {
26            // Check if the number 'value' is present between 'left' and 'right' indices
27            if (prefixSum[left][value] < prefixSum[right + 1][value]) {
28                // If 'lastOccurrence' is not -1, it means that we have already found a previous number
29                if (lastOccurrence !== -1) {
30                    // Update minDiff if the current difference is smaller than the previously found
31                    minDiff = Math.min(minDiff, value - lastOccurrence);
32                }
33                // Update the lastOccurrence to the current value
34                lastOccurrence = value;
35            }
36        }
37
38        // If no number is found between 'left' and 'right', return -1, else the minimum difference
39        results.push(minDiff === Infinity ? -1 : minDiff);
40    }
41
42    return results; // Return result array with minimum differences for each query
43}
44

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.

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.
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:

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.
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.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Add another stack to store the minimums

Add a heap to store the minimums

Add a variable to track the minimum

Add a queue to store the minumums

I don't know