The first approach involves sorting the array and then iterating through it to find the pairs with the minimum absolute difference. By sorting, the smallest differences can only occur between consecutive elements. Hence, we sort the array and compute differences between adjacent elements to find the minimum difference.
Steps:
Time Complexity: O(n log n), due to sorting the array. Space Complexity: O(1), not considering the output space.
1def minimumAbsDifference(arr):
2 arr.sort()
3 min_diff = float('inf')
4 result = []
5 for i in range(1, len(arr)):
6 diff = arr[i] - arr[i - 1]
7 if diff < min_diff:
8 min_diff = diff
9 result = [[arr[i - 1], arr[i]]]
10 elif diff == min_diff:
11 result.append([arr[i - 1], arr[i]])
12 return result
13This Python solution sorts the list initially and calculates the difference between consecutive elements. It keeps track of the minimum difference and collects pairs that have this difference, placing them in the result list accordingly.
The second approach compares all pairs of elements to determine their absolute differences. This method ensures that all possible pairs are considered, and the pairs with the minimum difference are identified. Although not as efficient as the first approach, it explicitly checks every possible pair.
Steps:
Time Complexity: O(n^2), considering all pair combinations. Space Complexity: O(1), excluding result space.
1#include <stdio.h>
2#include <stdlib.h>
3#include <limits.h>
4
5int compare(const void *a, const void *b) {
6 return (*(int*)a - *(int*)b);
7}
8
9int** minimumAbsDifference(int* arr, int arrSize, int* returnSize, int** returnColumnSizes) {
10 *returnSize = 0;
11 int minDiff = INT_MAX;
12 for (int i = 0; i < arrSize; i++) {
13 for (int j = i + 1; j < arrSize; j++) {
14 int diff = arr[j] - arr[i];
15 if (diff < 0) diff = -diff;
16 if (diff < minDiff) {
17 minDiff = diff;
18 }
19 }
20 }
21 for (int i = 0; i < arrSize; i++) {
22 for (int j = i + 1; j < arrSize; j++) {
23 int diff = arr[j] - arr[i];
24 if (diff < 0) diff = -diff;
25 if (diff == minDiff) (*returnSize)++;
26 }
27 }
28 int** result = malloc(*returnSize * sizeof(int*));
29 *returnColumnSizes = malloc(*returnSize * sizeof(int));
30 int idx = 0;
31 for (int i = 0; i < arrSize; i++) {
32 for (int j = i + 1; j < arrSize; j++) {
33 int diff = arr[j] - arr[i];
34 if (diff < 0) diff = -diff;
35 if (diff == minDiff) {
36 result[idx] = malloc(2 * sizeof(int));
37 result[idx][0] = arr[i];
38 result[idx][1] = arr[j];
39 (*returnColumnSizes)[idx] = 2;
40 idx++;
41 }
42 }
43 }
44 return result;
45}
46This C implementation evaluates all pairs of elements to calculate their absolute differences, records the minimum difference detected, and accumulates the pairs with this difference in an array subsequently returned.