Minimum Absolute Difference

🎯

Minimum Absolute Difference

easySORT_SEARCHAmazonGoogle

Imagine you have a list of prices for similar products and want to find two products priced closest to each other to decide on a fair deal.

💡 This problem asks for the smallest difference between any two numbers in an array. Beginners often struggle because they might try comparing every pair without realizing sorting can simplify the problem drastically.

📋

Problem Statement

Given an array of distinct integers arr, find and return the minimum absolute difference between any two elements in the array.

2 ≤ n ≤ 10^5-10^6 ≤ arr[i] ≤ 10^6All elements in arr are distinct

💡

Example

Input"[4, 2, 1, 3]"

Output1

After sorting, the array becomes [1,2,3,4]. The minimum absolute difference is between adjacent elements 1 and 2, 2 and 3, or 3 and 4, all equal to 1.

• Array with only two elements → output is absolute difference of those two
• Array with negative and positive numbers → ensure absolute difference calculation is correct
• Array sorted in descending order → sorting step must handle this
• Array with large values near constraints → test for integer overflow issues

⚠️

Common Mistakes

Not sorting the array before scanning adjacent pairs

Incorrect minimum difference because non-adjacent pairs might be closer

✅ Always sort the array first

Using nested loops for large inputs

Time limit exceeded due to O(n^2) complexity

✅ Use sorting + single pass approach

Not handling negative numbers correctly

Wrong difference calculation if absolute value not used or sorting not done

✅ Sort array and subtract adjacent elements (no need for abs after sorting)

Forgetting to update minimum difference when a smaller one is found

Returns incorrect larger minimum difference

✅ Always update min_diff when a smaller difference is found

Assuming minimum difference can be zero without duplicates

Incorrect early exit or wrong answer

✅ Remember problem states distinct integers, so minimum difference ≥ 1

🧠

Brute Force (Nested Loops)

💡 This approach exists to build intuition by directly comparing every pair, showing why a naive solution is inefficient and motivating better methods.

Intuition

Check every possible pair of elements and compute their absolute difference, keeping track of the minimum found.

Algorithm

1. Initialize min_diff to a large number.
2. Use two nested loops to consider every pair of elements.
3. Calculate the absolute difference for each pair.
4. Update min_diff if a smaller difference is found.

💡 The nested loops make it easy to understand but hard to scale for large inputs.

</>

Code

def minimum_abs_difference(arr):
    n = len(arr)
    min_diff = float('inf')
    for i in range(n):
        for j in range(i + 1, n):
            diff = abs(arr[i] - arr[j])
            if diff < min_diff:
                min_diff = diff
    return min_diff

# Driver code
if __name__ == '__main__':
    arr = [4, 2, 1, 3]
    print(minimum_abs_difference(arr))  # Output: 1

Line Notes

n = len(arr)Determine the number of elements to set loop bounds

for i in range(n)Outer loop picks the first element of the pair

for j in range(i + 1, n)Inner loop picks the second element, avoiding repeats

diff = abs(arr[i] - arr[j])Calculate absolute difference between the pair

if diff < min_diffUpdate minimum difference if current is smaller

import java.util.*;
public class MinimumAbsoluteDifference {
    public static int minimumAbsDifference(int[] arr) {
        int n = arr.length;
        int minDiff = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int diff = Math.abs(arr[i] - arr[j]);
                if (diff < minDiff) {
                    minDiff = diff;
                }
            }
        }
        return minDiff;
    }
    public static void main(String[] args) {
        int[] arr = {4, 2, 1, 3};
        System.out.println(minimumAbsDifference(arr)); // Output: 1
    }
}

Line Notes

int n = arr.length;Get array length for loop limits

for (int i = 0; i < n; i++)Outer loop selects first element

for (int j = i + 1; j < n; j++)Inner loop selects second element without repeats

int diff = Math.abs(arr[i] - arr[j]);Compute absolute difference

if (diff < minDiff)Update minimum difference if smaller found

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;

int minimumAbsDifference(vector<int>& arr) {
    int n = arr.size();
    int minDiff = INT_MAX;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int diff = abs(arr[i] - arr[j]);
            if (diff < minDiff) {
                minDiff = diff;
            }
        }
    }
    return minDiff;
}

int main() {
    vector<int> arr = {4, 2, 1, 3};
    cout << minimumAbsDifference(arr) << endl; // Output: 1
    return 0;
}

Line Notes

int n = arr.size();Get number of elements for loops

for (int i = 0; i < n; i++)Outer loop picks first element

for (int j = i + 1; j < n; j++)Inner loop picks second element without repeats

int diff = abs(arr[i] - arr[j]);Calculate absolute difference

if (diff < minDiff)Update minimum difference if current is smaller

function minimumAbsDifference(arr) {
    const n = arr.length;
    let minDiff = Infinity;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const diff = Math.abs(arr[i] - arr[j]);
            if (diff < minDiff) {
                minDiff = diff;
            }
        }
    }
    return minDiff;
}

// Driver code
const arr = [4, 2, 1, 3];
console.log(minimumAbsDifference(arr)); // Output: 1

Line Notes

const n = arr.length;Determine array length for loops

for (let i = 0; i < n; i++)Outer loop selects first element

for (let j = i + 1; j < n; j++)Inner loop selects second element without repeats

const diff = Math.abs(arr[i] - arr[j]);Calculate absolute difference

if (diff < minDiff)Update minimum difference if smaller found

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops each run up to n times, resulting in n*(n-1)/2 comparisons.

💡 For n=20, this means about 190 comparisons, which is manageable, but for n=100000, it becomes 5 billion comparisons, which is too slow.

Interview Verdict: TLE

This approach is too slow for large inputs and will time out, but it helps understand the problem and motivates better solutions.

🧠

Sorting + Adjacent Pair Scan

💡 Sorting the array first allows us to only check adjacent pairs for minimum difference, drastically reducing comparisons.

Intuition

After sorting, the smallest difference must be between two adjacent elements, so we only scan once through the array comparing neighbors.

Algorithm

1. Sort the array in ascending order.
2. Initialize min_diff to a large number.
3. Iterate through the array from the first to the second last element.
4. Calculate the difference between current and next element and update min_diff if smaller.

💡 Sorting enables a linear scan to find the minimum difference, which is much faster than nested loops.

</>

Code

def minimum_abs_difference(arr):
    arr.sort()
    min_diff = float('inf')
    for i in range(len(arr) - 1):
        diff = arr[i + 1] - arr[i]
        if diff < min_diff:
            min_diff = diff
    return min_diff

# Driver code
if __name__ == '__main__':
    arr = [4, 2, 1, 3]
    print(minimum_abs_difference(arr))  # Output: 1

Line Notes

arr.sort()Sort array to bring closest elements next to each other

for i in range(len(arr) - 1)Loop through array to compare adjacent pairs

diff = arr[i + 1] - arr[i]Calculate difference between neighbors

if diff < min_diffUpdate minimum difference if current is smaller

import java.util.*;
public class MinimumAbsoluteDifference {
    public static int minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);
        int minDiff = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length - 1; i++) {
            int diff = arr[i + 1] - arr[i];
            if (diff < minDiff) {
                minDiff = diff;
            }
        }
        return minDiff;
    }
    public static void main(String[] args) {
        int[] arr = {4, 2, 1, 3};
        System.out.println(minimumAbsDifference(arr)); // Output: 1
    }
}

Line Notes

Arrays.sort(arr);Sort array to arrange elements in ascending order

for (int i = 0; i < arr.length - 1; i++)Loop through array to check adjacent pairs

int diff = arr[i + 1] - arr[i];Calculate difference between neighbors

if (diff < minDiff)Update minimum difference if smaller found

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int minimumAbsDifference(vector<int>& arr) {
    sort(arr.begin(), arr.end());
    int minDiff = INT_MAX;
    for (int i = 0; i < (int)arr.size() - 1; i++) {
        int diff = arr[i + 1] - arr[i];
        if (diff < minDiff) {
            minDiff = diff;
        }
    }
    return minDiff;
}

int main() {
    vector<int> arr = {4, 2, 1, 3};
    cout << minimumAbsDifference(arr) << endl; // Output: 1
    return 0;
}

Line Notes

sort(arr.begin(), arr.end());Sort array to bring closest elements together

for (int i = 0; i < (int)arr.size() - 1; i++)Loop through array to compare adjacent elements

int diff = arr[i + 1] - arr[i];Calculate difference between neighbors

if (diff < minDiff)Update minimum difference if current is smaller

function minimumAbsDifference(arr) {
    arr.sort((a, b) => a - b);
    let minDiff = Infinity;
    for (let i = 0; i < arr.length - 1; i++) {
        const diff = arr[i + 1] - arr[i];
        if (diff < minDiff) {
            minDiff = diff;
        }
    }
    return minDiff;
}

// Driver code
const arr = [4, 2, 1, 3];
console.log(minimumAbsDifference(arr)); // Output: 1

Line Notes

arr.sort((a, b) => a - b);Sort array numerically ascending

for (let i = 0; i < arr.length - 1; i++)Loop through array to check adjacent pairs

const diff = arr[i + 1] - arr[i];Calculate difference between neighbors

if (diff < minDiff)Update minimum difference if smaller found

⏱

Complexity

TimeO(n log n)

SpaceO(1) or O(n) depending on sorting implementation

Sorting takes O(n log n), then a single pass O(n) to find minimum difference.

💡 For n=100000, sorting is feasible and scanning neighbors is very fast, making this approach practical.

Interview Verdict: Accepted

This approach is efficient and accepted for large inputs, making it the standard solution.

🧠

Sorting + Single Pass with Early Exit

💡 This approach optimizes the previous by exiting early if the minimum difference 1 is found, since it cannot get smaller.

Intuition

Since the minimum absolute difference between distinct integers is at least 1, if we find difference 1, we can stop scanning further.

Algorithm

1. Sort the array in ascending order.
2. Initialize min_diff to a large number.
3. Iterate through the array comparing adjacent elements.
4. If difference is 1, return immediately as it's the smallest possible.
5. Otherwise, update min_diff if smaller difference found.
6. Return min_diff after full scan if no early exit.

💡 Early exit reduces unnecessary work when minimum difference is found quickly.

</>

Code

def minimum_abs_difference(arr):
    arr.sort()
    min_diff = float('inf')
    for i in range(len(arr) - 1):
        diff = arr[i + 1] - arr[i]
        if diff == 1:
            return 1
        if diff < min_diff:
            min_diff = diff
    return min_diff

# Driver code
if __name__ == '__main__':
    arr = [4, 2, 1, 3]
    print(minimum_abs_difference(arr))  # Output: 1

Line Notes

arr.sort()Sort array to bring closest elements together

for i in range(len(arr) - 1)Loop through array to check adjacent pairs

if diff == 1:Early exit if minimum possible difference found

if diff < min_diff:Update minimum difference if smaller found

import java.util.*;
public class MinimumAbsoluteDifference {
    public static int minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);
        int minDiff = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length - 1; i++) {
            int diff = arr[i + 1] - arr[i];
            if (diff == 1) {
                return 1;
            }
            if (diff < minDiff) {
                minDiff = diff;
            }
        }
        return minDiff;
    }
    public static void main(String[] args) {
        int[] arr = {4, 2, 1, 3};
        System.out.println(minimumAbsDifference(arr)); // Output: 1
    }
}

Line Notes

Arrays.sort(arr);Sort array ascending

for (int i = 0; i < arr.length - 1; i++)Loop through array to check adjacent pairs

if (diff == 1)Return immediately if minimum difference found

if (diff < minDiff)Update minimum difference if smaller found

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int minimumAbsDifference(vector<int>& arr) {
    sort(arr.begin(), arr.end());
    int minDiff = INT_MAX;
    for (int i = 0; i < (int)arr.size() - 1; i++) {
        int diff = arr[i + 1] - arr[i];
        if (diff == 1) {
            return 1;
        }
        if (diff < minDiff) {
            minDiff = diff;
        }
    }
    return minDiff;
}

int main() {
    vector<int> arr = {4, 2, 1, 3};
    cout << minimumAbsDifference(arr) << endl; // Output: 1
    return 0;
}

Line Notes

sort(arr.begin(), arr.end());Sort array ascending

for (int i = 0; i < (int)arr.size() - 1; i++)Loop through array to check adjacent pairs

if (diff == 1)Early return if minimum difference found

if (diff < minDiff)Update minimum difference if smaller found

function minimumAbsDifference(arr) {
    arr.sort((a, b) => a - b);
    let minDiff = Infinity;
    for (let i = 0; i < arr.length - 1; i++) {
        const diff = arr[i + 1] - arr[i];
        if (diff === 1) {
            return 1;
        }
        if (diff < minDiff) {
            minDiff = diff;
        }
    }
    return minDiff;
}

// Driver code
const arr = [4, 2, 1, 3];
console.log(minimumAbsDifference(arr)); // Output: 1

Line Notes

arr.sort((a, b) => a - b);Sort array ascending

for (let i = 0; i < arr.length - 1; i++)Loop through array to check adjacent pairs

if (diff === 1)Return immediately if minimum difference found

if (diff < minDiff)Update minimum difference if smaller found

⏱

Complexity

TimeO(n log n)

SpaceO(1) or O(n) depending on sorting

Sorting dominates time; early exit can improve best-case runtime.

💡 Early exit helps when minimum difference is small and found early, saving time in practice.

Interview Verdict: Accepted

This is a practical optimization that can impress interviewers by showing attention to detail.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, coding the sorting + adjacent scan approach is best for clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code due to inefficiency
2. Sorting + Adjacent Scan	O(n log n)	O(1) or O(n)	No	N/A	Code this approach for best balance of simplicity and performance
3. Sorting + Early Exit	O(n log n) best case faster	O(1) or O(n)	No	N/A	Mention as optimization if time permits

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach and its inefficiency.Step 3: Introduce sorting and scanning adjacent pairs to optimize.Step 4: Mention early exit optimization if applicable.Step 5: Code the chosen approach and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 8min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your ability to optimize from brute force to efficient sorting-based solution and your understanding of time-space tradeoffs.

Common Follow-ups

• What if the array contains duplicates? → Minimum difference could be zero.
• Can you return the pairs with minimum difference? → Store pairs during scanning.
• What if the array is already sorted? → Skip sorting step.
• How to handle very large arrays efficiently? → Use external sorting or streaming.

💡 These follow-ups test your ability to adapt the solution to variations and optimize further.

🔍

Pattern Recognition

When to Use

1) Asked for minimum or maximum difference between elements; 2) Array or list input; 3) Distinct or unsorted elements; 4) Constraints allow sorting.

Signature Phrases

'minimum absolute difference between any two elements''find the smallest difference'

NOT This Pattern When

Problems requiring subsequence sums or dynamic programming are different despite involving arrays.

Similar Problems

3Sum Closest - also uses sorting and scanning pairsFind K Closest Elements - sorting and two pointers to find closest values

Practice

1. Consider the following code snippet implementing the optimal solution to rearrange an array so no two adjacent elements are equal. What is the output of the function call make_array_beautiful_heap([1,1,2])?

easy

A. []

B. [1, 1, 2]

C. [1, 2, 1]

D. [2, 1, 1]

Solution

1. Step 1: Check max frequency condition

   Frequency counts: 1 -> 2, 2 -> 1; max_freq=2, n=3, (n+1)//2=2, so condition passes.

2. Step 2: Trace heap operations and result construction

   Heap: [(-2,1), (-1,2)] Pop (-2,1): res=[1], prev_count=-1, prev_num=1 Pop (-1,2): res=[1,2], push back (-1,1) since prev_count<0 Pop (-1,1): res=[1,2,1] Return [1,2,1]

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected rearrangement with no adjacent duplicates [OK]

Hint: Check max frequency and simulate heap pops [OK]

Common Mistakes:

• Returning original array without rearrangement
• Confusing heap push/pop order

2. The following code attempts to find the maximum gap between successive elements in a list using the bucket sort approach. Identify the line containing the subtle bug that can cause incorrect results for some inputs.

def maximumGap(nums):
    if len(nums) < 2:
        return 0
    min_num, max_num = min(nums), max(nums)
    if min_num == max_num:
        return 0
    bucket_size = max(1, (max_num - min_num) // (len(nums) - 1))
    bucket_count = (max_num - min_num) // bucket_size
    buckets = [[None, None] for _ in range(bucket_count + 1)]
    for num in nums:
        idx = (num - min_num) // bucket_size
        if buckets[idx][0] is None or num < buckets[idx][0]:
            buckets[idx][0] = num
        if buckets[idx][1] is None or num > buckets[idx][1]:
            buckets[idx][1] = num
    max_gap = 0
    prev_max = None
    for b in buckets:
        if b[0] is None:
            continue
        if prev_max is not None:
            max_gap = max(max_gap, b[0] - prev_max)
        prev_max = b[1]
    return max_gap

medium

A. Line assigning idx: idx = (num - min_num) // bucket_size

B. Line calculating bucket_size: bucket_size = max(1, (max_num - min_num) // (len(nums) - 1))

C. Line updating max_gap inside the for-loop scanning buckets

D. Line calculating bucket_count: bucket_count = (max_num - min_num) // bucket_size

Solution

1. Step 1: Understand bucket count calculation

   Bucket count should be ceil((max_num - min_num) / bucket_size) to cover full range.

2. Step 2: Identify bug in bucket_count line

   Using integer division truncates, possibly missing the last bucket, causing some elements to be out of range or buckets to overlap.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct bucket count must cover entire range [OK]

Hint: Bucket count must cover full range, use ceiling not floor [OK]

Common Mistakes:

• Using floor division for bucket count
• Incorrect bucket size causing overlaps
• Assuming max gap inside buckets

3. What is the worst-case time complexity of the optimal approach using binary search to find missing ranges in a sorted list of size n within the range [lower, upper]?

medium

A. O(n log n)

B. O((upper - lower) * log n)

C. O(n + log(upper - lower))

D. O(n log(upper - lower))

Solution

1. Step 1: Analyze binary search calls per iteration

   Each iteration advances pointer to next missing range start or after current number. Each bisect call is O(log n). Since pointer can advance by 1 in worst case, total iterations can be up to (upper - lower + 1).

2. Step 2: Combine iteration count and bisect cost

   In worst case, pointer advances one by one through the entire range, each bisect O(log n), total O((upper - lower) * log n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search per number in range leads to O((upper - lower) log n) [OK]

Hint: Pointer can advance one by one, so multiply range size by log n [OK]

Common Mistakes:

• Assuming pointer always skips ahead by elements
• Confusing n and range size
• Ignoring worst-case pointer increments

4. Consider the following buggy code snippet for finding missing ranges. Which line contains the subtle bug that causes missing ranges at the start of the interval to be ignored?

medium

A. Line with condition 'if pointer <= curr:' should be 'if pointer < curr:'

B. Line updating pointer to 'curr + 1' should be 'curr' instead

C. Line checking 'if idx == len(nums):' should check 'if idx > len(nums):'

D. Line appending missing range should format single numbers as 'start->end' always

Solution

1. Step 1: Identify condition for missing range detection

   The condition 'if pointer <= curr:' incorrectly includes the case pointer == curr, causing no gap detection before first element if pointer equals first number.

2. Step 2: Correct condition to 'if pointer < curr:'

   This ensures missing ranges are detected only when pointer is strictly less than current number, capturing missing numbers before first element.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing to '<' fixes missing start ranges [OK]

Hint: Check strict inequality when detecting gaps [OK]

Common Mistakes:

• Using <= instead of <
• Incorrect pointer update
• Wrong formatting of single numbers

5. Suppose the problem is modified so that time points can repeat multiple times and you want to find the minimum difference between any two occurrences, but the input size is very large (up to 10^7). Which approach is best suited to handle this efficiently?

hard

A. Use the brute force nested loops approach to check all pairs for minimum difference.

B. Use the bucket sort approach with a boolean array to detect duplicates and find minimum difference in O(n) time.

C. Use a hash map to count occurrences and then sort unique times to find minimum difference.

D. Use a balanced binary search tree to insert times and find minimum difference on the fly.

Solution

1. Step 1: Consider input size and duplicates

   With up to 10^7 times and possible duplicates, brute force is infeasible.

2. Step 2: Bucket sort with boolean array is optimal

   Using a fixed-size 1440-length boolean array detects duplicates instantly and scans once for minimum difference in O(n) time.

3. Step 3: Other approaches are less efficient

   Sorting or balanced trees add overhead and cannot beat fixed-size bucket scanning for this problem.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Bucket sort approach handles large inputs and duplicates efficiently [OK]

Hint: Fixed 1440 bucket array handles duplicates and large inputs efficiently [OK]

Common Mistakes:

• Trying brute force on large inputs
• Sorting large inputs with duplicates is costly
• Using trees adds unnecessary overhead