Teaching Kids Programming: Videos on Data Structures and Algorithms
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 arrExample 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]]
Minimum Absolute Difference via Bruteforce Algorithm
We can bruteforce the pairs in O(N^2) time and obtain the min difference first, then we can iterate again to construct the result.
1 2 3 4 5 6 7 8 9 10 11 12 13 | class Solution: def minimumAbsDifference(self, nums: List[int]) -> List[List[int]]: n = len(nums) minDiff = math.inf for i in range(n): for j in range(i): minDiff = min(minDiff, abs(nums[i] - nums[j])) ans = [] for i in range(n): for j in range(i): if abs(nums[i] - nums[j]) == minDiff: ans.append([min(nums[i], nums[j]), max(nums[i], nums[j])]) return sorted(ans) |
class Solution:
def minimumAbsDifference(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
minDiff = math.inf
for i in range(n):
for j in range(i):
minDiff = min(minDiff, abs(nums[i] - nums[j]))
ans = []
for i in range(n):
for j in range(i):
if abs(nums[i] - nums[j]) == minDiff:
ans.append([min(nums[i], nums[j]), max(nums[i], nums[j])])
return sorted(ans)The time complexity is O(N^2) + O(NLogN) which is O(N^2). We can do this in one go, if we find a smaller Min Difference, we clear the array and append the current pair.
We need to sort the answer array in O(NLogN).
Below is the one-pass algorithm:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | class Solution: def minimumAbsDifference(self, nums: List[int]) -> List[List[int]]: n = len(nums) minDiff = math.inf ans = [] for i in range(n): for j in range(i): curDiff = abs(nums[i] - nums[j]) if curDiff < minDiff: minDiff = curDiff ans = [[min(nums[i], nums[j]), max(nums[i], nums[j])]] elif curDiff == minDiff: ans.append([min(nums[i], nums[j]), max(nums[i], nums[j])]) return sorted(ans) |
class Solution:
def minimumAbsDifference(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
minDiff = math.inf
ans = []
for i in range(n):
for j in range(i):
curDiff = abs(nums[i] - nums[j])
if curDiff < minDiff:
minDiff = curDiff
ans = [[min(nums[i], nums[j]), max(nums[i], nums[j])]]
elif curDiff == minDiff:
ans.append([min(nums[i], nums[j]), max(nums[i], nums[j])])
return sorted(ans)The time complexity is still O(N^2).
Minimum Absolute Difference via Sorting Algorithm
We can sort the array in O(NLogN) time, and then the min difference must be in the adjacent numbers (first pass). Then the second pass is to add pairs with the min difference.
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution: def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]: n = len(arr) arr.sort() minDiff = math.inf for i in range(1, n): minDiff = min(minDiff, arr[i] - arr[i - 1]) ans = [] for i in range(1, n): if arr[i] - arr[i - 1] == minDiff: ans.append([arr[i - 1], arr[i]]) return ans |
class Solution:
def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
n = len(arr)
arr.sort()
minDiff = math.inf
for i in range(1, n):
minDiff = min(minDiff, arr[i] - arr[i - 1])
ans = []
for i in range(1, n):
if arr[i] - arr[i - 1] == minDiff:
ans.append([arr[i - 1], arr[i]])
return ansAgain, we can do this in one-pass:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | class Solution: def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]: n = len(arr) arr.sort() minDiff = math.inf ans = [] for i in range(1, n): curDiff = arr[i] - arr[i - 1] if curDiff < minDiff: minDiff = curDiff ans = [[arr[i - 1], arr[i]]] elif curDiff == minDiff: ans.append([arr[i - 1], arr[i]]) return ans |
class Solution:
def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
n = len(arr)
arr.sort()
minDiff = math.inf
ans = []
for i in range(1, n):
curDiff = arr[i] - arr[i - 1]
if curDiff < minDiff:
minDiff = curDiff
ans = [[arr[i - 1], arr[i]]]
elif curDiff == minDiff:
ans.append([arr[i - 1], arr[i]])
return ansBoth implementations using sorting require O(NLogN) time.
–EOF (The Ultimate Computing & Technology Blog) —
Last Post: Teaching Kids Programming - Day of the Year (Leap Year Algorithm)
Next Post: Teaching Kids Programming - Minimum Starting Nodes to Visit Graph (Topological Sort, Indegree)