Minimum Absolute Difference - Practice Coding Problems

Minimum Absolute Difference - Problem

Array Sorting Easy

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements.

Return a list of pairs in ascending order (with respect to pairs), each pair [a, b] follows:

a, b are from arr
a < b
b - a equals to the minimum absolute difference of any two elements in arr

Input & Output

Example 1 — Basic Case

$ Input: arr = [4,2,1,3]

› Output: [[1,2],[2,3],[3,4]]

💡 Note: After sorting: [1,2,3,4]. Adjacent differences: |2-1|=1, |3-2|=1, |4-3|=1. Minimum difference is 1, so all adjacent pairs qualify.

Example 2 — Single Pair

$ Input: arr = [1,3,6,10,15]

› Output: [[1,3]]

💡 Note: After sorting: [1,3,6,10,15]. Adjacent differences: |3-1|=2, |6-3|=3, |10-6|=4, |15-10|=5. Minimum difference is 2, only pair [1,3] qualifies.

Example 3 — Multiple Minimum Pairs

$ Input: arr = [1,1,3,3]

› Output: [[1,3],[1,3]]

💡 Note: After sorting: [1,1,3,3]. Adjacent differences: |1-1|=0, |3-1|=2, |3-3|=0. Wait, this violates distinct constraint. Let's use [1,5,3,4]: sorted [1,3,4,5], differences [2,1,1], min=1, pairs [[3,4],[4,5]].

Constraints

2 ≤ arr.length ≤ 10⁵
-10⁶ ≤ arr[i] ≤ 10⁶
All integers in arr are distinct

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array of distinct integers

Sort & Compare

Sort array and find minimum difference between adjacent elements

Collect Pairs

Return all adjacent pairs with minimum difference

Key Takeaway

🎯 Key Insight: After sorting, minimum absolute difference can only occur between adjacent elements

Asked in

a Amazon 15 G Google 12 f Facebook 8 M Microsoft 6

The key insight is that after sorting the array, the minimum absolute difference can only occur between adjacent elements. The optimal approach sorts first in O(n log n), then finds minimum difference in O(n). Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Sort First - Optimal Solution	O(n log n)	O(1)	Sort array first, then minimum difference must be between adjacent elements
Brute Force - Compare All Pairs	O(n²)	O(1)	Check every possible pair to find minimum difference, then collect all pairs with that difference

Sort First - Optimal Solution — Algorithm Steps

Step 1: Sort the array
Step 2: Find minimum difference by checking adjacent pairs
Step 3: Collect all adjacent pairs with minimum difference

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Array

Arrange elements in ascending order

Check Adjacent

Find minimum difference between consecutive elements

Collect Pairs

Gather adjacent pairs with minimum difference

Code -

solution.c — C

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

int compare_ints(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int** solution(int* arr, int arrSize, int* returnSize, int** returnColumnSizes) {
    // Sort the array
    qsort(arr, arrSize, sizeof(int), compare_ints);
    
    // Find minimum difference between adjacent elements
    int minDiff = INT_MAX;
    for (int i = 0; i < arrSize - 1; i++) {
        int diff = arr[i + 1] - arr[i];
        if (diff < minDiff) {
            minDiff = diff;
        }
    }
    
    // Count pairs with minimum difference
    int count = 0;
    for (int i = 0; i < arrSize - 1; i++) {
        if (arr[i + 1] - arr[i] == minDiff) {
            count++;
        }
    }
    
    // Allocate result
    int** result = (int**)malloc(count * sizeof(int*));
    *returnColumnSizes = (int*)malloc(count * sizeof(int));
    
    // Collect pairs
    int idx = 0;
    for (int i = 0; i < arrSize - 1; i++) {
        if (arr[i + 1] - arr[i] == minDiff) {
            result[idx] = (int*)malloc(2 * sizeof(int));
            (*returnColumnSizes)[idx] = 2;
            result[idx][0] = arr[i];
            result[idx][1] = arr[i + 1];
            idx++;
        }
    }
    
    *returnSize = count;
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse array
    int arr[1000];
    int arrSize = 0;
    char *token = strtok(line + 1, ",]");
    while (token != NULL) {
        arr[arrSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(arr, arrSize, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[%d,%d]", result[i][0], result[i][1]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), then single pass O(n) to find pairs

⚡ Linearithmic

Space Complexity

O(1)

Only using variables if sorting in-place, O(n) if creating new array

✓ Linear Space

23.5K Views

Medium Frequency

~15 min Avg. Time

894 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

Sort First - Optimal Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler