Closest numbers from a list of unsorted integers
Given a list of distinct unsorted integers, find the pair of elements that have the smallest absolute difference between them? If there are multiple pairs, find them all.
Examples:
Input : arr[] = {10, 50, 12, 100}
Output : (10, 12)
The closest elements are 10 and 12
Input : arr[] = {5, 4, 3, 2}
Output : (2, 3), (3, 4), (4, 5)
This problem is mainly an extension of Find minimum difference between any two elements.
- Sort the given array.
- Find minimum difference of all pairs in linear time in sorted array.
- Traverse sorted array one more time to print all pairs with minimum difference obtained in step 2.
Implementation:
C++
// CPP program to find minimum difference // an unsorted array. #include<bits/stdc++.h> using namespace std; // Returns minimum difference between any // two pair in arr[0..n-1] void printMinDiffPairs( int arr[], int n) { if (n <= 1) return ; // Sort array elements sort(arr, arr+n); // Compare differences of adjacent // pairs to find the minimum difference. int minDiff = arr[1] - arr[0]; for ( int i = 2 ; i < n ; i++) minDiff = min(minDiff, arr[i] - arr[i-1]); // Traverse array again and print all pairs // with difference as minDiff. for ( int i = 1; i < n; i++) if ((arr[i] - arr[i-1]) == minDiff) cout << "(" << arr[i-1] << ", " << arr[i] << "), " ; } // Driver code int main() { int arr[] = {5, 3, 2, 4, 1}; int n = sizeof (arr) / sizeof (arr[0]); printMinDiffPairs(arr, n); return 0; } |
Java
// Java program to find minimum // difference an unsorted array. import java.util.*; class GFG { // Returns minimum difference between // any two pair in arr[0..n-1] static void printMinDiffPairs( int arr[], int n) { if (n <= 1 ) return ; // Sort array elements Arrays.sort(arr); // Compare differences of adjacent // pairs to find the minimum difference. int minDiff = arr[ 1 ] - arr[ 0 ]; for ( int i = 2 ; i < n; i++) minDiff = Math.min(minDiff, arr[i] - arr[i- 1 ]); // Traverse array again and print all pairs // with difference as minDiff. for ( int i = 1 ; i < n; i++) { if ((arr[i] - arr[i- 1 ]) == minDiff) { System.out.print( "(" + arr[i- 1 ] + ", " + arr[i] + ")," ); } } } // Driver code public static void main (String[] args) { int arr[] = { 5 , 3 , 2 , 4 , 1 }; int n = arr.length; printMinDiffPairs(arr, n); } } // This code is contributed by Ansu Kumari |
Python3
# Python3 program to find minimum # difference in an unsorted array. # Returns minimum difference between # any two pair in arr[0..n-1] def printMinDiffPairs(arr , n): if n < = 1 : return # Sort array elements arr.sort() # Compare differences of adjacent # pairs to find the minimum difference. minDiff = arr[ 1 ] - arr[ 0 ] for i in range ( 2 , n): minDiff = min (minDiff, arr[i] - arr[i - 1 ]) # Traverse array again and print all # pairs with difference as minDiff. for i in range ( 1 , n): if (arr[i] - arr[i - 1 ]) = = minDiff: print ( "(" + str (arr[i - 1 ]) + ", " + str (arr[i]) + "), " , end = '') # Driver code arr = [ 5 , 3 , 2 , 4 , 1 ] n = len (arr) printMinDiffPairs(arr , n) # This code is contributed by Ansu Kumari |
C#
// C# program to find minimum // difference an unsorted array. using System; class GFG { // Returns minimum difference between // any two pair in arr[0..n-1] static void printMinDiffPairs( int []arr, int n) { if (n <= 1) return ; // Sort array elements Array.Sort(arr); // Compare differences of adjacent // pairs to find the minimum difference. int minDiff = arr[1] - arr[0]; for ( int i = 2; i < n; i++) minDiff = Math.Min(minDiff, arr[i] - arr[i-1]); // Traverse array again and print all pairs // with difference as minDiff. for ( int i = 1; i < n; i++) { if ((arr[i] - arr[i-1]) == minDiff) { Console.Write( " (" + arr[i-1] + ", " + arr[i] + "), " ); } } } // Driver code public static void Main () { int []arr = {5, 3, 2, 4, 1}; int n = arr.Length; printMinDiffPairs(arr, n); } } // This code is contributed by vt_m |
Javascript
<script> // JavaScript program to find minimum // difference an unsorted array. // Returns minimum difference between // any two pair in arr[0..n-1] function printMinDiffPairs(arr, n) { if (n <= 1) return ; // Sort array elements arr.sort(); // Compare differences of adjacent // pairs to find the minimum difference. let minDiff = arr[1] - arr[0]; for (let i = 2; i < n; i++) minDiff = Math.min(minDiff, arr[i] - arr[i-1]); // Traverse array again and print all pairs // with difference as minDiff. for ( let i = 1; i < n; i++) { if ((arr[i] - arr[i-1]) == minDiff) { document.write( "(" + arr[i-1] + ", " + arr[i] + ") , " ); } } } // Driver code let arr = [5, 3, 2, 4, 1]; let n = arr.length; printMinDiffPairs(arr , n); </script> |
PHP
<?php //PHP program to find minimum difference // an unsorted array. // Returns minimum difference between any // two pair in arr[0..n-1] function printMinDiffPairs( $arr , $n ) { if ( $n <= 1) return ; // Sort array elements sort( $arr ); // Compare differences of adjacent // pairs to find the minimum // difference. $minDiff = $arr [1] - $arr [0]; for ( $i = 2 ; $i < $n ; $i ++) $minDiff = min( $minDiff , $arr [ $i ] - $arr [ $i -1]); // Traverse array again and print all // pairs with difference as minDiff. for ( $i = 1; $i < $n ; $i ++) if (( $arr [ $i ] - $arr [ $i -1]) == $minDiff ) echo "(" , $arr [ $i -1] , ", " , $arr [ $i ] , "), " ; } // Driver code $arr = array (5, 3, 2, 4, 1); $n = sizeof( $arr ); printMinDiffPairs( $arr , $n ); // This code is contributed by ajit. ?> |
Output:
(1, 2), (2, 3), (3, 4), (4, 5),
Time Complexity: O(n log n)
Auxiliary Space: O(1)
Does above program handle duplicates?
The cases like {x, x, x} are not handled by above program. For this case, the expected output (x, x), (x, x), (x, x), but above program prints (x, x), (x, x).
See the below method where the duplicates problem is handled nicely and efficiently.
Another Approach: Using Map
Another method to solve this problem is to use map, which can help in sorting and finding minimum difference at same time. It also solves the duplicate elements handling problem.
Example:
Input : arr[] = { 5, 5, 3, 2, 2, 4, 1, 1 }
Output : (2, 3), (3, 4), (4, 5)
Steps:
- Insert all the elements of the array into the map.
- Now iterate through the map and check the difference at a same time to find minimum difference.
- In next iteration, print those elements whose difference are minimum.
Below is the implementation of the above approach:
C++
// CPP program to find minimum difference // an unsorted array using map #include <bits/stdc++.h> using namespace std; // Returns minimum difference between any // two pair in arr[0..n-1] void printMinDiffPairs( int arr[], int n) { if (n <= 1) return ; // Creating map map< int , int > mp; // Sort array elements during insertion for ( int i = 0; i < n; i++) mp[arr[i]]++; // Compare differences of adjacent // pairs to find the minimum difference. int minDiff = INT_MAX; for ( auto it = mp.begin(); it != mp.end(); it++) { auto temp = it->first; it++; // If map doesn't contain ends if (it == mp.end()) break ; minDiff = min(minDiff, ((it->first) - temp)); it--; } // Traverse array again and print all pairs // with difference as minDiff. for ( auto it = mp.begin(); it != mp.end(); it++) { auto temp = it->first; it++; // If map doesn't contain ends if (it == mp.end()) break ; if (((it->first) - temp) == minDiff) cout << "(" << temp << ", " << it->first << "), " ; it--; } } // Driver code int main() { int arr[] = { 5, 5, 3, 2, 2, 4, 1, 1 }; int n = sizeof (arr) / sizeof (arr[0]); printMinDiffPairs(arr, n); return 0; } // This code is contributed by Susobhan Akhuli |
Java
// Java program to find minimum difference // an unsorted array using map import java.util.*; public class Main { // Returns minimum difference between any // two pair in arr[0..n-1] public static void printMinDiffPairs( int [] arr, int n) { if (n <= 1 ) { return ; } // Creating map Map<Integer, Integer> mp = new HashMap<>(); for ( int i = 0 ; i < n; i++) { if (mp.containsKey(arr[i])) { mp.put(arr[i], mp.get(arr[i]) + 1 ); } else { mp.put(arr[i], 1 ); } } // Compare differences of adjacent // pairs to find the minimum difference. int minDiff = Integer.MAX_VALUE; Iterator<Map.Entry<Integer, Integer>> it = mp.entrySet().iterator(); Map.Entry<Integer, Integer> prev = it.next(); // If map doesn't contain ends while (it.hasNext()) { Map.Entry<Integer, Integer> curr = it.next(); int diff = curr.getKey() - prev.getKey(); if (diff < minDiff) { minDiff = diff; } prev = curr; } it = mp.entrySet().iterator(); prev = it.next(); while (it.hasNext()) { Map.Entry<Integer, Integer> curr = it.next(); int diff = curr.getKey() - prev.getKey(); if (diff == minDiff) { System.out.print( "(" + prev.getKey() + ", " + curr.getKey() + "), " ); } prev = curr; } } // Driver code public static void main(String[] args) { int [] arr = { 5 , 5 , 3 , 2 , 2 , 4 , 1 , 1 }; int n = arr.length; printMinDiffPairs(arr, n); } } // This code is contributed by shiv14o3g |
Python3
# Python code to find minimum difference # an unsorted array using dictionary # Returns minimum difference between any # two pair in arr[0..n-1] def printMinDiffPairs(arr, n): if n < = 1 : return # Creating dictionary mp = {} # Sort array elements during insertion for i in range (n): mp[arr[i]] = mp.get(arr[i], 0 ) + 1 # Compare differences of adjacent # pairs to find the minimum difference. minDiff = float ( 'inf' ) temp = float ( 'inf' ) for key in mp: minDiff = min (minDiff, abs (key - temp)) temp = key # Traverse array again and print all pairs # with difference as minDiff. for key in sorted (mp.keys()): if key + minDiff in mp: print (f "({key}, {key+minDiff})" , end = ', ' ) # Driver code if __name__ = = '__main__' : arr = [ 5 , 5 , 3 , 2 , 2 , 4 , 1 , 1 ] n = len (arr) printMinDiffPairs(arr, n) # This code is contributed by Susobhan Akhuli |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { // Function to find and print pairs with minimum difference static void PrintMinDiffPairs( int [] arr) { if (arr.Length <= 1) { return ; } // Creating a dictionary to store frequency of elements Dictionary< int , int > frequencyMap = new Dictionary< int , int >(); // Sort the array elements during insertion foreach ( int element in arr) { if (frequencyMap.ContainsKey(element)) { frequencyMap[element]++; } else { frequencyMap[element] = 1; } } // Compare differences of adjacent pairs to find the minimum difference int minDiff = int .MaxValue; int temp = int .MaxValue; foreach ( int key in frequencyMap.Keys) { minDiff = Math.Min(minDiff, Math.Abs(key - temp)); temp = key; } // Traverse the array again and print all pairs with a difference as minDiff var sortedKeys = frequencyMap.Keys.OrderBy(k => k); foreach ( int key in sortedKeys) { int potentialPair = key + minDiff; if (frequencyMap.ContainsKey(potentialPair)) { Console.WriteLine($ "({key}, {potentialPair})," ); } } } static void Main() { int [] arr = { 5, 5, 3, 2, 2, 4, 1, 1 }; PrintMinDiffPairs(arr); } } |
Javascript
// Function to print minimum difference pairs function printMinDiffPairs(arr) { if (arr.length <= 1) return ; // Creating a dictionary let mp = new Map(); // Sort array elements during insertion for (let i = 0; i < arr.length; i++) { mp.set(arr[i], (mp.get(arr[i]) || 0) + 1); } // Compare differences of adjacent pairs to find the minimum difference let minDiff = Infinity; let temp = Infinity; for (const key of mp.keys()) { minDiff = Math.min(minDiff, Math.abs(key - temp)); temp = key; } // Traverse array again and print all pairs with a difference as minDiff for (const key of [...mp.keys()].sort((a, b) => a - b)) { if (mp.has(key + minDiff)) { console.log(`(${key}, ${key + minDiff}),`); } } } // Driver code let arr = [5, 5, 3, 2, 2, 4, 1, 1]; printMinDiffPairs(arr); |
(1, 2), (2, 3), (3, 4), (4, 5),
Time Complexity: O(n*log n), where n is the number of elements in array.
Auxiliary Space: O(n), to store elements in Map.
Contact Us