Solution Explanation

This problem asks to find the minimum absolute difference between any two distinct elements within given subarrays of an input array. The solution uses a prefix sum approach for efficient query processing.

Approach:

1. Prefix Sum: A 2D prefix sum array preSum is created. preSum[i][j] stores the count of occurrences of the number j in the subarray nums[0...i-1]. This allows for quick calculation of the number of occurrences of each element within any subarray nums[l...r] using preSum[r+1][j] - preSum[l][j].

2. Query Processing: For each query [l, r], we iterate through the possible numbers (1 to 100, as specified in the constraints).

   • We check if a number j is present in the subarray nums[l...r] using the prefix sum.
   • If it is present, and we've encountered a previous number (last), we calculate the absolute difference between j and last, updating the minimum difference t if necessary.
   • If the subarray contains only one unique element, t will remain at its initial high value (infinity in Python, Integer.MAX_VALUE in Java, etc.), resulting in the output -1 after the loop.

3. Result: The minimum absolute difference for each query is stored in the ans array and returned.

Time Complexity Analysis:

• Prefix Sum Calculation: The prefix sum array is computed in O(m*100) time, where 'm' is the length of the input array nums. This is because we iterate through the array once for each possible number (1 to 100).

• Query Processing: For each query, we iterate through at most 100 possible numbers (1 to 100). Thus, processing n queries takes O(n*100) time.

Therefore, the overall time complexity is O(m100 + n100), which simplifies to O(m + n) since 100 is a constant.

Space Complexity Analysis:

The space complexity is dominated by the prefix sum array preSum, which has dimensions (m+1) x 101. Therefore, the space complexity is O(m).

Code Explanation (Python3):

class Solution:
    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        m, n = len(nums), len(queries)
        pre_sum = [[0] * 101 for _ in range(m + 1)]  # Initialize prefix sum array
        for i in range(1, m + 1):
            for j in range(1, 101):
                t = 1 if nums[i - 1] == j else 0 # Count occurrences of j
                pre_sum[i][j] = pre_sum[i - 1][j] + t
 
        ans = []
        for i in range(n):
            left, right = queries[i][0], queries[i][1] + 1 #Extract query indices
            t = float('inf')  # Initialize minimum difference to infinity
            last = -1
            for j in range(1, 101):
                if pre_sum[right][j] - pre_sum[left][j] > 0: #Check if j is present in the subarray
                    if last != -1:
                        t = min(t, j - last) #Update minimum difference
                    last = j
            if t == float('inf'):  #Handle case where all elements are the same
                t = -1
            ans.append(t)
        return ans

The code in other languages (Java, C++, Go, TypeScript) follows the same algorithmic approach, with minor syntax differences. The core logic of prefix sum calculation and query processing remains consistent.