1200. Minimum Absolute Difference
Problem Description
The problem provides an array of distinct integers named arr
. The objective is to find all pairs of elements that have the minimum absolute difference when compared to all other possible element pairs. In other words, we're looking for pairs of numbers that are closer together than any other pairs.
To satisfy the conditions of the problem, there are a few requirements:
- Each pair must be constructed from elements of
arr
. - In each pair
[a, b]
,a
should be less thanb
. - The difference
b - a
must be equal to the smallest absolute difference of any two elements inarr
.
The result should be a list of these pairs in ascending order. Ascending order here applies to the order of the pairs themselves, meaning the first elements of each pair should be in ascending order, and in the case of a tie, the second elements should be in ascending order.
Intuition
To find the pairs with the minimum absolute difference, our approach involves sorting the array and comparing adjacent elements. The reason for sorting is that the smallest difference will always be between adjacent elements; no element can have a smaller difference with a non-adjacent element due to the properties of real numbers.
Here's the step-by-step intuition:
-
Sort the Array: By sorting
arr
, we ensure that we're only comparing differences between neighbors, which simplifies the problem significantly. We know that the minimum difference can only occur between neighboring numbers because the array consists of distinct integers. -
Find the Minimum Difference: We iterate through the sorted array, considering each pair of adjacent elements, to find the minimum difference that exists in the array. This step is key to identifying what the "minimum absolute difference" actually is.
-
Gather All Pairs with Minimum Difference: Once we know the minimum difference, we iterate through the array again, this time collecting all pairs of adjacent elements that have this minimum difference. We construct a list of lists, where each inner list contains a pair of numbers.
The code provided utilizes a Pythonic way of dealing with the adjacent elements through the use of the pairwise()
function, which when provided an iterable, yields tuples containing pairs of consecutive elements. This function is a cleaner and more readable way of accessing adjacent pairs without having to manage indexes manually.
Altogether, the solution efficiently gathers the pairs in a single pass after sorting, keeping the process succinct and the code readable.
Learn more about Sorting patterns.
Solution Approach
To implement the solution to this problem, we are taking advantage of the Python language features and some common algorithmic patterns. Here is a detailed explanation of how the solution approach works:
-
Sorting the Array:
The very first step is to sort the array,arr.sort()
. Sorting is a foundational algorithm in computer science, which organizes elements of a list in a certain order – in this case, ascending numerical order. Since the array consists ofdistinct
integers, sorting will arrange the numbers such that if there's any pair with a minimum absolute difference, it will have neighboring elements. -
Finding the Minimum Absolute Difference:
With the sorted array, we employ a generator expression within themin
function:min(b - a for a, b in pairwise(arr))
. Thepairwise
function is used to create an iterator that will return paired tuples (e.g., (arr[0], arr[1]), (arr[1], arr[2]), ...). Themin
function then finds the smallest difference between these successive pairs. -
List Comprehension to Collect Pairs with Minimum Difference:
After finding the minimum absolute difference, we step through the array again with a list comprehension[ [a, b] for a, b in pairwise(arr) if b - a == mi ]
. This comprehension checks each adjacent pair again to see if their difference is equal to the previously found minimum difference (mi
). When a pair matches, it is added to the output list. -
Returning the Result:
The list of collected pairs that satisfy the minimum absolute difference condition is returned as the final result.
The algorithms and patterns used in this solution are:
- Sorting: A fundamental operation that reorders the items of a list (or any other sequence) to make subsequent operations (like finding a minimum difference) more efficient.
- List Comprehension: A convenient and readable way to construct lists in Python, used here for collecting the required pairs.
- Generator Expression: Used to generate values on the fly; in this case, it helps to find the minimum absolute difference without creating an intermediate list of differences.
- Itertools pairwise() Utility: Although
pairwise
is not an inbuilt function in Python versions prior to 3.10, it can be found in theitertools
module or be custom implemented. It’s a utility to abstract away the complexity of iterating over pairs of consecutive elements.
By breaking down the problem into these steps, the implementation remains clean, efficient, and easy to understand.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to demonstrate how the solution approach is applied. Suppose we have the following array of distinct integers:
1arr = [4, 2, 1, 3]
We are tasked with finding all pairs of elements that have the minimum absolute difference. Here's how we will apply the explained solution approach to this array:
-
Sort the Array:
First, we will sort the array:
1arr.sort() => arr = [1, 2, 3, 4]
After sorting, the array's elements are arranged in ascending order, making it easier to find pairs with the minimum absolute difference, which will be between neighbors.
-
Find the Minimum Absolute Difference:
Next, we examine adjacent pairs to find the smallest difference. Using the
pairwise()
function (or iterating through neighboring pairs manually), we get:1Pairs: (1, 2), (2, 3), (3, 4) 2Differences: 1, 1, 1
The minimum difference here is
1
. This value is determined by iterating through the pairs and finding the smallest difference, which is achieved using:1min(b - a for a, b in pairwise(arr))
-
Collect Pairs with Minimum Difference:
Now that we know the minimum difference is
1
, we look for all pairs with this difference:1[ [a, b] for a, b in pairwise(arr) if b - a == 1 ] 2 3Resulting Pairs: [[1, 2], [2, 3], [3, 4]]
Each of these pairs has the same difference of
1
, which is the minimum we found in the previous step. -
Returning the Result:
Lastly, we return the resultant pairs:
1[[1, 2], [2, 3], [3, 4]]
This is the final result, containing all pairs of elements in arr
which have the smallest absolute difference of any two elements, formatted according to the problem requirements. The pairs are already in ascending order due to the initial sorting of arr
.
Through this example, the implementation follows the steps laid out in the solution approach and demonstrates the effectiveness of sorting, generator expressions, and list comprehensions to solve the problem with minimum absolute difference pairs efficiently.
Solution Implementation
1from itertools import pairwise # import the pairwise function from itertools
2
3class Solution:
4 def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
5 arr.sort() # sort the array
6 # Find the minimum absolute difference between any two consecutive elements
7 min_diff = min(b - a for a, b in pairwise(arr))
8
9 # Create a list of pairs that have the minimum absolute difference
10 result = [[a, b] for a, b in pairwise(arr) if b - a == min_diff]
11
12 return result # return the list of pairs with the minimum absolute difference
13
14# Note: If the `pairwise` function is not available, you can replace it with a direct implementation as shown below.
15# This could be important if you are using a Python version older than 3.10, where `pairwise` was introduced.
16```
17
18If you're using a Python version older than 3.10, which might not have the `pairwise` utility available from `itertools`, you can rewrite the `pairwise` functionality yourself as follows:
19
20```python
21class Solution:
22 def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
23 arr.sort() # Sort the array to obtain elements in ascending order
24
25 # Helper function to iterate over the array in pairs
26 def pairwise(iterable):
27 a, b = tee(iterable)
28 next(b, None)
29 return zip(a, b)
30
31 # Compute the minimum difference between consecutive elements
32 min_diff = min(b - a for a, b in pairwise(arr))
33
34 # Create a list of pairs with the minimum difference
35 result = [[a, b] for a, b in pairwise(arr) if b - a == min_diff]
36
37 return result # Return the resulting list of pairs
38
39# This code is compatible with Python versions older than 3.10, because it defines a custom pairwise function.
40
1import java.util.Arrays; // Import necessary classes
2import java.util.List;
3import java.util.ArrayList;
4
5class Solution {
6 public List<List<Integer>> minimumAbsDifference(int[] arr) {
7 // Sort the array to ensure that the pairs with the smallest absolute difference are adjacent
8 Arrays.sort(arr);
9 int n = arr.length; // Total number of elements in the array
10 int minDifference = Integer.MAX_VALUE; // Initialize minimum difference with the maximum possible integer value
11
12 // Find the minimum absolute difference between consecutive elements
13 for (int i = 0; i < n - 1; ++i) {
14 minDifference = Math.min(minDifference, arr[i + 1] - arr[i]);
15 }
16
17 // Prepare a list to hold pairs with the minimum absolute difference
18 List<List<Integer>> result = new ArrayList<>();
19
20 // Iterate over the array again to find all pairs with the minimum absolute difference
21 for (int i = 0; i < n - 1; ++i) {
22 // If the absolute difference matches the minimum difference found, add the pair to the result list
23 if (arr[i + 1] - arr[i] == minDifference) {
24 result.add(List.of(arr[i], arr[i + 1]));
25 }
26 }
27
28 // Return all pairs with the minimum absolute difference
29 return result;
30 }
31}
32
1class Solution {
2public:
3 vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
4 // Sort the input array.
5 sort(arr.begin(), arr.end());
6
7 // Initialize the minimum absolute difference as a large value.
8 int minDifference = INT_MAX;
9
10 // Calculate the size of the input array.
11 int n = arr.size();
12
13 // Loop through the sorted array to find the minimum absolute difference.
14 for (int i = 0; i < n - 1; ++i) {
15 minDifference = min(minDifference, arr[i + 1] - arr[i]);
16 }
17
18 // Initialize an empty vector to store pairs with the minimum absolute difference.
19 vector<vector<int>> result;
20
21 // Loop through the array once more to find all pairs with the minimum absolute difference.
22 for (int i = 0; i < n - 1; ++i) {
23 if (arr[i + 1] - arr[i] == minDifference) {
24 // Add the pair to the result vector.
25 result.push_back({arr[i], arr[i + 1]});
26 }
27 }
28
29 // Return the vector containing all pairs of integers with the minimum absolute difference.
30 return result;
31 }
32};
33
1function minimumAbsDifference(arr: number[]): number[][] {
2 // Sort the input array in non-decreasing order
3 arr.sort((a, b) => a - b);
4
5 // Initialize the minimum difference to a large number
6 let minDifference = Number.MAX_SAFE_INTEGER;
7
8 // Calculate the number of elements in the array
9 const n = arr.length;
10
11 // Find the minimum absolute difference between any two adjacent elements
12 for (let i = 0; i < n - 1; ++i) {
13 minDifference = Math.min(minDifference, arr[i + 1] - arr[i]);
14 }
15
16 // Prepare an array to store pairs with the minimum absolute difference
17 const result: number[][] = [];
18
19 // Populate the result array with pairs of numbers that have the minimum difference
20 for (let i = 0; i < n - 1; ++i) {
21 if (arr[i + 1] - arr[i] === minDifference) {
22 result.push([arr[i], arr[i + 1]]);
23 }
24 }
25
26 // Return the array with all pairs having the minimum absolute difference
27 return result;
28}
29
Time and Space Complexity
The given Python code snippet defines a function minimumAbsDifference
that finds all the pairs of elements in a list with the smallest absolute difference. Here is the analysis of its computational complexity:
Time Complexity
- Sorting the array:
arr.sort()
is used, which has a time complexity ofO(n log n)
wheren
is the number of elements inarr
. - Finding the minimum absolute difference: The comprehension
min(b - a for a, b in pairwise(arr))
iterates over the array once, which gives a time complexity ofO(n-1)
, simplifying toO(n)
. - Generating the list of pairs with the smallest absolute difference: The list comprehension
[[a, b] for a, b in pairwise(arr) if b - a == mi]
also iterates over the array once, resulting in the time complexity ofO(n)
.
Since the sorting step dominates the overall time complexity, the final time complexity of the entire function is O(n log n)
.
Space Complexity
- The sorted list: In-place sorting is used so no additional space complexity is introduced for sorting beyond the variable reassignments, which is
O(1)
. - The minimum absolute difference: The minimum value
mi
is found with a generator expression, so the space complexity for this step isO(1)
. - The output list: The space complexity is proportional to the number of pairs with the smallest absolute difference. In the worst case, all pairs have the same minimum absolute difference, thus the space complexity is
O(n)
.
So, the space complexity for the function is O(n)
with respect to the output size.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.