Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1200.html

1200. Minimum Absolute Difference (Easy)

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

Related Topics:
Array

Solution 1.

  • class Solution {
        public List<List<Integer>> minimumAbsDifference(int[] arr) {
            Arrays.sort(arr);
            int minDifference = Integer.MAX_VALUE;
            int length = arr.length;
            for (int i = 1; i < length; i++) {
                int difference = arr[i] - arr[i - 1];
                minDifference = Math.min(minDifference, difference);
            }
            List<List<Integer>> pairs = new ArrayList<List<Integer>>();
            for (int i = 1; i < length; i++) {
                int difference = arr[i] - arr[i - 1];
                if (difference == minDifference) {
                    List<Integer> pair = new ArrayList<Integer>();
                    pair.add(arr[i - 1]);
                    pair.add(arr[i]);
                    pairs.add(pair);
                }
            }
            return pairs;
        }
    }
    
    ############
    
    class Solution {
        public List<List<Integer>> minimumAbsDifference(int[] arr) {
            Arrays.sort(arr);
            List<List<Integer>> ans = new ArrayList<>();
            int n = arr.length;
            int mi = Integer.MAX_VALUE;
            for (int i = 0; i < n - 1; ++i) {
                int a = arr[i], b = arr[i + 1];
                int d = b - a;
                if (d < mi) {
                    ans.clear();
                    ans.add(Arrays.asList(a, b));
                    mi = d;
                } else if (d == mi) {
                    ans.add(Arrays.asList(a, b));
                }
            }
            return ans;
        }
    }
    
  • // OJ: https://leetcode.com/problems/minimum-absolute-difference/
    // Time: O(NlogN)
    // Space: O(1) extra space
    class Solution {
    public:
        vector<vector<int>> minimumAbsDifference(vector<int>& A) {
            sort(begin(A), end(A));
            int N = A.size(), minDiff = INT_MAX;
            vector<vector<int>> ans;
            for (int i = 1; i < N; ++i) minDiff = min(minDiff, A[i] - A[i - 1]);
            for (int i = 1; i < N; ++i) {
                if (A[i] - A[i - 1] == minDiff) ans.push_back({ A[i - 1], A[i] });
            }
            return ans;
        }
    };
    
  • class Solution:
        def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
            arr.sort()
            ans = []
            mi = inf
            for a, b in pairwise(arr):
                d = b - a
                if d < mi:
                    ans = [(a, b)]
                    mi = d
                elif d == mi:
                    ans.append((a, b))
            return ans
    
    ############
    
    # 1200. Minimum Absolute Difference
    # https://leetcode.com/problems/minimum-absolute-difference/
    
    class Solution:
        def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
            arr.sort()
            m = min(b - a for a,b in zip(arr, arr[1:]))
            return [[a,b] for a,b in zip(arr, arr[1:]) if b - a == m]
            
    
    
  • func minimumAbsDifference(arr []int) [][]int {
    	sort.Ints(arr)
    	mi := math.MaxInt32
    	var ans [][]int
    	for i, a := range arr[:len(arr)-1] {
    		b := arr[i+1]
    		d := b - a
    		if d < mi {
    			mi = d
    			ans = [][]int{[]int{a, b} }
    		} else if d == mi {
    			ans = append(ans, []int{a, b})
    		}
    	}
    	return ans
    }
    
  • function minimumAbsDifference(arr: number[]): number[][] {
        arr.sort((a, b) => a - b);
        let mi = 1 << 30;
        const n = arr.length;
        for (let i = 0; i < n - 1; ++i) {
            mi = Math.min(mi, arr[i + 1] - arr[i]);
        }
        const ans: number[][] = [];
        for (let i = 0; i < n - 1; ++i) {
            if (arr[i + 1] - arr[i] === mi) {
                ans.push([arr[i], arr[i + 1]]);
            }
        }
        return ans;
    }
    
    

All Problems

All Solutions