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 arra < bb - 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] <= 106The 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:
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n), due to sorting the array. Space Complexity: O(1), not considering the output space.
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:
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), considering all pair combinations. Space Complexity: O(1), excluding result space.
| Approach | Complexity |
|---|---|
| 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. |
Minimum Distance between BST Nodes - Leetcode 783 - Python • NeetCodeIO • 22,987 views views
Watch 9 more video solutions →Practice Minimum Absolute Difference with our built-in code editor and test cases.
Practice on FleetCode