Introduction

Finding the minimum difference between elements in an array is a common task in interviews and real systems such as ranking, scheduling, and threshold analysis. The straightforward brute-force solution is easy to write but slow for large inputs. The standard efficient approach is sorting followed by adjacent comparison.

Problem Definition

Given an integer array, find the smallest absolute difference between any two distinct elements.

Example:

• input: [4, 9, 1, 32, 13]
• answer: 3, from pairs (1, 4) or (9, 13)

For arrays with fewer than two elements, no valid pair exists. Your function should raise an error or return a sentinel value according to API design.

Brute-Force Baseline

Check every pair and track the best difference.

1def min_diff_bruteforce(arr):
2    if len(arr) < 2:
3        raise ValueError("Need at least two elements")
4
5    best = float("inf")
6    for i in range(len(arr)):
7        for j in range(i + 1, len(arr)):
8            best = min(best, abs(arr[i] - arr[j]))
9
10    return best
11
12print(min_diff_bruteforce([4, 9, 1, 32, 13]))

Complexity is O(n^2), which becomes expensive as n grows.

Sorting-Based Efficient Solution

After sorting, the smallest absolute difference must occur between adjacent values in sorted order.

1def min_diff_sorted(arr):
2    if len(arr) < 2:
3        raise ValueError("Need at least two elements")
4
5    s = sorted(arr)
6    best = float("inf")
7
8    for i in range(1, len(s)):
9        diff = s[i] - s[i - 1]
10        if diff < best:
11            best = diff
12
13    return best
14
15print(min_diff_sorted([4, 9, 1, 32, 13]))

Complexity is O(n log n) due to sorting, with linear scan after.

Why Adjacent Comparison Works

Assume sorted values a <= b <= c. If you compare non-adjacent a and c, then c - a is at least as large as either b - a or c - b. So a non-adjacent pair cannot produce a strictly smaller difference than all adjacent pairs.

That proof is why adjacent scan is both correct and efficient.

Return the Pair Along with the Difference

Many applications need not only the value but also which pair produced it.

1def min_diff_with_pair(arr):
2    if len(arr) < 2:
3        raise ValueError("Need at least two elements")
4
5    s = sorted(arr)
6    best = s[1] - s[0]
7    pair = (s[0], s[1])
8
9    for i in range(2, len(s)):
10        diff = s[i] - s[i - 1]
11        if diff < best:
12            best = diff
13            pair = (s[i - 1], s[i])
14
15    return best, pair
16
17print(min_diff_with_pair([4, 9, 1, 32, 13]))

Returning the pair improves explainability and debugging.

Handle Duplicates and Negative Numbers

The sorting approach naturally supports duplicates and negatives.

print(min_diff_sorted([5, 5, 10]))        # 0
print(min_diff_sorted([-10, -3, 2, 9]))   # 5

Duplicate values yield minimum possible difference 0.

In-Place Versus Copy Sorting

sorted(arr) returns a copy, while arr.sort() mutates input. Choose based on caller expectations.

In-place variant:

1def min_diff_inplace(arr):
2    if len(arr) < 2:
3        raise ValueError("Need at least two elements")
4
5    arr.sort()
6    return min(arr[i] - arr[i - 1] for i in range(1, len(arr)))

Document mutation behavior clearly to avoid surprises.

C++ Version

The same logic applies in C++.

1#include <algorithm>
2#include <iostream>
3#include <stdexcept>
4#include <vector>
5
6int minDiff(std::vector<int> a) {
7    if (a.size() < 2) {
8        throw std::invalid_argument("need at least two elements");
9    }
10
11    std::sort(a.begin(), a.end());
12    int best = a[1] - a[0];
13
14    for (size_t i = 2; i < a.size(); ++i) {
15        best = std::min(best, a[i] - a[i - 1]);
16    }
17
18    return best;
19}

This keeps the same O(n log n) complexity profile.

Common Pitfalls

A common pitfall is forgetting to sort before adjacent comparison, which invalidates the logic.

Another issue is using absolute difference after sorting when simple subtraction already yields non-negative values and is slightly cleaner.

Some implementations forget edge cases with fewer than two elements and crash on index access.

In-place sorting without documentation is another frequent bug source when callers expect original order preserved.

Finally, brute-force solutions are sometimes used in production for convenience and later become bottlenecks at scale.

Summary

• Brute force is simple but slow at O(n^2).
• Sorting plus adjacent scan solves the problem in O(n log n).
• Adjacent comparison works because non-adjacent gaps cannot be smaller.
• Duplicates and negatives are naturally handled.
• Decide and document whether your function mutates input.