Minimum Absolute Difference Queries

Minimum Absolute Difference Queries - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [4,5,2,7,10], queries = [[0,2]]

› Output: [1]

💡 Note: Query [0,2] gives subarray [4,5,2]. Checking differences: |4-5|=1, |4-2|=2, |5-2|=3. Minimum is 1.

Example 2 — Multiple Queries

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

› Output: [2,1]

💡 Note: Query [0,1] gives [1,3], difference |1-3|=2. Query [1,2] gives [3,4], difference |3-4|=1.

Example 3 — All Same Elements

$ Input: nums = [5,5,5], queries = [[0,2]]

› Output: [-1]

💡 Note: All elements in subarray [5,5,5] are identical, so no valid pairs with different values exist.

Constraints

2 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 100
1 ≤ queries.length ≤ 2 × 10⁴
0 ≤ l_i < r_i < nums.length

Visualization

Tap to expand

Asked in

a Amazon 15 G Google 12

Brief HTML summary: The key insight is leveraging the constraint that values are bounded in [1,100] to use frequency counting instead of checking all pairs. Best approach is frequency counting with Time: O(Q × N), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Count Optimization	O(Q × N + Q × 100)	O(100)	Use frequency counting and the constraint that values are in range [1,100]
Brute Force	O(Q × N²)	O(1)	For each query, check all pairs in the subarray to find minimum absolute difference

Frequency Count Optimization — Algorithm Steps

Step 1: For each query, count frequency of each value in range [1,100]
Step 2: Find all unique values that appear in the subarray
Step 3: Check consecutive unique values to find minimum difference

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Count how many times each value appears in query range

Find Unique Values

Extract values that appear at least once

Check Consecutive

Minimum difference must be between consecutive unique values

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int* solution(int* nums, int numsSize, int** queries, int queriesSize, int* returnSize) {
    int* result = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int q = 0; q < queriesSize; q++) {
        int left = queries[q][0], right = queries[q][1];
        
        // Count frequency of each value
        int freq[101] = {0};
        for (int i = left; i <= right; i++) {
            freq[nums[i]]++;
        }
        
        // Find all unique values
        int uniqueVals[100];
        int uniqueCount = 0;
        for (int val = 1; val <= 100; val++) {
            if (freq[val] > 0) {
                uniqueVals[uniqueCount++] = val;
            }
        }
        
        // Find minimum difference between consecutive unique values
        if (uniqueCount < 2) {
            result[q] = -1;
        } else {
            int minDiff = INT_MAX;
            for (int i = 0; i < uniqueCount - 1; i++) {
                int diff = uniqueVals[i + 1] - uniqueVals[i];
                if (diff < minDiff) {
                    minDiff = diff;
                }
            }
            result[q] = minDiff;
        }
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse nums array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    
    // Parse queries
    int** queries = (int**)malloc(100 * sizeof(int*));
    int queriesSize = 0;
    char* ptr = line;
    while (*ptr && queriesSize < 100) {
        if (*ptr == '[' && *(ptr+1) != '[') {
            queries[queriesSize] = (int*)malloc(2 * sizeof(int));
            sscanf(ptr, "[%d,%d]", &queries[queriesSize][0], &queries[queriesSize][1]);
            queriesSize++;
        }
        ptr++;
    }
    
    int returnSize;
    int* result = solution(nums, numsSize, queries, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize-1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(Q × N + Q × 100)

Q queries, each scanning N elements and checking up to 100 values

✓ Linear Growth

Space Complexity

O(100)

Frequency array of size 100 for value counts

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Count Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler