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

0 0 16 minutes read

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)

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
?>

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

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 zambiatek!