1200. Minimum Absolute Difference #

Problem #

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

Problem Summary #

Given an array, find all pairs [a,b] that satisfy the conditions: a<b and the difference b-a is the minimum difference among all pairs of elements in the array.

Solution Approach #

• Given an array, find all pairs [a,b] that satisfy the conditions: a<b and the difference b-a is the minimum difference among all pairs of elements in the array.
• Easy problem. Sort according to the problem statement, then sequentially calculate the difference between every two adjacent elements and find the minimum difference. Finally, traverse the array once and output all pairs whose difference equals the minimum difference.

Code #

package leetcode

import (
	"math"
	"sort"
)

func minimumAbsDifference(arr []int) [][]int {
	minDiff, res := math.MaxInt32, [][]int{}
	sort.Ints(arr)
	for i := 1; i < len(arr); i++ {
		if arr[i]-arr[i-1] < minDiff {
			minDiff = arr[i] - arr[i-1]
		}
		if minDiff == 1 {
			break
		}
	}
	for i := 1; i < len(arr); i++ {
		if arr[i]-arr[i-1] == minDiff {
			res = append(res, []int{arr[i-1], arr[i]})
		}
	}
	return res
}