Problem

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

Examples

Example 1:

1
2
3

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

Example 2:

1
2
3

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

Example 3:

1
2
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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)