-
Notifications
You must be signed in to change notification settings - Fork 22
Expand file tree
/
Copy path1200.minimum-absolute-difference.cpp
More file actions
62 lines (55 loc) · 1.44 KB
/
1200.minimum-absolute-difference.cpp
File metadata and controls
62 lines (55 loc) · 1.44 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// Tag: Array, Sorting
// Time: O(N)
// Space: O(N)
// Ref: -
// Note: -
// 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 <= 105
// -106 <= arr[i] <= 106
//
//
class Solution {
public:
vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
int n = arr.size();
sort(arr.begin(), arr.end());
int min_diff = INT_MAX;
vector<vector<int>> res;
for (int i = 0; i < n - 1; i++) {
int diff = arr[i + 1] - arr[i];
if (diff < min_diff) {
res.clear();
min_diff = diff;
}
if (diff == min_diff) {
res.push_back({arr[i], arr[i + 1]});
}
}
return res;
}
};