Problem

Given an unsorted array, find the minimum difference between any pair of elements in the array.

Examples

Example 1:

Input: [4, 9, 1, 32, 13]
Output: 3
Explanation: The minimum difference is between 4 and 1.

Example 2:

Input: [1, 5, 3, 19, 18, 25]
Output: 1
Explanation: The minimum difference is between 18 and 19.

Example 3:

Input: [30, 5, 20, 9]
Output: 4
Explanation: The minimum difference is between 5 and 9.

Solution

Method 1 - Naive

The brute force approach involves checking every possible pair of elements in the array and calculating the difference between each pair. Keep track of the minimum difference encountered.

Code

Java
public class Solution {
    public int findMinDifference(int[] nums) {
        int minDifference = Integer.MAX_VALUE;

        // Iterate through all pairs of elements
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int diff = Math.abs(nums[i] - nums[j]);
                if (diff < minDifference) {
                    minDifference = diff;
                }
            }
        }

        return minDifference;
    }
}
Python
def find_min_difference_brute_force(nums):
    min_difference = float("inf")

    # Iterate through all pairs of elements
    for i in range(len(nums) - 1):
        for j in range(i + 1, len(nums)):
            diff = abs(nums[i] - nums[j])
            if diff < min_difference:
                min_difference = diff

    return min_difference

Complexity

  • ⏰ Time complexity: O(n ^ 2)
  • 🧺 Space complexity: 1)`

Method 2 - Sorting

To find the minimum difference between any pair in an unsorted array, a straightforward approach is to leverage sorting:

  1. Sort the Array: Sorting the array allows us to compare adjacent elements, which are naturally the closest in value.
  2. Find Minimum Difference: Iterate through the sorted array and compute the difference between each pair of adjacent elements. Track the smallest difference encountered.

Code

Java
public class Solution {
    public int findMinDifference(int[] nums) {
        // Sort the array
        Arrays.sort(nums);

        // Initialize minimum difference to a large value
        int minDifference = Integer.MAX_VALUE;

        // Iterate through sorted array and find the minimum difference
        for (int i = 1; i < nums.length; i++) {
            int diff = nums[i] - nums[i - 1];
            if (diff < minDifference) {
                minDifference = diff;
            }
        }

        return minDifference;
    }
}
Python
def find_min_difference(nums):
    # Sort the array
    nums.sort()

    # Initialize minimum difference to a large value
    min_difference = float("inf")

    # Iterate through sorted array and find the minimum difference
    for i in range(1, len(nums)):
        diff = nums[i] - nums[i - 1]
        if diff < min_difference:
            min_difference = diff

    return min_difference

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(1)