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 = [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 <= 10^5
-10^6 <= arr[i] <= 10^6
Solution:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LeetCode.AskGif.Easy.Array
{
public class MinimumAbsDifferenceSoln
{
public IList<IList<int>> MinimumAbsDifference(int[] arr)
{
int minDiff = int.MaxValue;
int diff = 0;
var res = new List<IList<int>>();
//Sort the array in ascending order
arr = arr.OrderBy(x => x).ToArray();
for (int i = 1; i < arr.Length; i++)
{
diff = arr[i] - arr[i - 1];
if(diff < minDiff)
{
res.Clear();
res.Add(new List<int>() { arr[i - 1], arr[i] });
minDiff = diff;
}
else if(diff == minDiff)
{
res.Add(new List<int>() { arr[i - 1], arr[i] });
}
}
return res;
}
}
}
Time Complexity: O(nlogn) Using QuickSort
Space Complexity: O(n) For storing the result
Unit Tests:
using LeetCode.AskGif.Easy.Array;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
using System.Collections.Generic;
using System.Text;
namespace CodingUnitTest.Easy.Array
{
[TestClass]
public class MinimumAbsDifferenceSolnTests
{
[TestMethod]
public void MinimumAbsDifferenceSoln_First()
{
var chips = new int[] { 4, 2, 1, 3 };
var output = new int[,] {
{ 1, 2 },
{ 2, 3 },
{ 3, 4 }
};
var res = new MinimumAbsDifferenceSoln().MinimumAbsDifference(chips);
AreEqual(output, res);
}
[TestMethod]
public void MinimumAbsDifferenceSoln_Second()
{
var chips = new int[] { 1, 3, 6, 10, 15 };
var output = new int[,] {
{ 1, 3 }
};
var res = new MinimumAbsDifferenceSoln().MinimumAbsDifference(chips);
AreEqual(output, res);
}
[TestMethod]
public void MinimumAbsDifferenceSoln_Third()
{
var chips = new int[] { 3, 8, -10, 23, 19, -4, -14, 27 };
var output = new int[,] {
{ -14, -10 },
{ 19, 23 },
{ 23, 27 }
};
var res = new MinimumAbsDifferenceSoln().MinimumAbsDifference(chips);
AreEqual(output, res);
}
private void AreEqual(int[,] output, IList<IList<int>> res)
{
for (int i = 0; i < output.GetLength(0); i++)
{
for (int j = 0; j < output.GetLength(1); j++)
{
Assert.AreEqual(output[i, j], res[i][j]);
}
}
}
}
}
