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 arr
  • a < b
  • 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 = [3,8,-10,23,19,-4,-14,27]
Output: [[-14,-10],[19,23],[23,27]]

Solution:

How can we approach this problem?

In this article I’m gonna to guide you to tackle this problem.

To solve this, you must have a good understanding of

  1. Array.Sort() method – It sorts the array in ascending order
  2. Math.Abs() and Math.Min() built-in functions in C#

Math.Abs()

For example, Math.Abs(-10) gives 10, Math.Abs(-4) gives 4, Math.Abs(5) gives 5.

It ignores the negative sign gives only the absolute value. To get the absolute number we use Math.Abs() method.

Math.Min()

For example, Math.Min(4,2) gives 2. It compares the two values and returns the minimum value.

Simple and Efficient algorithm

  • Consider this example, arr = [4,2,1,3]
  • First Sort the Array using Array.Sort(arr) method.
  • Then arr=[1,2,3,4]
  • Second, initialize one variable to find the minimum difference value in the array. In this case, I initialized the variable minDistance with maximum integer value. I assigned maximum value, so it is easy for me to track the minimum value in the array.
  • Third find the minimum value in the array, by using Math.Abs() and Math.Min() functions.

for(int i=1;i<arr.Length;i++)
{
minDistance = Math.Min( Math.Abs(arr[i] – arr[i-1]) , minDistance);
}

  • From this step, we got a minimum absolute difference value in the array.
  • Based on that value, track the array once again to get the pair which is equal to the minDistance. After that, construct a list based on that.

C# program for finding Minimum absolute difference

public class Solution {
public IList<IList<int>> MinimumAbsDifference(int[] arr) {
Array.Sort(arr);
int minDistance = Int32.MaxValue;
var list = new List<IList<int>>();

for(int i=1;i<arr.Length;i++)
{
    minDistance = Math.Min(Math.Abs(arr[i] - arr[i-1]), minDistance); 
}

for(int i=1;i<arr.Length;i++)
{
   if(Math.Abs(arr[i] - arr[i-1]) == minDistance)
   {
        var l = new List<int>();    
        l.Add(arr[i-1]);
        l.Add(arr[i]);
        list.Add(l);
   }
}
return list;
}
}

Note: In the above program, > sign is replaced by &get; by this code editor. Make sure, it is >.

Time Complexity is O(nlogn), since we have used Array.Sort() method. It takes O(nlogn) times to sort the array.

Space Complexity is O(n).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s