Minimum Absolute Difference
- 2 min read
- Array
- LC-Easy
3 years ago
Solution
- Sort numbers, and iterate once to get smallest difference
- Iterate second time, and check consecutive numbers if their diff is equal to smallest difference, and if so, append to answer
- We can reduce to only one iteration by using the difference between each consecutive number as the key, and the value is a list of number pairs. Whilst we're adding new elements to the dictionary, just keep track of the smallest diff seen so far
| Time | Space | Explanation |
|---|---|---|
O(nlogn) | O(n) | (space from sorting) |
function minimumAbsDifference(arr: number[]): number[][] {
const pairs = [];
arr.sort((a, b) => a - b);
let smallest_diff = Infinity;
for (let i = 0; i < arr.length - 1; i++) {
const diff = Math.abs(arr[i + 1] - arr[i]);
smallest_diff = Math.min(diff, smallest_diff)
}
for(let i = 0; i < arr.length - 1; i++) {
const diff = Math.abs(arr[i + 1] - arr[i]);
if (diff === smallest_diff) {
pairs.push([arr[i], arr[i + 1]]);
}
}
return pairs;
};
Optimized Solution (O(n) time vs. O(2n))
Only does one pass instead of two
function minimumAbsDifference(arr: number[]): number[][] {
const pairs = {};
arr.sort((a, b) => a - b);
let smallest_diff = Infinity;
for(let i = 0; i < arr.length - 1; i++) {
const diff = Math.abs(arr[i + 1] - arr[i]);
smallest_diff = Math.min(diff, smallest_diff);
if (!Object.hasOwn(pairs, diff)) {
pairs[diff] = [];
}
pairs[diff].push([arr[i], arr[i + 1]]);
}
return pairs[smallest_diff];
};
TLE Solution
| Time | Space | Explanation |
|---|---|---|
O(nlogn + n^2) | O(n) | (space from sorting) |
- Double for loop, check each number with each other and see if difference equals absolute smallest difference (that was pre-computed)
function minimumAbsDifference(arr: number[]): number[][] {
const pairs = [];
arr.sort((a, b) => a - b);
let smallest_diff = Infinity;
for (let i = 0; i < arr.length - 1; i++) {
const diff = Math.abs(arr[i + 1] - arr[i]);
smallest_diff = Math.min(diff, smallest_diff)
}
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
const diff = Math.abs(arr[j] - arr[i]);
if (diff === smallest_diff) {
pairs.push([arr[i], arr[j]]);
}
}
}
return pairs;
};