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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5 return (*(int*)a - *(int*)b);
6}
7
8int** minimumAbsDifference(int* arr, int arrSize, int* returnSize, int** returnColumnSizes) {
9 qsort(arr, arrSize, sizeof(int), compare);
10 int minDiff = __INT_MAX__;
11 for (int i = 1; i < arrSize; i++) {
12 if (arr[i] - arr[i-1] < minDiff) {
13 minDiff = arr[i] - arr[i-1];
14 }
15 }
16 int** result = malloc(arrSize * sizeof(int*));
17 *returnColumnSizes = malloc(arrSize * sizeof(int));
18 *returnSize = 0;
19 for (int i = 1; i < arrSize; i++) {
20 if (arr[i] - arr[i-1] == minDiff) {
21 result[*returnSize] = malloc(2 * sizeof(int));
22 result[*returnSize][0] = arr[i-1];
23 result[*returnSize][1] = arr[i];
24 (*returnColumnSizes)[*returnSize] = 2;
25 (*returnSize)++;
26 }
27 }
28 return result;
29}
30This C solution sorts the input array using quicksort and then computes the minimum difference between consecutive elements. Using this minimum difference, it collects all pairs satisfying this difference and stores them in the result array, which is then returned.
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.
1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5 public List<List<Integer>> minimumAbsDifference(int[] arr) {
6 int minDiff = Integer.MAX_VALUE;
7 List<List<Integer>> result = new ArrayList<>();
8 for (int i = 0; i < arr.length; i++) {
9 for (int j = i + 1; j < arr.length; j++) {
10 int diff = Math.abs(arr[i] - arr[j]);
11 if (diff < minDiff) {
12 minDiff = diff;
13 result.clear();
14 result.add(List.of(arr[i], arr[j]));
15 } else if (diff == minDiff) {
16 result.add(List.of(arr[i], arr[j]));
17 }
18 }
19 }
20 return result;
21 }
22}
23The Java approach explicitly investigates each element pair, calculating their differences, updating the minimum difference, and storing viable pairs in a list that is returned on completion.