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 <vector>
2#include <algorithm>
3
4std::vector<std::vector<int>> minimumAbsDifference(std::vector<int>& arr) {
5 std::sort(arr.begin(), arr.end());
6 int minDiff = INT_MAX;
7 std::vector<std::vector<int>> result;
8 for (size_t i = 1; i < arr.size(); ++i) {
9 int diff = arr[i] - arr[i - 1];
10 if (diff < minDiff) {
11 minDiff = diff;
12 result.clear();
13 result.push_back({arr[i - 1], arr[i]});
14 } else if (diff == minDiff) {
15 result.push_back({arr[i - 1], arr[i]});
16 }
17 }
18 return result;
19}
20This C++ solution also sorts the array first. It then uses a loop to calculate the minimum difference and adjusts the result vector based on whether a new minimum is found or if the current difference is equal to the minimum difference found earlier.
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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public IList<IList<int>> MinimumAbsDifference(int[] arr) {
6 int minDiff = int.MaxValue;
7 List<IList<int>> result = new List<IList<int>>();
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(new List<int> { arr[i], arr[j] });
15 } else if (diff == minDiff) {
16 result.Add(new List<int> { arr[i], arr[j] });
17 }
18 }
19 }
20 return result;
21 }
22}
23The C# solution thoroughly examines each set of potential pairs, calculates their differences, updates the minimum difference determined, and stores the results in a list formatted for return.