Skip to main content
Talentd

Minimum Absolute Difference Queries - Solution & Explanation

MediumArrayHash Table15 min readAsked at: Google
Practice this problem

Problem Statement

The minimum absolute difference of an array a is defined as the minimum value of |a[i] - a[j]|, where 0 <= i < j < a.length and a[i] != a[j]. If all elements of a are the same, the minimum absolute difference is -1.

  • For example, the minimum absolute difference of the array [5,2,3,7,2] is |2 - 3| = 1. Note that it is not 0 because a[i] and a[j] must be different.

You are given an integer array nums and the array queries where queries[i] = [li, ri]. For each query i, compute the minimum absolute difference of the subarray nums[li...ri] containing the elements of nums between the 0-based indices li and ri (inclusive).

Return an array ans where ans[i] is the answer to the ith query.

A subarray is a contiguous sequence of elements in an array.

The value of |x| is defined as:

  • x if x >= 0.
  • -x if x < 0.

 

Example 1:

Input: nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]]
Output: [2,1,4,1]
Explanation: The queries are processed as follows:
- queries[0] = [0,1]: The subarray is [1,3] and the minimum absolute difference is |1-3| = 2.
- queries[1] = [1,2]: The subarray is [3,4] and the minimum absolute difference is |3-4| = 1.
- queries[2] = [2,3]: The subarray is [4,8] and the minimum absolute difference is |4-8| = 4.
- queries[3] = [0,3]: The subarray is [1,3,4,8] and the minimum absolute difference is |3-4| = 1.

Example 2:

Input: nums = [4,5,2,2,7,10], queries = [[2,3],[0,2],[0,5],[3,5]]
Output: [-1,1,1,3]
Explanation: The queries are processed as follows:
- queries[0] = [2,3]: The subarray is [2,2] and the minimum absolute difference is -1 because all the
  elements are the same.
- queries[1] = [0,2]: The subarray is [4,5,2] and the minimum absolute difference is |4-5| = 1.
- queries[2] = [0,5]: The subarray is [4,5,2,2,7,10] and the minimum absolute difference is |4-5| = 1.
- queries[3] = [3,5]: The subarray is [2,7,10] and the minimum absolute difference is |7-10| = 3.

 

Constraints:

  • 2 <= nums.length <= 105
  • 1 <= nums[i] <= 100
  • 1 <= queries.length <= 2 * 104
  • 0 <= li < ri < nums.length

Approach Overview

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.

Approach 1: Brute Force with Sorting

This approach involves extracting the subarray for each query, sorting it, and then finding the minimum absolute difference by checking adjacent elements.

Considering the constraints, this approach might not be optimal, but it is straightforward and leverages the fact that the minimum difference will be between consecutive elements in a sorted sequence.

The function processes each query by slicing the nums array and sorting the subarray. It then calculates the minimum difference between consecutive elements in the sorted subarray. If all elements in the subarray are the same, it returns -1. Otherwise, it returns the smallest difference.

Code

Python

Python

Complexity

Time Complexity: O(q * n * log(n)), where q is the number of queries and n is the average size of the subarray.
Space Complexity: O(n) due to the space needed to store the sorted subarray.

Try this approach in the editor →

Approach 2: Optimized Approach with Precomputation

To efficiently compute the minimum absolute difference for each query, we can use a prefix frequency-like array to keep track of the frequency of each number from 0 to 100 in the current range of queries.

This approach reduces redundant computations by leveraging frequency arrays and iteratively building the solution.

This solution precomputes the prefix frequency of each number from 1 to the maximum number in nums for each position. For each query [l, r], it determines the numbers present in the subarray by subtracting the prefix frequency at position l from that at position r+1. This allows for quick determination of differences between the numbers in constant time.

Code

Python

Python

Complexity

Time Complexity: O(n + q * m), where n is the length of nums, q is the number of queries, and m is the number of unique numbers possible (fixed here to 100).
Space Complexity: O(n * m) for storing the prefix frequency array.

Try this approach in the editor →

Approach 3: Approach 1: Sort and Compare Adjacent Elements

This approach involves sorting the subarray and then comparing adjacent elements to find the minimum absolute difference.

This C solution sorts each queried subarray and scans for the minimum absolute difference between adjacent unique elements, ensuring O((r-l) log (r-l)) time complexity for each query due to sorting.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) per query due to sorting.
Space Complexity: O(n) for the subarray.

Try this approach in the editor →

Approach 4: Approach 2: Frequency and Preprocessing

This approach involves preprocessing frequency counts of elements and using the preprocessed data to quickly answer each query.

The C implementation leverages a frequency array, which counts occurrences of elements, and checks adjacent elements for minimum difference calculation.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(100 * q) where q is the number of queries due to fixed range count.
Space Complexity: O(1) ignoring result storage, as we use a fixed-size array for frequency.

Try this approach in the editor →

Approach 5: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force with Sorting

Time Complexity: O(q * n * log(n)), where q is the number of queries and n is the average size of the subarray.
Space Complexity: O(n) due to the space needed to store the sorted subarray.

Optimized Approach with Precomputation

Time Complexity: O(n + q * m), where n is the length of nums, q is the number of queries, and m is the number of unique numbers possible (fixed here to 100).
Space Complexity: O(n * m) for storing the prefix frequency array.

Approach 1: Sort and Compare Adjacent Elements

Time Complexity: O(n log n) per query due to sorting.
Space Complexity: O(n) for the subarray.

Approach 2: Frequency and Preprocessing

Time Complexity: O(100 * q) where q is the number of queries due to fixed range count.
Space Complexity: O(1) ignoring result storage, as we use a fixed-size array for frequency.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with SortingO(q * k log k)O(k)Small arrays or when the number of queries is very low
Sort and Compare Adjacent ElementsO(q * k log k)O(k)Simple implementation when optimization is not required
Frequency and Preprocessing (Prefix Counts)O(n * 100 + q * 100)O(n * 100)Best choice when there are many queries and values are within a small fixed range

Video Solution

Leetcode Solutions | 1906. Minimum Absolute Difference Queries • Fraz • 6,914 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Minimum Absolute Difference Queries easy or hard?
Minimum Absolute Difference Queries is classified as a Medium problem on LeetCode. The brute force solution is simple, but identifying the prefix-frequency optimization using the limited value range requires stronger algorithmic insight.
Minimum Absolute Difference Queries Python/Java solution
Python and Java implementations typically build a prefix frequency matrix of size n x 101. For each query, compute the count of each value in the range and scan the values in ascending order to calculate the smallest difference between consecutive present numbers.
How to solve Minimum Absolute Difference Queries in O(n)?
Strict O(n) overall is not possible because multiple queries must be processed. The closest efficient solution preprocesses prefix frequencies in O(n * 100) time and answers each query in O(100). Since 100 is a fixed constant, the solution behaves nearly linear relative to input size.
What is the best approach for Minimum Absolute Difference Queries?
The optimal approach uses prefix frequency preprocessing. Since the values in nums are limited to the range 1 to 100, you can store cumulative counts for each value. For every query, check which numbers appear in the range and compute the minimum difference by scanning the value domain. This reduces each query to O(100) time after preprocessing.
Is Minimum Absolute Difference Queries asked at Google/Amazon/Meta?
Range query problems with preprocessing and prefix counting frequently appear in interviews at companies like Google, Amazon, and Meta. This problem tests your ability to exploit constraints such as small value ranges and design efficient query handling strategies.
What data structure is used in Minimum Absolute Difference Queries?
The optimal solution uses a prefix frequency array, which is essentially a 2D array storing cumulative counts of numbers from 1 to 100. The problem also involves core concepts from arrays and hash-based counting techniques for tracking value occurrences.
What is the time complexity of Minimum Absolute Difference Queries?
The brute force approach sorts each queried subarray and runs in O(q * k log k), where k is the subarray length. The optimized solution builds a prefix frequency table in O(n * 100) time and answers each query in O(100). Overall complexity becomes O(n * 100 + q * 100).

Ready to solve this problem?

Practice Minimum Absolute Difference Queries with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays