Find the minimum difference between any two elements using Map
We can solve this problem using a map. We can first sort the array in ascending order and then find the minimum difference by comparing adjacent elements. Alternatively, we can insert all the elements into a map and then iterate through the map, comparing adjacent elements.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; int findMinDiff( int arr[], int n) { map< int , int > mp; int minDiff = INT_MAX; for ( int i = 0; i < n; i++) { auto it = mp.lower_bound(arr[i]); // Find the first element that is greater than or equal to arr[i] if (it != mp.end()) { minDiff = min(minDiff, it->first - arr[i]); // Check difference between current element and the next element in map } if (it != mp.begin()) { it--; minDiff = min(minDiff, arr[i] - it->first); // Check difference between current element and the previous element in map } mp[arr[i]] = i; // Insert element into map } return minDiff; } int main() { int arr[] = {1, 5, 3, 19, 18, 25}; int n = sizeof (arr) / sizeof (arr[0]); cout << findMinDiff(arr, n) << endl; return 0; } |
Java
import java.util.*; public class Main { public static int findMinDiff( int [] arr, int n) { TreeMap<Integer, Integer> mp = new TreeMap<>(); int minDiff = Integer.MAX_VALUE; for ( int i = 0 ; i < n; i++) { Map.Entry<Integer, Integer> entry = mp.ceilingEntry(arr[i]); // Find the first element that is greater than or equal to arr[i] if (entry != null ) { minDiff = Math.min(minDiff, entry.getKey() - arr[i]); // Check difference between current element and the next element in map } entry = mp.lowerEntry(arr[i]); if (entry != null ) { minDiff = Math.min(minDiff, arr[i] - entry.getKey()); // Check difference between current element and the previous element in map } mp.put(arr[i], i); // Insert element into map } return minDiff; } public static void main(String[] args) { int [] arr = { 1 , 5 , 3 , 19 , 18 , 25 }; int n = arr.length; System.out.println(findMinDiff(arr, n)); } } |
Python3
import bisect def findMinDiff(arr, n): mp = {} minDiff = float ( 'inf' ) for i in range (n): it = bisect.bisect_left( list (mp.keys()), arr[i]) # Find the first element that is greater than or equal to arr[i] if it ! = len (mp): minDiff = min (minDiff, list (mp.keys())[it] - arr[i]) # Check difference between current element and the next element in map if it ! = 0 : minDiff = min (minDiff, arr[i] - list (mp.keys())[it - 1 ]) # Check difference between current element and the previous element in map mp[arr[i]] = i # Insert element into map return minDiff arr = [ 1 , 5 , 3 , 19 , 18 , 25 ] n = len (arr) print (findMinDiff(arr, n)) |
C#
using System; using System.Collections.Generic; class Program { static int FindMinDiff( int [] arr) { Dictionary< int , int > dict = new Dictionary< int , int >(); int minDiff = int .MaxValue; for ( int i = 0; i < arr.Length; i++) { // Find the first element that is greater than or equal to arr[i] KeyValuePair< int , int >? greaterOrEqual = null ; foreach ( var kvp in dict) { if (kvp.Key >= arr[i]) { greaterOrEqual = kvp; break ; } } if (greaterOrEqual != null ) { // Check difference between the current element //and the next element in the dictionary minDiff = Math.Min(minDiff, greaterOrEqual.Value.Key - arr[i]); } // Find the previous element in the dictionary KeyValuePair< int , int >? previous = null ; foreach ( var kvp in dict) { if (kvp.Key < arr[i]) { previous = kvp; } else { break ; } } if (previous != null ) { // Check difference between the current // element and the previous element in the dictionary minDiff = Math.Min(minDiff, arr[i] - previous.Value.Key); } // Insert the current element into the dictionary dict[arr[i]] = i; } return minDiff; } static void Main() { int [] arr = { 1, 5, 3, 19, 18, 25 }; int minDiff = FindMinDiff(arr); Console.WriteLine(minDiff); } } |
Javascript
function findMinDiff(arr, n) { let mp = new Map(); // Create a Map to store elements of the array let minDiff = Infinity; // Initialize the minimum difference with Infinity for (let i = 0; i < n; i++) { let keys = Array.from(mp.keys()); // Get an array of keys from the Map let it = bisect_left(keys, arr[i]); // Find the first element that is greater than or equal to arr[i] if (it !== keys.length) { minDiff = Math.min(minDiff, keys[it] - arr[i]); // Check difference between current element and the next element in the map } if (it !== 0) { minDiff = Math.min(minDiff, arr[i] - keys[it - 1]); // Check difference between current element and the previous element in the map } mp.set(arr[i], i); // Insert element into the map } return minDiff; // Return the minimum difference } function bisect_left(arr, x) { let lo = 0; let hi = arr.length; while (lo < hi) { let mid = Math.floor((lo + hi) / 2); // Calculate the middle index if (arr[mid] < x) { lo = mid + 1; // If the middle element is less than x, search the right half } else { hi = mid; // If the middle element is greater than or equal to x, search the left half } } return lo; // Return the index where x should be inserted or found } let arr = [1, 5, 3, 19, 18, 25]; let n = arr.length; console.log(findMinDiff(arr, n)); |
1
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Find minimum difference between any two elements (pair) in given array
Given an unsorted array, find the minimum difference between any pair in the given array.
Examples :
Input: {1, 5, 3, 19, 18, 25}
Output: 1
Explanation: Minimum difference is between 18 and 19Input: {30, 5, 20, 9}
Output: 4
Explanation: Minimum difference is between 5 and 9Input: {1, 19, -4, 31, 38, 25, 100}
Output: 5
Explanation: Minimum difference is between 1 and -4
Naive Approach: To solve the problem follow the below idea:
A simple solution is to use two loops two generate every pair of elements and compare them to get the minimum difference
Below is the implementation of the above approach:
C++
// C++ implementation of simple method to find // minimum difference between any pair #include <bits/stdc++.h> using namespace std; // Returns minimum difference between any pair int findMinDiff( int arr[], int n) { // Initialize difference as infinite int diff = INT_MAX; // Find the min diff by comparing difference // of all possible pairs in given array for ( int i = 0; i < n - 1; i++) for ( int j = i + 1; j < n; j++) if ( abs (arr[i] - arr[j]) < diff) diff = abs (arr[i] - arr[j]); // Return min diff return diff; } // Driver code int main() { int arr[] = { 1, 5, 3, 19, 18, 25 }; int n = sizeof (arr) / sizeof (arr[0]); // Function call cout << "Minimum difference is " << findMinDiff(arr, n); return 0; } |
Java
// Java implementation of simple method to find // minimum difference between any pair class GFG { // Returns minimum difference between any pair static int findMinDiff( int [] arr, int n) { // Initialize difference as infinite int diff = Integer.MAX_VALUE; // Find the min diff by comparing difference // of all possible pairs in given array for ( int i = 0 ; i < n - 1 ; i++) for ( int j = i + 1 ; j < n; j++) if (Math.abs((arr[i] - arr[j])) < diff) diff = Math.abs((arr[i] - arr[j])); // Return min diff return diff; } // Driver code public static void main(String[] args) { int arr[] = new int [] { 1 , 5 , 3 , 19 , 18 , 25 }; // Function call System.out.println( "Minimum difference is " + findMinDiff(arr, arr.length)); } } |
Python3
# Python implementation of simple method to find # minimum difference between any pair # Returns minimum difference between any pair def findMinDiff(arr, n): # Initialize difference as infinite diff = 10 * * 20 # Find the min diff by comparing difference # of all possible pairs in given array for i in range (n - 1 ): for j in range (i + 1 , n): if abs (arr[i] - arr[j]) < diff: diff = abs (arr[i] - arr[j]) # Return min diff return diff # Driver code if __name__ = = "__main__" : arr = [ 1 , 5 , 3 , 19 , 18 , 25 ] n = len (arr) # Function call print ( "Minimum difference is " + str (findMinDiff(arr, n))) # This code is contributed by Pratik Chhajer |
C#
// C# implementation of simple method to find // minimum difference between any pair using System; class GFG { // Returns minimum difference between any pair static int findMinDiff( int [] arr, int n) { // Initialize difference as infinite int diff = int .MaxValue; // Find the min diff by comparing difference // of all possible pairs in given array for ( int i = 0; i < n - 1; i++) for ( int j = i + 1; j < n; j++) if (Math.Abs((arr[i] - arr[j])) < diff) diff = Math.Abs((arr[i] - arr[j])); // Return min diff return diff; } // Driver code public static void Main() { int [] arr = new int [] { 1, 5, 3, 19, 18, 25 }; // Function call Console.Write( "Minimum difference is " + findMinDiff(arr, arr.Length)); } } // This code is contributed by nitin mittal. |
Javascript
<script> // JavaScript program implementation of simple method to find // minimum difference between any pair // Returns minimum difference between any pair function findMinDiff( arr, n) { // Initialize difference as infinite let diff = Number.MAX_VALUE; // Find the min diff by comparing difference // of all possible pairs in given array for (let i=0; i<n-1; i++) for (let j=i+1; j<n; j++) if (Math.abs((arr[i] - arr[j]) )< diff) diff = Math.abs((arr[i] - arr[j])); // Return min diff return diff; } // Driver Code let arr = [1, 5, 3, 19, 18, 25]; document.write( "Minimum difference is " + findMinDiff(arr, arr.length)); </script> |
PHP
<?php // PHP implementation of simple // method to find minimum // difference between any pair // Returns minimum difference // between any pair function findMinDiff( $arr , $n ) { // Initialize difference // as infinite $diff = PHP_INT_MAX; // Find the min diff by comparing // difference of all possible // pairs in given array for ( $i = 0; $i < $n - 1; $i ++) for ( $j = $i + 1; $j < $n ; $j ++) if ( abs ( $arr [ $i ] - $arr [ $j ]) < $diff ) $diff = abs ( $arr [ $i ] - $arr [ $j ]); // Return min diff return $diff ; } // Driver code $arr = array (1, 5, 3, 19, 18, 25); $n = sizeof( $arr ); // Function call echo "Minimum difference is " , findMinDiff( $arr , $n ); // This code is contributed by ajit ?> |
Minimum difference is 1
Time Complexity: O(N2).
Auxiliary Space: O(1)