Blogs Hub

Minimum Absolute Difference - Array - Easy - LeetCode - MiniTV

Minimum Absolute Difference - Array - Easy - LeetCode - मिनी टीवी

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]);
                }
            }
        }
    }
}