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:
- We can only compare different elements, so the same elements should be disregarded when calculating the differences (e.g.,
|5 - 5|
, which equals0
, 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.
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
, wherem
is the number of elements innums
, and101
is used because the numbers are constrained between1
to100
. Thepre_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
tom
(inclusive), iterating over the input arraynums
. - The inner loop goes from
1
to100
, iterating over all possible number values within the constraints.
At each iteration, the code checks if the number
j
is the same as thei-th
element ofnums
. If it matches (nums[i - 1] == j
), the code increments the count for that number at the current prefix index. This populatespre_sum
such thatpre_sum[i][j]
represents the number of times the numberj
has appeared from the start ofnums
up to indexi-1
. - The outer loop goes from
-
Handling Queries: For each query defined by
[l, r]
, the code translates it to a range inpre_sum
as[left, right+1]
to use one-based indexing. It then initializes variablest
to hold the maximum possible value (infinity at the start as a placeholder for no result) andlast
to-1
as a placeholder for the previously encountered number in the subarray. -
Processing each Query: For each query, the code iterates from
1
to100
to check which numbers are present in the subarray and to calculate their difference. Ifpre_sum[right][j] - pre_sum[left][j] > 0
, it means that the numberj
is present in the subarray. We then calculate the difference with thelast
seen number and updatet
with the minimum difference.last
is updated to the current numberj
to be used in the next iterations. -
Handling impossible cases: After processing the differences, if
t
remains as infinity (the code usesinf
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 thust
is set to-1
. -
Storing the Result: The minimum difference
t
calculated for each query is then appended to the result listans
. -
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 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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
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 entrypre_sum[i][j]
represents the number of occurrences of the numberj
up to thei
-th position innums
. Iterating through all values ofnums
and all numbers[1, 100]
to populate this array has a complexity ofO(m * 100)
since we iterate through 100 numbers for each of them
elements innums
. -
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 from1
to100
, we iterate 100 times for each query to determine this. Therefore, the complexity for processing all queries isO(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 thepre_sum
array is(m+1) x 101
, so the space complexity contributed by this array isO(m * 101)
, which isO(m)
as101
is a constant factor. -
Output Array (
ans
): The size of the output array isn
, correlating directly with the number of queries. Therefore, it contributesO(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.
Which data structure is used to implement recursion?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.