Problem Description

You are given an integer array nums and a 2D array queries where each query is represented as [li, ri]. For each query, you need to find the minimum absolute difference in the subarray nums[li...ri].

The minimum absolute difference of an array is the smallest value of |a[i] - a[j]| where:

• 0 <= i < j < array.length
• a[i] != a[j] (the two elements must be different)
• If all elements in the array are the same, return -1

For example, in the array [5, 2, 3, 7, 2]:

• The minimum absolute difference is |2 - 3| = 1
• Note that even though there are two 2's, we can't use |2 - 2| = 0 because the elements must be different values

Your task is to process each query and return an array ans where ans[i] is the minimum absolute difference for the subarray specified by the i-th query.

The solution uses a prefix sum approach to efficiently track which values (1-100) appear in each subarray range. For each query:

1. It builds a frequency count of values present in the subarray using prefix sums
2. It identifies all distinct values that appear in the range
3. It finds the minimum difference between consecutive distinct values
4. If only one distinct value exists (all elements are the same), it returns -1

The time complexity is O(m * 100 + n * 100) where m is the length of nums and n is the number of queries, since values are constrained to the range [1, 100].

Intuition

The key insight is that to find the minimum absolute difference between different elements, we need to identify which distinct values exist in a subarray and find the smallest gap between them.

Since we're dealing with multiple queries on different subarrays, a naive approach of sorting each subarray would be inefficient. We need a way to quickly determine which values are present in any given range.

The crucial observation is that the problem constraints limit values to the range [1, 100]. This small range allows us to use a fixed-size frequency tracking approach. Instead of sorting or using complex data structures, we can simply track the presence of each possible value.

To efficiently answer range queries, we can use prefix sums. For each position in the array and each possible value (1 to 100), we maintain a count of how many times that value has appeared up to that position. This creates a 2D prefix sum array where pre_sum[i][j] represents the count of value j in nums[0...i-1].

With this preprocessing, for any query [left, right], we can instantly determine if value j exists in that range by checking if pre_sum[right+1][j] - pre_sum[left][j] > 0.

Once we know which values are present, finding the minimum difference becomes straightforward: we iterate through all possible values (1 to 100) in order, track consecutive values that appear in the range, and calculate their differences. The minimum of these differences is our answer.

This approach trades space for time - we use O(m * 100) space to achieve O(100) time per query, which is constant time given the constraint on values.

Solution Approach

The solution implements a prefix sum approach with the following steps:

1. Building the Prefix Sum Array:

pre_sum = [[0] * 101 for _ in range(m + 1)]

We create a 2D array pre_sum where pre_sum[i][j] stores the count of value j in the first i elements of nums. The array has dimensions (m+1) × 101 where m is the length of nums.

for i in range(1, m + 1):
    for j in range(1, 101):
        t = 1 if nums[i - 1] == j else 0
        pre_sum[i][j] = pre_sum[i - 1][j] + t

For each position i and value j, we check if nums[i-1] == j. If yes, we increment the count from the previous position by 1, otherwise we keep the same count.

2. Processing Each Query:

For each query [left, right]:

left, right = queries[i][0], queries[i][1] + 1

We adjust right to right + 1 to make it inclusive for our prefix sum calculation.

3. Finding Present Values and Minimum Difference:

t = inf
last = -1
for j in range(1, 101):
    if pre_sum[right][j] - pre_sum[left][j] > 0:
        if last != -1:
            t = min(t, j - last)
        last = j

• We iterate through all possible values from 1 to 100
• For each value j, we check if it exists in the range using: pre_sum[right][j] - pre_sum[left][j] > 0
• If the value exists:
  • If we've seen a previous value (last != -1), we calculate the difference j - last and update our minimum
  • We update last to the current value j

4. Handling Edge Cases:

if t == inf:
    t = -1
ans.append(t)

If t remains as inf, it means we found only one distinct value (or none), so we return -1 as specified.

The algorithm efficiently handles range queries in O(100) time per query after O(m × 100) preprocessing, making it suitable for multiple queries on the same array.

Example Walkthrough

Let's walk through the solution with a concrete example:

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

Step 1: Build Prefix Sum Array

We create a prefix sum array to track occurrences of each value (1-100) up to each position:

Position:     0     1     2     3     4     5
nums:         -    [4]   [2]   [3]   [2]   [4]

Key prefix sum values (showing only values 2, 3, 4 for brevity):

pre_sum[0][2] = 0, pre_sum[0][3] = 0, pre_sum[0][4] = 0
pre_sum[1][2] = 0, pre_sum[1][3] = 0, pre_sum[1][4] = 1
pre_sum[2][2] = 1, pre_sum[2][3] = 0, pre_sum[2][4] = 1
pre_sum[3][2] = 1, pre_sum[3][3] = 1, pre_sum[3][4] = 1
pre_sum[4][2] = 2, pre_sum[4][3] = 1, pre_sum[4][4] = 1
pre_sum[5][2] = 2, pre_sum[5][3] = 1, pre_sum[5][4] = 2

Step 2: Process Query [0, 2] (subarray: [4, 2, 3])

Check which values exist in range [0, 2]:

• Value 2: pre_sum[3][2] - pre_sum[0][2] = 1 - 0 = 1 ✓ (exists)
• Value 3: pre_sum[3][3] - pre_sum[0][3] = 1 - 0 = 1 ✓ (exists)
• Value 4: pre_sum[3][4] - pre_sum[0][4] = 1 - 0 = 1 ✓ (exists)

Find minimum difference between consecutive present values:

• First present value: 2 (set last = 2)
• Next present value: 3 → difference = 3 - 2 = 1
• Next present value: 4 → difference = 4 - 3 = 1
• Minimum difference = 1

Step 3: Process Query [2, 4] (subarray: [3, 2, 4])

Check which values exist in range [2, 4]:

• Value 2: pre_sum[5][2] - pre_sum[2][2] = 2 - 1 = 1 ✓ (exists)
• Value 3: pre_sum[5][3] - pre_sum[2][3] = 1 - 0 = 1 ✓ (exists)
• Value 4: pre_sum[5][4] - pre_sum[2][4] = 2 - 1 = 1 ✓ (exists)

Find minimum difference:

• Present values in order: 2, 3, 4
• Differences: 3 - 2 = 1, 4 - 3 = 1
• Minimum difference = 1

Step 4: Process Query [0, 4] (subarray: [4, 2, 3, 2, 4])

Check which values exist in range [0, 4]:

• Value 2: pre_sum[5][2] - pre_sum[0][2] = 2 - 0 = 2 ✓ (exists)
• Value 3: pre_sum[5][3] - pre_sum[0][3] = 1 - 0 = 1 ✓ (exists)
• Value 4: pre_sum[5][4] - pre_sum[0][4] = 2 - 0 = 2 ✓ (exists)

Find minimum difference:

• Present values in order: 2, 3, 4
• Differences: 3 - 2 = 1, 4 - 3 = 1
• Minimum difference = 1

Final Answer: [1, 1, 1]

The algorithm efficiently finds that all three queries have a minimum absolute difference of 1, using the prefix sum array to quickly identify which values are present in each subarray range.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * 101 + n * 101) which simplifies to O(m + n)

• Building the prefix sum array requires iterating through all m elements of nums, and for each element, we update 101 values (constant), resulting in O(m * 101) = O(m) time.
• Processing queries requires iterating through all n queries. For each query, we check all 101 possible values (constant) to find which values exist in the subarray and calculate the minimum difference, taking O(n * 101) = O(n) time.
• The overall time complexity is O(m + n) where m is the length of nums and n is the number of queries.

Space Complexity: O(m * 101) which simplifies to O(m)

• The prefix sum array pre_sum has dimensions (m + 1) × 101, requiring O((m + 1) * 101) = O(m) space.
• The answer array ans stores n results, requiring O(n) space.
• Since typically m ≥ n in practical scenarios and the prefix sum dominates, the overall space complexity is O(m).
• Additional variables like left, right, t, and last use constant O(1) space.

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

Common Pitfalls

1. Incorrect Handling of Same Elements

A critical pitfall is misunderstanding that we need the minimum difference between distinct values, not between different positions of the same value.

Wrong Approach:

# Incorrect: Finding minimum difference between any two elements
min_diff = float('inf')
for i in range(left, right + 1):
    for j in range(i + 1, right + 1):
        min_diff = min(min_diff, abs(nums[i] - nums[j]))

This would incorrectly return 0 for [2, 5, 2] by comparing the two 2's.

Correct Approach: Only compare elements with different values, which the prefix sum solution handles by tracking distinct values present in the range.

2. Off-by-One Errors in Index Handling

The queries use 0-based indexing, but the prefix sum array needs careful index management.

Wrong:

# Forgetting to adjust indices properly
left, right = queries[i][0], queries[i][1]  # Missing +1 for right
count = prefix_count[right][value] - prefix_count[left][value]  # Wrong!

Correct:

left_idx = queries[query_idx][0]
right_idx = queries[query_idx][1] + 1  # Convert to exclusive right bound
count = prefix_count[right_idx][value] - prefix_count[left_idx][value]

3. Memory Inefficiency with Large Value Ranges

If the value range wasn't constrained to [1, 100], using a fixed-size array would be wasteful or impossible.

Problematic for large ranges:

# If values could be up to 10^9, this would use excessive memory
prefix_count = [[0] * (10**9 + 1) for _ in range(n + 1)]  # Memory error!

Solution for unconstrained values:

# Use dictionary-based approach for sparse values
from collections import defaultdict

def minDifference(nums, queries):
    result = []
    for left, right in queries:
        # Collect unique values in subarray
        unique_vals = sorted(set(nums[left:right+1]))
      
        if len(unique_vals) < 2:
            result.append(-1)
        else:
            min_diff = min(unique_vals[i+1] - unique_vals[i] 
                          for i in range(len(unique_vals)-1))
            result.append(min_diff)
    return result

4. Not Handling Edge Cases Properly

Failing to return -1 when all elements in the subarray are identical.

Wrong:

# Forgetting to check if we found at least 2 distinct values
min_diff = float('inf')
for value in range(1, 101):
    # ... find differences ...
result.append(min_diff)  # Would append inf instead of -1

Correct:

if min_diff == float('inf'):
    min_diff = -1  # Properly handle single distinct value case
result.append(min_diff)

5. Inefficient Query Processing Without Preprocessing

Processing each query independently without leveraging preprocessing leads to poor performance.

Inefficient O(n² × q) approach:

def minDifference(nums, queries):
    result = []
    for left, right in queries:
        min_diff = float('inf')
        for i in range(left, right + 1):
            for j in range(i + 1, right + 1):
                if nums[i] != nums[j]:
                    min_diff = min(min_diff, abs(nums[i] - nums[j]))
        result.append(-1 if min_diff == float('inf') else min_diff)
    return result

The prefix sum approach reduces this to O(100) per query after O(n × 100) preprocessing, which is much more efficient for multiple queries.