Find the minimum difference between any two elements using Map

Find the minimum difference between any two elements using sorting:

Find the minimum difference between any two elements using Merge Sort:

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));

Output

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 19

Input: {30, 5, 20, 9}
Output: 4
Explanation: Minimum difference is between 5 and 9

Input: {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
?>

Output

Minimum difference is 1

Time Complexity: O(N²).
Auxiliary Space: O(1)

Tags:

#Amazon #Arrays #Arrays #DSA #Sorting #Amazon #Arrays #Arrays #Sorting

Find the minimum difference between any two elements using sorting:

Find the minimum difference between any two elements using Merge Sort:

Find the minimum difference between any two elements using Map

C++

Java

Python3

C#

Javascript

Find minimum difference between any two elements (pair) in given array

C++

Java

Python3

C#

Javascript

PHP

Similar Reads

Contact Us