Minimum Absolute Difference Queries

Minimum Absolute Difference Queries

What is this problem about?

The Minimum Absolute Difference Queries problem is a more advanced variation of the basic difference problem. Instead of a tree, you are given an array and a set of queries. Each query defines a range [left, right], and you must find the minimum absolute difference between any two elements within that specific sub-segment of the array. The challenge lies in the constraints: if the array is large and there are many queries, a brute-force approach of sorting each sub-segment will be far too slow.

Why is this asked in interviews?

This is a frequent Minimum Absolute Difference Queries interview question at Google because it pushes candidates beyond simple array manipulation. It requires knowledge of Prefix Sums or frequency tracking. It tests if you can pre-calculate data to answer complex range queries in a fraction of the time. Interviewers use this to identify candidates who can optimize for "online" queries where response time per query is critical.

Algorithmic pattern used

The Prefix Sum interview pattern is adapted here by using a 2D prefix sum array (or a list of frequency arrays). Since the range of values in the array is often small (e.g., 1 to 100), you can store the count of each number up to every index. For a query [L, R], the frequency of a number x is count[R][x] - count[L-1][x]. By checking which numbers exist in the range in sorted order (1 to 100), you can find the minimum difference between consecutively existing numbers.

Example explanation

Suppose we have an array [1, 3, 4, 8] and a query for the whole range.

1. We track which numbers exist: 1, 3, 4, and 8.
2. We calculate differences between adjacent existing numbers:
   • |3 - 1| = 2
   • |4 - 3| = 1
   • |8 - 4| = 4
3. The minimum of these differences is 1. If a query was only for [1, 3], we would only see numbers 1 and 3, and the answer would be 2.

Common mistakes candidates make

• Brute force sorting: Trying to sort the subarray for every query. With Q queries and N elements, an $O(Q \cdot N \log N)$ approach will likely time out.
• Ignoring value constraints: Failing to notice that the values in the array have a small range, which is the crucial hint that you should use a frequency-based approach rather than a comparison-based one.
• Off-by-one errors: Incorrectly calculating the prefix sum range (using L instead of L-1), leading to missing elements at the boundary of the query.

Interview preparation tip

When you see "queries" on an array, immediately think of Precomputation. Ask yourself: "Can I store some information (like sums, min/max, or frequencies) that makes answering the query faster?" For this specific Minimum Absolute Difference Queries coding problem, the small range of values is a "hidden" clue to use a frequency-count strategy.