Skip to main content
Talentd

Minimum Absolute Difference - Solution & Explanation

EasyArraySorting18 min readAsked at: Amazon, Microsoft, Meta +13
Practice this problem

Problem Statement

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

 

Example 1:

Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.

Example 2:

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

Example 3:

Input: arr = [3,8,-10,23,19,-4,-14,27]
Output: [[-14,-10],[19,23],[23,27]]

 

Constraints:

  • 2 <= arr.length <= 105
  • -106 <= arr[i] <= 106

Approach Overview

Problem Overview: You are given an integer array arr. The task is to find every pair of elements whose absolute difference is the smallest among all possible pairs. The result must include all pairs that share this minimum difference and should be returned in ascending order.

Approach 1: Complete Pairwise Comparison (Brute Force) (O(n²) time, O(1) space)

This method checks every possible pair in the array. Use two nested loops: the outer loop fixes an element and the inner loop compares it with every element after it. For each pair, compute abs(arr[i] - arr[j]) and keep track of the smallest difference found so far. If a smaller difference appears, reset the result list; if the difference matches the current minimum, append the pair.

This approach requires no extra data structures and works on the unsorted array. However, it performs n(n-1)/2 comparisons, which becomes expensive for large inputs. Brute force is still useful when explaining the baseline solution in interviews or when constraints are very small.

Approach 2: Sort and Find Minimum Difference (O(n log n) time, O(1) extra space)

Sorting reveals the key insight: the smallest absolute difference between any two numbers must appear between adjacent elements in a sorted array. After sorting the array, iterate once and compute the difference between neighboring elements arr[i] and arr[i+1]. Maintain the smallest difference seen and collect all pairs that match it.

This works because sorting orders numbers so that the closest values appear next to each other. There is no need to compare distant elements. The algorithm performs a single linear scan after the sort, making the dominant cost the sorting step. Many implementations perform the sort in-place, so the extra memory usage remains constant aside from the output list.

The technique combines ideas from sorting with sequential scanning on an array. The code stays simple while achieving strong performance, which is why this approach appears in most accepted solutions.

Recommended for interviews: Start by explaining the brute force comparison to demonstrate you understand the definition of the minimum absolute difference. Then pivot to the sorting insight. Interviewers typically expect the O(n log n) sorted approach because it reduces unnecessary comparisons and shows you can leverage ordering to simplify pair problems.

Approach 1: Sort and Find Minimum Difference

The first approach involves sorting the array and then iterating through it to find the pairs with the minimum absolute difference. By sorting, the smallest differences can only occur between consecutive elements. Hence, we sort the array and compute differences between adjacent elements to find the minimum difference.

Steps:

  • Sort the array.
  • Iterate through the sorted array to find the minimum difference between consecutive elements.
  • Store all pairs with this minimum difference.

This C solution sorts the input array using quicksort and then computes the minimum difference between consecutive elements. Using this minimum difference, it collects all pairs satisfying this difference and stores them in the result array, which is then returned.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n), due to sorting the array. Space Complexity: O(1), not considering the output space.

Try this approach in the editor →

Approach 2: Complete Pairwise Comparison (Brute Force)

The second approach compares all pairs of elements to determine their absolute differences. This method ensures that all possible pairs are considered, and the pairs with the minimum difference are identified. Although not as efficient as the first approach, it explicitly checks every possible pair.

Steps:

  • Initialize the minimum difference as a large value.
  • For each pair of elements, calculate the absolute difference.
  • If the current difference is less than the stored minimum difference, update the minimum difference and restart the pair list.
  • If the difference equals the minimum difference, add the pair to the list.

This C implementation evaluates all pairs of elements to calculate their absolute differences, records the minimum difference detected, and accumulates the pairs with this difference in an array subsequently returned.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), considering all pair combinations. Space Complexity: O(1), excluding result space.

Try this approach in the editor →

Approach 3: Sorting

According to the problem description, we need to find the minimum absolute difference between any two elements in the array arr. Therefore, we can first sort the array arr, then traverse the adjacent elements to get the minimum absolute difference mi.

Finally, we traverse the adjacent elements again to find all pairs of elements where the minimum absolute difference equals mi.

The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array arr.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sort and Find Minimum Difference

Time Complexity: O(n log n), due to sorting the array. Space Complexity: O(1), not considering the output space.

Complete Pairwise Comparison (Brute Force)

Time Complexity: O(n^2), considering all pair combinations. Space Complexity: O(1), excluding result space.

Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Complete Pairwise Comparison (Brute Force)O(n²)O(1)Useful for small arrays or when explaining the baseline idea before optimization.
Sort and Scan Adjacent ElementsO(n log n)O(1) extra (excluding output)Best general solution. Sorting ensures the closest values appear next to each other, reducing comparisons.

Video Solution

LeetCode 1200. Minimum Absolute Difference (Algorithm Explained) • Nick White • 22,283 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Absolute Difference easy or hard?
Minimum Absolute Difference is classified as an Easy problem on LeetCode. The main insight is recognizing that sorting allows you to check only adjacent elements instead of all pairs. Once that idea is clear, the implementation is straightforward.
Minimum Absolute Difference Python/Java solution
In Python or Java, sort the array using the built-in sort function and iterate once to track the smallest difference. Whenever a smaller difference is found, reset the result list; if the difference matches the current minimum, append the pair. This implementation runs in O(n log n) time.
How to solve Minimum Absolute Difference in O(n)?
An O(n) solution is generally not possible for arbitrary unsorted input because identifying closest values requires ordering information. Sorting provides that ordering and costs O(n log n). After sorting, the remaining scan step runs in linear time.
What is the best approach for Minimum Absolute Difference?
The optimal approach sorts the array first and then scans adjacent elements to compute differences. Because the closest numbers must appear next to each other in sorted order, only neighboring pairs need to be checked. This runs in O(n log n) time due to sorting and O(1) extra space.
Is Minimum Absolute Difference asked at Google/Amazon/Meta?
Problems based on finding minimum differences and leveraging sorting patterns appear frequently in interviews at large tech companies. Variations of this problem are common in Amazon and Google interview preparation sets because they test understanding of sorting and pair comparisons.
What data structure is used in Minimum Absolute Difference?
The primary structure is a simple array. The algorithm relies on sorting the array and then iterating sequentially to compare adjacent elements. No additional complex data structures are required.
What is the time complexity of Minimum Absolute Difference?
The optimal solution runs in O(n log n) time because the array must be sorted before scanning. After sorting, a single pass through the array calculates differences between adjacent elements in O(n). The brute force method takes O(n²) time since it compares every pair.

Ready to solve this problem?

Practice Minimum Absolute Difference with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimize the Maximum Difference of Pairs

Next

Minimum Cost of Buying Candies With Discount