Minimum Absolute Difference Queries - Video Solutions

Problem Overview: You are given an integer nums and multiple queries [l, r]. For each query, consider the subarray nums[l..r] and return the minimum absolute difference between any two distinct values. If the subarray contains only one unique value, return -1. The challenge is answering many range queries efficiently.

Approach 1: Brute Force with Sorting (O(q * k log k) time, O(k) space)

For each query, extract the subarray nums[l..r], sort it, then compute the minimum difference between adjacent elements. Sorting works because the smallest absolute difference must appear between neighbors in sorted order. If the subarray length is k, sorting costs O(k log k) and scanning adjacent pairs costs O(k). This approach is straightforward but slow when there are many queries or large ranges.

Approach 2: Sort and Compare Adjacent Elements (O(q * k log k) time, O(k) space)

This method applies the same key observation: the minimum absolute difference must occur between adjacent elements after sorting. For each query, copy the range into a temporary array, sort it, then iterate once to compute the minimum gap. The algorithm is easy to implement in languages like C, C++, Java, Python, C#, and JavaScript. However, repeatedly sorting overlapping ranges leads to unnecessary work, making it inefficient for large datasets.

Approach 3: Frequency and Preprocessing (O(n * 100 + q * 100) time, O(n * 100) space)

The constraint that values lie between 1 and 100 enables a much faster approach. Build a prefix frequency table where prefix[i][v] stores how many times value v appears in the first i elements. For a query [l, r], determine which numbers exist in the range by subtracting prefix counts. Then scan values 1..100 and track the previous seen value to compute the minimum difference. Each query only checks 100 possible numbers, so it runs in constant time relative to input size.

This technique uses range counting and preprocessing, common in array query problems. The prefix table allows constant-time checks for whether a value exists in a range, avoiding repeated scans of the original array. A small fixed domain makes the algorithm extremely efficient.

Optimized Approach with Precomputation: The prefix-frequency strategy is the intended optimal solution. Precompute counts once, then process each query by iterating through the possible value range and calculating differences between consecutive present numbers. Time complexity becomes O(n * 100 + q * 100) and space complexity O(n * 100). This pattern appears frequently in range-query problems involving small integer domains and can be combined with structures like hash tables or prefix arrays.

Recommended for interviews: Start by explaining the sorting-based brute force to show the core observation about adjacent differences. Then transition to the prefix-frequency optimization. Interviewers expect the preprocessing solution because it reduces each query to scanning a fixed value range instead of repeatedly sorting subarrays.