EasyArraySortingUpdated Sep 2026

1200. Minimum Absolute Difference

Asked at Walmart

Difficulty

Easy

Time

O(n log n)

Space

O(1)

Pattern

Array

Companies

1

Problem

You are given an array arr of distinct integers. Look at every possible pair of elements and find the smallest absolute difference between any two of them. Call this value minDiff.

Return all pairs [a, b] that reach this difference, where a < b. The list of pairs must be sorted in ascending order: compare pairs by their first element, then by their second element.

A key observation: after you sort the array, the closest two values are always next to each other. So you never need to check far-apart elements — only neighbors.

Find the smallest gap, then list every pair with it

arr42130123The input is not sorted, so neighbors here are not theclosest values.sortedgap 1gap 1gap 112340123After sorting, each gap is 1, so the answer is[[1,2],[2,3],[3,4]].
In [4,2,1,3] the smallest gap is 1, and three adjacent pairs share it.

Constraints

  • ●2 <= arr.length <= 10^5
  • ●-10^6 <= arr[i] <= 10^6
  • ●All elements of arr are distinct

Examples

Example 1
Inputarr = [4,2,1,3]
Output[[1,2],[2,3],[3,4]]
WhySorted, the array is [1,2,3,4]. Every neighbor gap is 1, so the minimum difference is 1. Three pairs reach it: (1,2), (2,3) and (3,4).
Example 2
Inputarr = [1,3,6,10,15]
Output[[1,3]]
WhyThe neighbor gaps are 2, 3, 4 and 5. The smallest is 2, and only the pair (1,3) has that gap.
Example 3
Inputarr = [3,8,-10,23,19,-4,-14,27]
Output[[-14,-10],[19,23],[23,27]]
WhySorted: [-14,-10,-4,3,8,19,23,27]. The gaps are 4,6,7,5,11,4,4. The minimum is 4, reached by (-14,-10), (19,23) and (23,27).

Asked At

1 companies
CompanyDifficulty
WalmartEasyView all Walmart questions →

How to Think About It

1

Brute force: compare every pair of elements, track the minimum absolute difference.

2

Sort the array first so that the minimum difference must be between adjacent elements.

3

After sorting, make one pass computing arr[i+1] - arr[i] to find the minimum diff.

4

Collect all pairs that achieve the minimum difference in a second pass.

5

Time O(n log n) for sorting, space O(1) excluding the output. Total time O(n log n).

Optimal Approach

Sort the array. Initialize minDiff to a large value. Iterate through adjacent pairs, updating minDiff whenever a smaller difference is found. In a second pass, collect all pairs whose difference equals minDiff. Sorting guarantees the minimum difference is between neighbors. Time complexity is O(n log n) due to sorting. Space is O(1) auxiliary.

Sort, scan for minDiff, scan again to collect

sortedgap 2136101501234ii+1Pass 1 — compare each neighbor pair and keep thesmallest gap, here 2.sortedgap 2 = minDiff136101501234Pass 2 — keep only pairs whose gap equals minDiff, so[[1,3]].minDiff = min(arr[i+1] - arr[i])keep pair when arr[i+1] - arr[i] == minDiff
One pass finds the smallest neighbor gap; a second pass keeps every pair that matches it.
ComplexityTime O(n log n)Space O(1)Sorting dominates the cost; the two scans over adjacent pairs are linear, and only the output list uses extra memory.

What Trips People Up in Real Interviews

1

Confirm that all elements are distinct (simplifies the logic).

2

Ask whether the output order matters (ascending order of pairs).

3

Mention that after sorting, non-adjacent pairs cannot have a smaller difference.

4

Edge cases: array of size 2 (return that single pair), all pairs have same difference.

5

Use a list of pairs rather than a set to maintain sorted output order.

Solution Code

O(n log n) time
def minimumAbsDifference(arr):
    arr.sort()
    min_diff = float('inf')
    for i in range(len(arr) - 1):
        min_diff = min(min_diff, arr[i + 1] - arr[i])
    result = []
    for i in range(len(arr) - 1):
        if arr[i + 1] - arr[i] == min_diff:
            result.append([arr[i], arr[i + 1]])
    return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Minimum Absolute Difference problem?

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference in ascending order. Sorting the array ensures that the minimum difference always occurs between adjacent elements, reducing the problem to a single pass.

How do you solve Minimum Absolute Difference?

The optimal approach runs in O(n log n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Minimum Absolute Difference?

Minimum Absolute Difference is asked at Walmart. It is a easy difficulty problem.

What are common mistakes on Minimum Absolute Difference?
  • Confirm that all elements are distinct (simplifies the logic).
  • Ask whether the output order matters (ascending order of pairs).
  • Mention that after sorting, non-adjacent pairs cannot have a smaller difference.
  • Edge cases: array of size 2 (return that single pair), all pairs have same difference.
  • Use a list of pairs rather than a set to maintain sorted output order.