Find The Closest Numbers From A List Of Unsorted Integers In C++

In this guide, we will explore the process of determining the nearest numbers from an array of disorganized whole numbers using C++.

Problem Statement

From an unordered collection of various integers, our objective is to identify the pair of elements with the smallest absolute difference between them. In cases where there are multiple pairs meeting this criterion, we are required to determine each such pair. It is important to note that whenever the term "difference" is mentioned in this context, it always pertains to the absolute difference between two values.

Examples:

Input: [44, 42, 40, 23, 55]
Output: Pairs with minimum difference are:
  44 and 42
  42 and 40

The sets (44, 42) and (42, 40) exhibit the smallest variance. The numerical variance between forty and forty-two, as well as between forty and forty-four, is exactly two.

Input: [500, 200, 400, 300, 100]
Output: Pairs with a minimum difference:
  100 and 200
  200 and 300
  300 and 400
  400 and 500

In this scenario, since all pairs share a consistent difference of 100, the program will display all pairs.

Naive Approach

To address this issue using a brute-force approach, examine each combination of items within the collection and determine the exact variance between them.

The approach consists of the following steps -

• ✅ Examine the integer input list.
• ✅ Put INTMAX as mindiff.
• ✅ Create the variables mini and minj to save the indices of the pair with the least difference.
• ✅ As we go over the list, compare each entry with every other entry.
• ✅ If the absolute difference between the two elements is less than mindiff, update mindiff and save the indices of the two elements in mini and minj.
• ✅ Add the indices to a list of pairs if the absolute difference equals min_diff.

Example:

Let's consider an illustration to determine the nearest number from an array of disordered integers in C++.

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;
int main() {
vector<int> nums = {4, 5, 1, 7};
int min_diff = INT_MAX;
int n = nums.size();
vector<pair<int, int>> p;
for (int i = 0; i < n-1; i++) {
int diff = 0;
for (int j = i+1; j < n; j++) {
diff = abs(nums[i] - nums[j]);
if (diff < min_diff) {
min_diff = diff;
p.clear();
p.push_back(make_pair(i, j));
}
else if (diff == min_diff) {
p.push_back(make_pair(i, j));
}
}
}
for (auto x : p) {
cout << nums[x.first] << ", " << nums[x.second] << endl;
}
return 0;
}

Output:

Explanation:

• ✅ nums: A vector of integers.
• ✅ min_diff: Variable to store the minimum difference found, initialized to the maximum possible integer value.
• ✅ n: The size of the vector nums.
• ✅ p: A vector to store pairs of indices that have the minimum difference.
• ✅ The first element to the second-to-last element is where the outer loop begins.
• ✅ Every element i that comes after it is compared to all subsequent elements j in the inner loop.
• ✅ diff determines how much the elements at indices i and j differ absolute from one another.
• ✅ Update mindiff and clear vector p to hold the new pair if diff is less than the current mindiff.
• ✅ Add the new pair to p if diff equals min_diff.
• ✅ Print the pairs of numbers from nums that have the least difference when you iterate through the vector p.

Time and Space Complexity Analysis

Time complexity: O(n2)

Its time complexity is O(n^2) due to the utilization of two nested loops to check each element against every other element within the list. The outer loop iterates (n-1) times, while the inner loop iterates (n - i - 1) times, where n represents the size of the list. In total, there are (n - 1) + (n - 2) +... + 1 = n(n - 1) / 2 comparisons, leading to the O(n^2) time complexity.

Space complexity: O(k)

It operates with an O(k) space complexity, with k representing the count of pairs with the smallest absolute difference. The storage of pair indices in a vector of pairs is the reason behind this space requirement. In scenarios where all pairs share the same minimum absolute difference, K could potentially reach up to n(n-1)/2, denoting the highest possible pair combinations in a list of n elements. Therefore, the program's space complexity is O(n^2).

Optimized Approach

After sorting the list, we can compare neighboring entries to find the least absolute difference. However, optimizing the method would take O(log (n)) time.The approach consists of the following steps -

• ✅ In the list, the integers are arranged in ascending order.
• ✅ Set the initial values of the variables "min_diff" and "pairs" so that they may be used to store the smallest absolute difference and the pairs that share it.
• ✅ Go through the sorted list and compare adjacent components to find the one with the least absolute difference.
• ✅ If a lesser absolute difference is found, update the'minabsdiff,' clear the 'pairs' list, and add the current pair to it.
• ✅ If the same absolute difference is found, the current pair should be added to the "pairs" list.
• ✅ Print the "pairs" list as a last step.

Example:

Consider another scenario where we aim to identify the nearest number from an array of unsorted whole numbers using C++ programming language.

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int main(){
vector<int> nums = {12, 3, 19, 15, 6, 8, 1};
sort(nums.begin(), nums.end());
int minDiff = INT_MAX;
vector<pair<int, int>> p;
for (int i = 1; i < nums.size(); i++) {
int diff = abs(nums[i] - nums[i - 1]);
if (diff < minDiff) {
minDiff = diff;
p.clear();
p.push_back(make_pair(nums[i - 1], nums[i]));
}
else if (diff == minDiff) {
p.push_back(make_pair(nums[i - 1], nums[i]));
}
}
for (auto x : p)    {
cout << x.first << ", " << x.second << endl;
}
cout << endl;
return 0;
}

Output:

Explanation:

• ✅ There is an ascending order of sort for the nums vector. It takes O(nlogn) time to sort.
• ✅ Next, set minDiff's starting value to the biggest integer that can be found.
• ✅ Proceed to iterate over the sorted vector, beginning with the second member.
• ✅ Determine the exact variations between each element and its antecedent.
• ✅ Update minDiff, clear pairings vector p, and add the new pair if the difference is less than the current minDiff.
• ✅ Add the new pair to p if the difference is equal to the current minDiff.
• ✅ Print each pair of values that has the least difference as you iterate through the vector p.

Time and Space Complexity Analysis

Time Complexity: O(nlog(n))

The time complexity of this code snippet is O(nlog(n)), where n represents the quantity of numbers within the provided list. This arises from the sorting process of the input list in O(nlog(n)) time, followed by the subsequent iteration through the sorted list to identify pairs with the smallest absolute difference, an operation that consumes O(n) time. The cumulative time complexity is O(nlog(n)), as it supersedes O(n) due to its higher computational demand.

Space Complexity: O(k)

The quantity of pairings having the least absolute variance is represented by k, and the memory complexity of this code is O(k). This is because the code maintains a record of the pairs within a vector that can have a maximum capacity of k and possess the smallest absolute difference.