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

1. a, b is from arr 2. a < b 3. 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]]

Solution

There are many solutions to the problem.

Solution 1: Brute Force
1. Iterate over the Array and find a minimum difference. 2. Iterate Array in two nested loops to explore all pairs with respect to minimum difference.

Time Complexity : O(n2)

Solution 2: Sorting
1. Iterate over the Array and find a minimum difference. 2. Sort Array before iterate. 2. Iterate array with a single loop [ as minimum difference pair will come next one element to other].

Time Complexity : O(nlogn)

Code

[[-14, -10], [19, 23], [23, 27]]

We acknowledge you to write a comment if you have a better solution or having any doubt on the above topic.

Leave a Reply

Your email address will not be published. Required fields are marked *