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)
Find the minimum difference between any two elements using sorting:
The idea is to use sorting and compare every adjacent pair of the array
Follow the given steps to solve the problem:
- Sort array in ascending order
- Initialize difference as infinite
- Compare all adjacent pairs in a sorted array and keep track of the minimum difference
Below is the implementation of the above approach:
C++
// C++ program to find minimum difference between // any pair in an unsorted array #include <bits/stdc++.h> using namespace std; // Returns minimum difference between any pair int findMinDiff( int arr[], int n) { // Sort array in non-decreasing order sort(arr, arr + n); // Initialize difference as infinite int diff = INT_MAX; // Find the min diff by comparing adjacent // pairs in sorted array for ( int i = 0; i < n - 1; i++) if (arr[i + 1] - arr[i] < diff) diff = arr[i + 1] - arr[i]; // 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 program to find minimum difference between // any pair in an unsorted array import java.util.Arrays; class GFG { // Returns minimum difference between any pair static int findMinDiff( int [] arr, int n) { // Sort array in non-decreasing order Arrays.sort(arr); // Initialize difference as infinite int diff = Integer.MAX_VALUE; // Find the min diff by comparing adjacent // pairs in sorted array for ( int i = 0 ; i < n - 1 ; i++) if (arr[i + 1 ] - arr[i] < diff) diff = arr[i + 1 ] - arr[i]; // 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
# Python3 program to find minimum difference between # any pair in an unsorted array # Returns minimum difference between any pair def findMinDiff(arr, n): # Sort array in non-decreasing order arr = sorted (arr) # Initialize difference as infinite diff = 10 * * 20 # Find the min diff by comparing adjacent # pairs in sorted array for i in range (n - 1 ): if arr[i + 1 ] - arr[i] < diff: diff = arr[i + 1 ] - arr[i] # 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# program to find minimum // difference between any pair // in an unsorted array using System; class GFG { // Returns minimum difference // between any pair static int findMinDiff( int [] arr, int n) { // Sort array in // non-decreasing order Array.Sort(arr); // Initialize difference // as infinite int diff = int .MaxValue; // Find the min diff by // comparing adjacent pairs // in sorted array for ( int i = 0; i < n - 1; i++) if (arr[i + 1] - arr[i] < diff) diff = arr[i + 1] - arr[i]; // Return min diff return diff; } // Driver Code public static void Main() { int [] arr = new int [] { 1, 5, 3, 19, 18, 25 }; // Function call Console.WriteLine( "Minimum difference is " + findMinDiff(arr, arr.Length)); } } // This code is contributed by anuj_67. |
Javascript
<script> // Javascript program to find minimum // difference between any pair // in an unsorted array // Returns minimum difference // between any pair function findMinDiff(arr, n) { // Sort array in // non-decreasing order arr.sort( function (a, b) { return a - b}); // Initialize difference // as infinite let diff = Number.MAX_VALUE; // Find the min diff by // comparing adjacent pairs // in sorted array for (let i = 0; i < n - 1; i++) if (arr[i + 1] - arr[i] < diff) diff = arr[i + 1] - arr[i]; // Return min diff return diff; } let arr = [1, 5, 3, 19, 18, 25]; document.write( "Minimum difference is " + findMinDiff(arr, arr.length)); </script> |
PHP
<?php // PHP program to find minimum // difference between any pair // in an unsorted array // Returns minimum difference // between any pair function findMinDiff( $arr , $n ) { // Sort array in // non-decreasing order sort( $arr ); // Initialize difference // as infinite $diff = PHP_INT_MAX; // Find the min diff by // comparing adjacent // pairs in sorted array for ( $i = 0; $i < $n - 1; $i ++) if ( $arr [ $i + 1] - $arr [ $i ] < $diff ) $diff = $arr [ $i + 1] - $arr [ $i ]; // 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 ajit ?> |
Minimum difference is 1
Time Complexity: O(N log N)
Auxiliary Space: O(1)
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 the minimum difference between any two elements using Merge Sort:
The merge Helper function always compares two elements between each other. We can do this in O(nlogn) time instead of sorting and then again traversing the sorted array.
- Take a variable minDiff and store the minimum difference and compare with each recursive stack of the merge helper function.
C++
// C++ code #include <bits/stdc++.h> using namespace std; class Solution { public : // Function to find minimum difference between any pair // of elements in an array. int MinimumDifference( int arr[], int n) { if (n < 2) return INT_MAX; int mid = n / 2; int left[mid]; int right[n - mid]; for ( int i = 0; i < mid; i++) { left[i] = arr[i]; } for ( int i = mid; i < n; i++) { right[i - mid] = arr[i]; } int ls = MinimumDifference(left, mid); int rs = MinimumDifference(right, n - mid); int mg = mergeHelper(left, right, arr, mid, n - mid); return min(mg, min(ls, rs)); } private : int mergeHelper( int left[], int right[], int arr[], int n1, int n2) { int i = 0; int j = 0; int k = 0; int minDiff = INT_MAX; while (i < n1 && j < n2) { if (left[i] <= right[j]) { minDiff = min(minDiff, right[j] - left[i]); arr[k] = left[i]; i++; } else { minDiff = min(minDiff, left[i] - right[j]); arr[k] = right[j]; j++; } k++; } while (i < n1) { arr[k] = left[i]; i++; k++; } while (j < n2) { arr[k] = right[j]; j++; k++; } return minDiff; } }; int main() { // Code int arr[] = { 1, 5, 3, 19, 18, 25 }; int n = sizeof (arr) / sizeof (arr[0]); // Function call Solution sln; int minDiff = sln.MinimumDifference(arr, n); cout << "Minimum difference is " << minDiff << endl; return 0; } // This code is contributed by Aman Kumar |
Java
// Java Code import java.io.*; public class GFG { public static void main(String[] args) { // Code int [] arr = new int [] { 1 , 5 , 3 , 19 , 18 , 25 }; // Function call var sln = new Solution(); var minDiff = sln.MinimumDifference(arr, arr.length); System.out.println( "Minimum difference is " + minDiff); } } class Solution { // Function to find minimum difference between any pair // of elements in an array. public int MinimumDifference( int [] arr, int n) { // code here if (arr.length < 2 ) return Integer.MAX_VALUE; int mid = arr.length / 2 ; int [] left = new int [mid]; int [] right = new int [arr.length - mid]; int i = 0 ; while (i < mid) { left[i] = arr[i]; i += 1 ; } while (i < arr.length) { right[i - mid] = arr[i]; i += 1 ; } var ls = MinimumDifference(left, left.length); var rs = MinimumDifference(right, right.length); var mg = mergeHelper(left, right, arr); return Math.min(mg, Math.min(ls, rs)); } private int mergeHelper( int [] left, int [] right, int [] arr) { int i = 0 ; int j = 0 ; int k = 0 ; int minDiff = Integer.MAX_VALUE; while (i < left.length && j < right.length) { if (left[i] <= right[j]) { minDiff = Math.min(minDiff, right[j] - left[i]); arr[k] = left[i]; i += 1 ; } else { minDiff = Math.min(minDiff, left[i] - right[j]); arr[k] = right[j]; j += 1 ; } k += 1 ; } while (i < left.length) { arr[k] = left[i]; i += 1 ; k += 1 ; } while (j < right.length) { arr[k] = right[j]; j += 1 ; k += 1 ; } return minDiff; } } // This code is contributed by Pushpesh Raj. |
Python3
# Python Code class Solution: # Function to find minimum difference between any pair # of elements in an array. def MinimumDifference( self , arr, n): if n < 2 : return float ( 'inf' ) mid = n / / 2 left = arr[:mid] right = arr[mid:] ls = self .MinimumDifference(left, len (left)) rs = self .MinimumDifference(right, len (right)) mg = self .mergeHelper(left, right, arr, len (left), len (right)) return min (mg, min (ls, rs)) def mergeHelper( self , left, right, arr, n1, n2): i, j, k = 0 , 0 , 0 minDiff = float ( 'inf' ) while i < n1 and j < n2: if left[i] < = right[j]: minDiff = min (minDiff, right[j] - left[i]) arr[k] = left[i] i + = 1 else : minDiff = min (minDiff, left[i] - right[j]) arr[k] = right[j] j + = 1 k + = 1 while i < n1: arr[k] = left[i] i + = 1 k + = 1 while j < n2: arr[k] = right[j] j + = 1 k + = 1 return minDiff # Driver Code arr = [ 1 , 5 , 3 , 19 , 18 , 25 ] n = len (arr) sln = Solution() # Function call minDiff = sln.MinimumDifference(arr, n) print ( "Minimum difference is" , minDiff) # This code is contributed by Prasad Kandekar(prasad264) |
C#
using System; public class GFG { static public void Main() { // Code int [] arr = new int [] { 1, 5, 3, 19, 18, 25 }; // Function call var sln = new Solution(); var minDiff = sln.MinimumDifference(arr, arr.Length); Console.WriteLine( "Minimum difference is " + minDiff); } } class Solution { // Function to find minimum difference between any pair // of elements in an array. public int MinimumDifference( int [] arr, int n) { // code here if (arr.Length < 2) return int .MaxValue; int mid = arr.Length / 2; int [] left = new int [mid]; int [] right = new int [arr.Length - mid]; int i = 0; while (i < mid) { left[i] = arr[i]; i += 1; } while (i < arr.Length) { right[i - mid] = arr[i]; i += 1; } var ls = MinimumDifference(left, left.Length); var rs = MinimumDifference(right, right.Length); var mg = mergeHelper(left, right, arr); return Math.Min(mg, Math.Min(ls, rs)); } private int mergeHelper( int [] left, int [] right, int [] arr) { int i = 0; int j = 0; int k = 0; int minDiff = int .MaxValue; while (i < left.Length && j < right.Length) { if (left[i] <= right[j]) { minDiff = Math.Min(minDiff, right[j] - left[i]); arr[k] = left[i]; i += 1; } else { minDiff = Math.Min(minDiff, left[i] - right[j]); arr[k] = right[j]; j += 1; } k += 1; } while (i < left.Length) { arr[k] = left[i]; i += 1; k += 1; } while (j < right.Length) { arr[k] = right[j]; j += 1; k += 1; } return minDiff; } } |
Javascript
// JavaScript code class Solution { // Function to find minimum difference between any pair // of elements in an array. MinimumDifference(arr, n) { if (n < 2) return Number.MAX_SAFE_INTEGER; var mid = Math.floor(n / 2); var left = arr.slice(0, mid); var right = arr.slice(mid); var ls = this .MinimumDifference(left, mid); var rs = this .MinimumDifference(right, n - mid); var mg = this .mergeHelper(left, right, arr, mid, n - mid); return Math.min(mg, Math.min(ls, rs)); } // Helper function for merge sort mergeHelper(left, right, arr, n1, n2) { var i = 0; var j = 0; var k = 0; var minDiff = Number.MAX_SAFE_INTEGER; while (i < n1 && j < n2) { if (left[i] <= right[j]) { minDiff = Math.min(minDiff, right[j] - left[i]); arr[k] = left[i]; i++; } else { minDiff = Math.min(minDiff, left[i] - right[j]); arr[k] = right[j]; j++; } k++; } while (i < n1) { arr[k] = left[i]; i++; k++; } while (j < n2) { arr[k] = right[j]; j++; k++; } return minDiff; } } // Code var arr = [1, 5, 3, 19, 18, 25]; var n = arr.length; // Function call var sln = new Solution(); var minDiff = sln.MinimumDifference(arr, n); console.log( "Minimum difference is " + minDiff); // This code is contributed by Prasad Kandekar(prasad264) |
Minimum difference is 1
Time Complexity: O(N * log N) Merge sort algorithm uses (n * log n) complexity.
Auxiliary Space: O(N) In merge sort algorithm all elements are copied into an auxiliary array.
Contact Us