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 pairint 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 codeint 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 pairclass 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 pairdef 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 codeif __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 pairusing 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 pairfunction findMinDiff($arr, $n){// Initialize difference// as infinite$diff = PHP_INT_MAX;// Find the min diff by comparing// difference of all possible // pairs in given arrayfor ($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 diffreturn $diff;}// Driver code$arr = array(1, 5, 3, 19, 18, 25);$n = sizeof($arr);// Function callecho "Minimum difference is " , findMinDiff($arr, $n);// This code is contributed by ajit?> |
Output
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 pairint 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 codeint 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 arrayimport 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 pairdef 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 codeif __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 arrayusing 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 pairfunction findMinDiff($arr, $n){ // Sort array in // non-decreasing ordersort($arr);// Initialize difference// as infinite$diff = PHP_INT_MAX;// Find the min diff by // comparing adjacent // pairs in sorted arrayfor ($i = 0; $i < $n - 1; $i++) if ($arr[$i + 1] - $arr[$i] < $diff) $diff = $arr[$i + 1] - $arr[$i];// Return min diffreturn $diff;}// Driver code$arr = array(1, 5, 3, 19, 18, 25);$n = sizeof($arr);// Function callecho "Minimum difference is " , findMinDiff($arr, $n);// This code is contributed ajit?> |
Output
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 bisectdef 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 minDiffarr = [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)); |
Output
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 Codeimport 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 Codeclass 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 Codearr = [1, 5, 3, 19, 18, 25]n = len(arr)sln = Solution()# Function callminDiff = 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 codeclass 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; }}// Codevar arr = [1, 5, 3, 19, 18, 25];var n = arr.length;// Function callvar sln = new Solution();var minDiff = sln.MinimumDifference(arr, n);console.log("Minimum difference is " + minDiff);// This code is contributed by Prasad Kandekar(prasad264) |
Output
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.
Asked in: Amazon
This article is contributed by Harshit Agrawal. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
