Problem of The Day: Minimum Absolute Difference

Problem Statement

leetcode problem link

Solution [TLE]

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        N = len(arr)
        arr.sort()
        diff = {}
        min_diff = float('inf')
        for i in range(N):
            for j in range(i, N):
                if i != j:
                    k = abs(arr[i] - arr[j])
                    min_diff = min(min_diff, k)
                    diff[k] = diff.get(k, [])
                    curr = [arr[i], arr[j]]
                    if [arr[i], arr[j]] not in diff[k]:
                        diff[k].append(curr[:])

        return diff[min_diff]

Solution [Accepted]

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        N = len(arr)
        arr.sort()
        diff = {}
        min_diff = float('inf')
        for i in range(1, N):
            delta = arr[i] - arr[i - 1]
            diff[delta] = diff.get(delta, [])
            diff[delta].append([arr[i - 1], arr[i]])
            min_diff = min(min_diff, delta)

        return diff[min_diff]

Solution in CSharp

public class Solution {
    public IList<IList<int>> MinimumAbsDifference(int[] arr) {
        IList<IList<int>> result = new List<IList<int>>();
        int minDiff = int.MaxValue;
        Array.Sort(arr);
        for(int i = 1; i < arr.Length; i++) {
            minDiff = Math.Min(minDiff, arr[i] - arr[i - 1]);
        }

        for (int i = 1; i < arr.Length; i++) {
            if ((arr[i] - arr[i - 1]) == minDiff) {
                result.Add(new List<int> { arr[i - 1], arr[i]});
            }
        }
        return result;
    }
}

Editorial

Approach 1: Sort + 2 Traversals

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        # Sort the original array
        arr.sort()
        answer = []

        # Initialize minimum difference as a huge integer in order not
        # to miss the absolute difference of the first pair.
        min_pair_diff = float('inf')

        # Traverse the sorted array and calcalute the minimum absolute difference.
        for i in range(len(arr) - 1):
            min_pair_diff = min(min_pair_diff, arr[i + 1] - arr[i])

        # Traverse the sorted array and check every pair again, if
        # the absolute difference equals the minimum difference,
        # add this pair to the answer list.
        for i in range(len(arr) - 1):
            if arr[i + 1] - arr[i] == min_pair_diff:
                answer.append([arr[i], arr[i + 1]])
        return answer

time: O(nlogn) space: O(n)

Approach 2: Sort + 1 Traversal

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        # Sort the original array
        arr.sort()

        # Initialize minimum difference `min_pair_diff` as a huge integer in order not
        # to miss the absolute difference of the first pair.
        min_pair_diff = float('inf')
        answer = []

        # Traverse the sorted array
        for i in range(len(arr) - 1):
            # For the absolute value `curr_pair_diff` of the current pair:
            curr_pair_diff = arr[i + 1] - arr[i]

            # If `curr_pair_diff` equals `min_pair_diff`, add this pair to the answer list.
            # If `curr_pair_diff` is smaller than `min_pair_diff`, discard all pairs in the answer list,
            # add this pair to the answer list and update `min_pair_diff`.
            # If `curr_pair_diff` is larger than `min_pair_diff`, we just go ahead.
            if curr_pair_diff == min_pair_diff:
                answer.append([arr[i], arr[i + 1]])
            elif curr_pair_diff < min_pair_diff:
                answer = [[arr[i], arr[i + 1]]]
                min_pair_diff = curr_pair_diff

        return answer