If you have got the list [5, 2, 3, 4, 1]
Sort in as [1, 2, 3, 4, 5] to see that several pair have the minimum difference 1: [(1, 2), (2, 3), (3, 4), (4, 5)].
The return array would be [1, 2, 3, 3, 4, 4, 5]
Let’s understand the question.
There is a list given to us
[1, 9, 2, 3, 4]
We first sort them
[1, 2, 3, 4, 9]
Now we find the minimum difference among the sorted list.
Then, we will return the pairs which have the minimum difference value.
Step 1: Sort the array in a variable in O(n log n) time where n = length of array.
Step 2: Create a new array to store the result
Step 3: Run a loop to find the absolute minimum difference among all the pairs
Step 4: Again run a loop to find the pairs which are equal to the minimum difference
Time complexity: O(n log n) + O(n) + O(n) = O(n log n)
Space complexity: O(2(n – 1)) //Maximum (worst case) 4 the difference among each pair is same.