Minimum Absolute Difference solution and explanation
IBM
Google
9 more videos on this problem
LeetCode 1200. Minimum Absolute Difference (Algorithm Explained)Nick White · 5:21 · 22K views
Minimum Absolute Difference🔥 | Leetcode 1200 | SortingAyushi Sharma · 9:16 · 6K views
Minimum Absolute Difference | Simple Explanation | Leetcode 1200 | codestorywithMIKcodestorywithMIK · 8:49 · 4K views
LeetCode 1200: Minimum Absolute Difference - Interview Prep Ep 2Fisher Coder · 9:43 · 1K views
LEETCODE 1200 (JAVASCRIPT) | MINIMUM ABSOLUTE DIFFERENCEAndy Gala · 13:21 · 1K views
1200. Minimum Absolute Difference - LeetCode Python SolutionCode with Carter · 6:03 · 1K views
Minimum Absolute Difference | Leetcode 1200 | Live coding session 🔥🔥🔥🔥 | ArraysCoding Decoded · 4:37 · 810 views
Minimum Absolute Difference | LeetCode 1200 | Coders CampCoders Camp · 7:15 · 606 views
1200. Minimum Absolute Difference | Leetcode Daily - PythonLeetcode Daily · 8:40 · 550 views
1200. Minimum Absolute Difference (Leetcode Easy)Programming Live with Larry · 8:16 · 427 views
The problem
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, bare fromarra < bb - aequals to the minimum absolute difference of any two elements inarr
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.
def minimumAbsDifference(arr):
arr.sort()
min_diff = float('inf')
result = []
for i in range(1, len(arr)):
diff = arr[i] - arr[i - 1]
if diff < min_diff:
min_diff = diff
result = [[arr[i - 1], arr[i]]]
elif diff == min_diff:
result.append([arr[i - 1], arr[i]])
return resultimport java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public List<List<Integer>> minimumAbsDifference(int[] arr) {
Arrays.sort(arr);
int minDiff = Integer.MAX_VALUE;
List<List<Integer>> result = new ArrayList<>();
for (int i = 1; i < arr.length; i++) {
int diff = arr[i] - arr[i - 1];
if (diff < minDiff) {
minDiff = diff;
result.clear();
result.add(Arrays.asList(arr[i - 1], arr[i]));
} else if (diff == minDiff) {
result.add(Arrays.asList(arr[i - 1], arr[i]));
}
}
return result;
}
}#include <vector>
#include <algorithm>
std::vector<std::vector<int>> minimumAbsDifference(std::vector<int>& arr) {
std::sort(arr.begin(), arr.end());
int minDiff = INT_MAX;
std::vector<std::vector<int>> result;
for (size_t i = 1; i < arr.size(); ++i) {
int diff = arr[i] - arr[i - 1];
if (diff < minDiff) {
minDiff = diff;
result.clear();
result.push_back({arr[i - 1], arr[i]});
} else if (diff == minDiff) {
result.push_back({arr[i - 1], arr[i]});
}
}
return result;
}var minimumAbsDifference = function(arr) {
arr.sort((a, b) => a - b);
let minDiff = Infinity;
let result = [];
for (let i = 1; i < arr.length; i++) {
let diff = arr[i] - arr[i - 1];
if (diff < minDiff) {
minDiff = diff;
result = [[arr[i - 1], arr[i]]];
} else if (diff === minDiff) {
result.push([arr[i - 1], arr[i]]);
}
}
return result;
};#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int** minimumAbsDifference(int* arr, int arrSize, int* returnSize, int** returnColumnSizes) {
qsort(arr, arrSize, sizeof(int), compare);
int minDiff = __INT_MAX__;
for (int i = 1; i < arrSize; i++) {
if (arr[i] - arr[i-1] < minDiff) {
minDiff = arr[i] - arr[i-1];
}
}
int** result = malloc(arrSize * sizeof(int*));
*returnColumnSizes = malloc(arrSize * sizeof(int));
*returnSize = 0;
for (int i = 1; i < arrSize; i++) {
if (arr[i] - arr[i-1] == minDiff) {
result[*returnSize] = malloc(2 * sizeof(int));
result[*returnSize][0] = arr[i-1];
result[*returnSize][1] = arr[i];
(*returnColumnSizes)[*returnSize] = 2;
(*returnSize)++;
}
}
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> MinimumAbsDifference(int[] arr) {
Array.Sort(arr);
int minDiff = int.MaxValue;
List<IList<int>> result = new List<IList<int>>();
for (int i = 1; i < arr.Length; i++) {
int diff = arr[i] - arr[i - 1];
if (diff < minDiff) {
minDiff = diff;
result.Clear();
result.Add(new List<int> { arr[i - 1], arr[i] });
} else if (diff == minDiff) {
result.Add(new List<int> { arr[i - 1], arr[i] });
}
}
return result;
}
}This Python solution sorts the list initially and calculates the difference between consecutive elements. It keeps track of the minimum difference and collects pairs that have this difference, placing them in the result list accordingly.
Time Complexity: O(n log n), because the array is sorted. Space Complexity: O(1), without including the storage used for the results.
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.
def minimumAbsDifference(arr):
min_diff = float('inf')
result = []
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
diff = abs(arr[i] - arr[j])
if diff < min_diff:
min_diff = diff
result = [[arr[i], arr[j]]]
elif diff == min_diff:
result.append([arr[i], arr[j]])
return resultimport java.util.ArrayList;
import java.util.List;
class Solution {
public List<List<Integer>> minimumAbsDifference(int[] arr) {
int minDiff = Integer.MAX_VALUE;
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
int diff = Math.abs(arr[i] - arr[j]);
if (diff < minDiff) {
minDiff = diff;
result.clear();
result.add(List.of(arr[i], arr[j]));
} else if (diff == minDiff) {
result.add(List.of(arr[i], arr[j]));
}
}
}
return result;
}
}#include <vector>
#include <algorithm>
std::vector<std::vector<int>> minimumAbsDifference(std::vector<int>& arr) {
int minDiff = INT_MAX;
std::vector<std::vector<int>> result;
for (size_t i = 0; i < arr.size(); ++i) {
for (size_t j = i + 1; j < arr.size(); ++j) {
int diff = std::abs(arr[i] - arr[j]);
if (diff < minDiff) {
minDiff = diff;
result.clear();
result.push_back({arr[i], arr[j]});
} else if (diff == minDiff) {
result.push_back({arr[i], arr[j]});
}
}
}
return result;
}var minimumAbsDifference = function(arr) {
let minDiff = Infinity;
let result = [];
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
let diff = Math.abs(arr[i] - arr[j]);
if (diff < minDiff) {
minDiff = diff;
result = [[arr[i], arr[j]]];
} else if (diff === minDiff) {
result.push([arr[i], arr[j]]);
}
}
}
return result;
};#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int** minimumAbsDifference(int* arr, int arrSize, int* returnSize, int** returnColumnSizes) {
*returnSize = 0;
int minDiff = INT_MAX;
for (int i = 0; i < arrSize; i++) {
for (int j = i + 1; j < arrSize; j++) {
int diff = arr[j] - arr[i];
if (diff < 0) diff = -diff;
if (diff < minDiff) {
minDiff = diff;
}
}
}
for (int i = 0; i < arrSize; i++) {
for (int j = i + 1; j < arrSize; j++) {
int diff = arr[j] - arr[i];
if (diff < 0) diff = -diff;
if (diff == minDiff) (*returnSize)++;
}
}
int** result = malloc(*returnSize * sizeof(int*));
*returnColumnSizes = malloc(*returnSize * sizeof(int));
int idx = 0;
for (int i = 0; i < arrSize; i++) {
for (int j = i + 1; j < arrSize; j++) {
int diff = arr[j] - arr[i];
if (diff < 0) diff = -diff;
if (diff == minDiff) {
result[idx] = malloc(2 * sizeof(int));
result[idx][0] = arr[i];
result[idx][1] = arr[j];
(*returnColumnSizes)[idx] = 2;
idx++;
}
}
}
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> MinimumAbsDifference(int[] arr) {
int minDiff = int.MaxValue;
List<IList<int>> result = new List<IList<int>>();
for (int i = 0; i < arr.Length; i++) {
for (int j = i + 1; j < arr.Length; j++) {
int diff = Math.Abs(arr[i] - arr[j]);
if (diff < minDiff) {
minDiff = diff;
result.Clear();
result.Add(new List<int> { arr[i], arr[j] });
} else if (diff == minDiff) {
result.Add(new List<int> { arr[i], arr[j] });
}
}
}
return result;
}
}This Python implementation calculates differences for every pair of elements, updates the smallest detected difference, and arranges matched pairs into a list for return.
Time Complexity: O(n^2), entailing a comprehensive pair examination. Space Complexity: O(1), ignoring resulting list space.
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.
function minimumAbsDifference(arr: number[]): number[][] {
arr.sort((a, b) => a - b);
let mi = 1 << 30;
const n = arr.length;
for (let i = 0; i < n - 1; ++i) {
mi = Math.min(mi, arr[i + 1] - arr[i]);
}
const ans: number[][] = [];
for (let i = 0; i < n - 1; ++i) {
if (arr[i + 1] - arr[i] === mi) {
ans.push([arr[i], arr[i + 1]]);
}
}
return ans;
}func minimumAbsDifference(arr []int) (ans [][]int) {
sort.Ints(arr)
mi := 1 << 30
n := len(arr)
for i := 0; i < n-1; i++ {
if t := arr[i+1] - arr[i]; t < mi {
mi = t
}
}
for i := 0; i < n-1; i++ {
if arr[i+1]-arr[i] == mi {
ans = append(ans, []int{arr[i], arr[i+1]})
}
}
return
}impl Solution {
pub fn minimum_abs_difference(mut arr: Vec<i32>) -> Vec<Vec<i32>> {
arr.sort();
let n = arr.len();
let mut mi = i32::MAX;
for i in 1..n {
mi = mi.min(arr[i] - arr[i - 1]);
}
let mut ans = Vec::new();
for i in 1..n {
if arr[i] - arr[i - 1] == mi {
ans.push(vec![arr[i - 1], arr[i]]);
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sort and Find Minimum Difference | Time Complexity: O(n log n), because the array is sorted. Space Complexity: O(1), without including the storage used for the results. |
| Complete Pairwise Comparison (Brute Force) | Time Complexity: O(n^2), entailing a comprehensive pair examination. Space Complexity: O(1), ignoring resulting list space. |
| Sorting | – |
Complexity analysis
| Approach | Time | Space | When 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 Elements | O(n log n) | O(1) extra (excluding output) | Best general solution. Sorting ensures the closest values appear next to each other, reducing comparisons. |
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.