[LeetCode] 1200. Minimum Absolute Difference

 Problem : https://leetcode.com/problems/minimum-absolute-difference/

Because the minimum difference can only exist between 2 consecutive elements in sorted list.

We sort the input array first, then find the pairs with minimum difference.

Time complexity = O(N * LogN) + O(N),  N = length of the input array.

class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        int miGlobal = Integer.MAX_VALUE;
        List<List<Integer>> result = new ArrayList();
        
        // minimum absolute difference can only exist between 2 consecutive elements
        Arrays.sort(arr);
        
        for (int i = 1; i < arr.length; i++) {
            int miLocal = arr[i] - arr[i-1];
            if (miLocal < miGlobal) {
                // start a new result when find a new minimum difference
                miGlobal = miLocal;
                result = new ArrayList(Arrays.asList(Arrays.asList(arr[i-1], arr[i])));
            } else if (miLocal == miGlobal) {
                // otherwise append this new pair to the result list.
                result.add(Arrays.asList(arr[i-1], arr[i]));
            }
        }
        
        return result;
    }
}

Because the value range of the input array is from -10^6 to 10^6, the input array can be sorted with counting sort approach which Time complexity is O(N)