Minimum Difference Between K Closest Elements

🎯

Minimum Difference Between K Closest Elements

mediumTWO_POINTERGoogleAmazonFacebook

Imagine you have a list of houses along a street and want to find a group of K houses that are closest together to minimize travel distance for a delivery route.

💡 This problem asks for a subset of K elements from an array such that the difference between the maximum and minimum in that subset is as small as possible. Beginners often struggle because it’s not obvious how to efficiently find such a subset without checking all combinations.

📋

Problem Statement

Given an array of integers and an integer K, find the minimum difference between the maximum and minimum values among any subset of K elements from the array. Return this minimum difference.

1 ≤ n ≤ 10^5 (length of array)1 ≤ K ≤ n-10^9 ≤ array elements ≤ 10^9

💡

Example

Input"arr = [10, 12, 10, 7, 5, 22], K = 3"

Output2

The subset [10, 10, 12] has max-min = 12-10 = 2, which is the smallest possible difference for any 3 elements.

• K = 1 → output should be 0 since single element difference is zero
• All elements equal → output should be 0
• Array sorted ascending → minimal difference is between consecutive elements
• Array with negative and positive numbers → difference calculation must handle negatives

⚠️

Common Mistakes

Not sorting the array before sliding window

Incorrect minimum difference because elements are not contiguous

✅ Always sort the array first

Using max-min difference on unsorted windows

Wrong difference values leading to wrong answer

✅ Use sorted array so window max and min are first and last elements

Off-by-one errors in window boundaries

Index out of range errors or missing windows

✅ Ensure loop runs from 0 to n-k inclusive

Not handling K=1 edge case

Incorrect output or unnecessary computation

✅ Return 0 immediately if K=1 since difference is zero

🧠

Brute Force (Nested Loops Checking All Subsets)

💡 This approach exists to build intuition by trying all possible subsets of size K and checking their max-min difference. It’s slow but conceptually simple.

Intuition

Try every possible combination of K elements, find the difference between max and min in that subset, and track the minimum difference found.

Algorithm

1. Generate all subsets of size K from the array.
2. For each subset, find the maximum and minimum elements.
3. Calculate the difference (max - min) for that subset.
4. Keep track of the minimum difference found and return it.

💡 This algorithm is straightforward but inefficient because generating all subsets grows exponentially with input size.

</>

Code

from itertools import combinations

def min_diff_brute_force(arr, k):
    min_diff = float('inf')
    for subset in combinations(arr, k):
        current_diff = max(subset) - min(subset)
        if current_diff < min_diff:
            min_diff = current_diff
    return min_diff

# Driver code
if __name__ == '__main__':
    arr = [10, 12, 10, 7, 5, 22]
    k = 3
    print(min_diff_brute_force(arr, k))  # Output: 2

Line Notes

from itertools import combinationsImport combinations to generate all subsets of size k

for subset in combinations(arr, k):Iterate over every possible subset of size k

current_diff = max(subset) - min(subset)Calculate difference between max and min in current subset

if current_diff < min_diff:Update minimum difference if current is smaller

import java.util.*;

public class MinDiffBruteForce {
    public static int minDiffBruteForce(int[] arr, int k) {
        int n = arr.length;
        int minDiff = Integer.MAX_VALUE;
        List<List<Integer>> subsets = new ArrayList<>();
        generateCombinations(arr, k, 0, new ArrayList<>(), subsets);
        for (List<Integer> subset : subsets) {
            int maxVal = Collections.max(subset);
            int minVal = Collections.min(subset);
            int diff = maxVal - minVal;
            if (diff < minDiff) minDiff = diff;
        }
        return minDiff;
    }

    private static void generateCombinations(int[] arr, int k, int start, List<Integer> current, List<List<Integer>> subsets) {
        if (current.size() == k) {
            subsets.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i < arr.length; i++) {
            current.add(arr[i]);
            generateCombinations(arr, k, i + 1, current, subsets);
            current.remove(current.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] arr = {10, 12, 10, 7, 5, 22};
        int k = 3;
        System.out.println(minDiffBruteForce(arr, k)); // Output: 2
    }
}

Line Notes

generateCombinationsRecursively generate all subsets of size k

if (current.size() == k)Base case: subset of size k formed

int maxVal = Collections.max(subset);Find max in current subset

int minVal = Collections.min(subset);Find min in current subset

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void generateCombinations(vector<int>& arr, int k, int start, vector<int>& current, vector<vector<int>>& subsets) {
    if (current.size() == k) {
        subsets.push_back(current);
        return;
    }
    for (int i = start; i < arr.size(); i++) {
        current.push_back(arr[i]);
        generateCombinations(arr, k, i + 1, current, subsets);
        current.pop_back();
    }
}

int minDiffBruteForce(vector<int>& arr, int k) {
    vector<vector<int>> subsets;
    vector<int> current;
    generateCombinations(arr, k, 0, current, subsets);
    int minDiff = INT_MAX;
    for (auto& subset : subsets) {
        int maxVal = *max_element(subset.begin(), subset.end());
        int minVal = *min_element(subset.begin(), subset.end());
        int diff = maxVal - minVal;
        if (diff < minDiff) minDiff = diff;
    }
    return minDiff;
}

int main() {
    vector<int> arr = {10, 12, 10, 7, 5, 22};
    int k = 3;
    cout << minDiffBruteForce(arr, k) << endl; // Output: 2
    return 0;
}

Line Notes

generateCombinationsRecursive function to generate all subsets of size k

if (current.size() == k)Stop recursion when subset size k is reached

int maxVal = *max_element(subset.begin(), subset.end())Find max element in subset

int minVal = *min_element(subset.begin(), subset.end())Find min element in subset

function generateCombinations(arr, k, start, current, subsets) {
    if (current.length === k) {
        subsets.push([...current]);
        return;
    }
    for (let i = start; i < arr.length; i++) {
        current.push(arr[i]);
        generateCombinations(arr, k, i + 1, current, subsets);
        current.pop();
    }
}

function minDiffBruteForce(arr, k) {
    const subsets = [];
    generateCombinations(arr, k, 0, [], subsets);
    let minDiff = Infinity;
    for (const subset of subsets) {
        const maxVal = Math.max(...subset);
        const minVal = Math.min(...subset);
        const diff = maxVal - minVal;
        if (diff < minDiff) minDiff = diff;
    }
    return minDiff;
}

// Driver code
const arr = [10, 12, 10, 7, 5, 22];
const k = 3;
console.log(minDiffBruteForce(arr, k)); // Output: 2

Line Notes

generateCombinationsRecursive helper to generate all subsets of size k

if (current.length === k)Base case: subset of size k formed

const maxVal = Math.max(...subset)Find max element in current subset

const minVal = Math.min(...subset)Find min element in current subset

⏱

Complexity

TimeO(n choose k * k) which is exponential and impractical for large n

SpaceO(n choose k * k) due to storing all subsets

Generating all subsets of size k is combinatorial, and checking max-min for each subset adds extra work

💡 For n=20 and k=3, this means over 1140 subsets to check, which is borderline but grows quickly beyond that.

Interview Verdict: TLE / Use only to introduce problem

This approach is too slow for large inputs but helps understand the problem fully before optimizing.

🧠

Sorting + Sliding Window (Two Pointers)

💡 Sorting the array first lets us consider only consecutive windows of size K, because the minimal difference subset must be contiguous in sorted order.

Intuition

After sorting, the K closest elements minimizing max-min difference must be next to each other. So slide a window of size K and find the minimal range.

Algorithm

1. Sort the array in ascending order.
2. Initialize min_diff to a large number.
3. Slide a window of size K from start to end of array.
4. For each window, compute difference between last and first element.
5. Update min_diff if current difference is smaller.
6. Return min_diff after checking all windows.

💡 This approach leverages sorting to reduce the search space drastically and uses a simple linear scan.

</>

Code

def min_diff_sorting(arr, k):
    arr.sort()
    min_diff = float('inf')
    for i in range(len(arr) - k + 1):
        current_diff = arr[i + k - 1] - arr[i]
        if current_diff < min_diff:
            min_diff = current_diff
    return min_diff

# Driver code
if __name__ == '__main__':
    arr = [10, 12, 10, 7, 5, 22]
    k = 3
    print(min_diff_sorting(arr, k))  # Output: 2

Line Notes

arr.sort()Sort array to bring closest elements together

for i in range(len(arr) - k + 1)Slide window of size k over sorted array

current_diff = arr[i + k - 1] - arr[i]Calculate difference between window's max and min

if current_diff < min_diffUpdate minimum difference found so far

import java.util.*;

public class MinDiffSorting {
    public static int minDiffSorting(int[] arr, int k) {
        Arrays.sort(arr);
        int minDiff = Integer.MAX_VALUE;
        for (int i = 0; i <= arr.length - k; i++) {
            int diff = arr[i + k - 1] - arr[i];
            if (diff < minDiff) minDiff = diff;
        }
        return minDiff;
    }

    public static void main(String[] args) {
        int[] arr = {10, 12, 10, 7, 5, 22};
        int k = 3;
        System.out.println(minDiffSorting(arr, k)); // Output: 2
    }
}

Line Notes

Arrays.sort(arr)Sort array to group close elements

for (int i = 0; i <= arr.length - k; i++)Slide window of size k over array

int diff = arr[i + k - 1] - arr[i]Calculate difference in current window

if (diff < minDiff)Update minimum difference if smaller

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minDiffSorting(vector<int>& arr, int k) {
    sort(arr.begin(), arr.end());
    int minDiff = INT_MAX;
    for (int i = 0; i <= (int)arr.size() - k; i++) {
        int diff = arr[i + k - 1] - arr[i];
        if (diff < minDiff) minDiff = diff;
    }
    return minDiff;
}

int main() {
    vector<int> arr = {10, 12, 10, 7, 5, 22};
    int k = 3;
    cout << minDiffSorting(arr, k) << endl; // Output: 2
    return 0;
}

Line Notes

sort(arr.begin(), arr.end())Sort array to bring close elements together

for (int i = 0; i <= (int)arr.size() - k; i++)Slide window of size k over sorted array

int diff = arr[i + k - 1] - arr[i]Calculate difference between window's max and min

if (diff < minDiff)Update minimum difference if current is smaller

function minDiffSorting(arr, k) {
    arr.sort((a, b) => a - b);
    let minDiff = Infinity;
    for (let i = 0; i <= arr.length - k; i++) {
        let diff = arr[i + k - 1] - arr[i];
        if (diff < minDiff) minDiff = diff;
    }
    return minDiff;
}

// Driver code
const arr = [10, 12, 10, 7, 5, 22];
const k = 3;
console.log(minDiffSorting(arr, k)); // Output: 2

Line Notes

arr.sort((a, b) => a - b)Sort array numerically ascending

for (let i = 0; i <= arr.length - k; i++)Slide window of size k over sorted array

let diff = arr[i + k - 1] - arr[i]Calculate difference between max and min in window

if (diff < minDiff)Update minimum difference if smaller

⏱

Complexity

TimeO(n log n) due to sorting, plus O(n) for sliding window

SpaceO(1) or O(n) depending on sorting implementation

Sorting dominates time complexity; sliding window is linear scan

💡 For n=10^5, sorting takes about 10^5 log(10^5) ≈ 1.7 million operations, which is efficient.

Interview Verdict: Accepted / Efficient for large inputs

This approach is optimal for this problem and is what interviewers expect after brute force.

🧠

Optimized Sliding Window with Early Stopping

💡 This approach is a minor optimization over the previous by stopping early if difference zero is found, since zero is the minimal possible difference.

Intuition

If we find a window with difference zero, we can return immediately because no smaller difference exists.

Algorithm

1. Sort the array.
2. Slide a window of size K over the array.
3. Calculate difference between last and first element in window.
4. If difference is zero, return zero immediately.
5. Otherwise, track minimum difference.
6. Return minimum difference after full scan if zero not found.

💡 This optimization can save time in best cases but does not change worst-case complexity.

</>

Code

def min_diff_early_stop(arr, k):
    arr.sort()
    min_diff = float('inf')
    for i in range(len(arr) - k + 1):
        current_diff = arr[i + k - 1] - arr[i]
        if current_diff == 0:
            return 0
        if current_diff < min_diff:
            min_diff = current_diff
    return min_diff

# Driver code
if __name__ == '__main__':
    arr = [10, 10, 10, 7, 5, 22]
    k = 3
    print(min_diff_early_stop(arr, k))  # Output: 0

Line Notes

arr.sort()Sort array to group close elements

for i in range(len(arr) - k + 1)Slide window of size k

if current_diff == 0Early stop if minimal difference found

if current_diff < min_diffUpdate minimum difference if smaller

import java.util.*;

public class MinDiffEarlyStop {
    public static int minDiffEarlyStop(int[] arr, int k) {
        Arrays.sort(arr);
        int minDiff = Integer.MAX_VALUE;
        for (int i = 0; i <= arr.length - k; i++) {
            int diff = arr[i + k - 1] - arr[i];
            if (diff == 0) return 0;
            if (diff < minDiff) minDiff = diff;
        }
        return minDiff;
    }

    public static void main(String[] args) {
        int[] arr = {10, 10, 10, 7, 5, 22};
        int k = 3;
        System.out.println(minDiffEarlyStop(arr, k)); // Output: 0
    }
}

Line Notes

Arrays.sort(arr)Sort array for sliding window

for (int i = 0; i <= arr.length - k; i++)Slide window over array

if (diff == 0) return 0Return immediately if minimal difference found

if (diff < minDiff) minDiff = diffUpdate minimum difference

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minDiffEarlyStop(vector<int>& arr, int k) {
    sort(arr.begin(), arr.end());
    int minDiff = INT_MAX;
    for (int i = 0; i <= (int)arr.size() - k; i++) {
        int diff = arr[i + k - 1] - arr[i];
        if (diff == 0) return 0;
        if (diff < minDiff) minDiff = diff;
    }
    return minDiff;
}

int main() {
    vector<int> arr = {10, 10, 10, 7, 5, 22};
    int k = 3;
    cout << minDiffEarlyStop(arr, k) << endl; // Output: 0
    return 0;
}

Line Notes

sort(arr.begin(), arr.end())Sort array for contiguous windows

for (int i = 0; i <= (int)arr.size() - k; i++)Slide window of size k

if (diff == 0) return 0Early return on minimal difference

if (diff < minDiff) minDiff = diffUpdate minimum difference found

function minDiffEarlyStop(arr, k) {
    arr.sort((a, b) => a - b);
    let minDiff = Infinity;
    for (let i = 0; i <= arr.length - k; i++) {
        let diff = arr[i + k - 1] - arr[i];
        if (diff === 0) return 0;
        if (diff < minDiff) minDiff = diff;
    }
    return minDiff;
}

// Driver code
const arr = [10, 10, 10, 7, 5, 22];
const k = 3;
console.log(minDiffEarlyStop(arr, k)); // Output: 0

Line Notes

arr.sort((a, b) => a - b)Sort array numerically ascending

for (let i = 0; i <= arr.length - k; i++)Slide window over sorted array

if (diff === 0) return 0Return immediately if minimal difference found

if (diff < minDiff) minDiff = diffUpdate minimum difference

⏱

Complexity

TimeO(n log n) due to sorting, O(n) for sliding window

SpaceO(1) or O(n) depending on sorting

Same as previous approach but with early stopping

💡 Early stopping can save time in best cases but worst case remains same.

Interview Verdict: Accepted / Minor optimization

This is a practical optimization to mention but not required to implement in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always code the sorting + sliding window approach unless input size is tiny.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n choose k * k) exponential	O(n choose k * k)	Yes (deep recursion in combinations)	Yes	Mention only - never code
2. Sorting + Sliding Window	O(n log n)	O(1) or O(n) depending on sort	No	Yes	Code this approach
3. Optimized Sliding Window with Early Stop	O(n log n)	O(1) or O(n)	No	Yes	Mention as optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem constraints and examples.Step 2: Explain brute force approach to show understanding.Step 3: Introduce sorting + sliding window as efficient solution.Step 4: Code the sorting + sliding window approach carefully.Step 5: Test with edge cases and discuss possible optimizations.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Interviewer tests your problem understanding, ability to optimize from brute force, coding accuracy, and handling edge cases.

Common Follow-ups

• What if the array is already sorted? → Skip sorting step.
• How to find the actual subset, not just the difference? → Track window indices with min difference.
• What if duplicates are allowed? → Approach remains same.
• Can this be done without sorting? → Not efficiently for this problem.

💡 These follow-ups test your understanding of problem variations and ability to adapt solutions.

🔍

Pattern Recognition

When to Use

1) Asked to find subset of size K minimizing max-min difference; 2) Input is array of integers; 3) K ≤ n; 4) Minimizing range or difference

Signature Phrases

minimum difference between K elementssubset of size K with smallest range

NOT This Pattern When

Problems asking for maximum difference or subsets without size constraints

Similar Problems

Find K Closest Elements - similar sliding window after sortingSmallest Range Covering Elements from K Lists - extension to multiple lists

Practice

1. What is the time complexity of the optimal two-pointer approach for the 3Sum Smaller problem when the input array has length n?

medium

A. O(n^2) because the outer loop runs n times and the inner two-pointer scan runs in O(n)

B. O(n^3) because of the nested loops

C. O(n log n) due to sorting dominating the complexity

D. O(n^2 log n) because each two-pointer step involves a binary search

Solution

1. Step 1: Identify loops and sorting cost

   Sorting takes O(n log n). The main loop runs O(n) times.

2. Step 2: Analyze inner two-pointer loop

   For each i, two pointers scan the remaining array once, total O(n) per i.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall time is O(n log n + n^2) -> O(n^2) dominates [OK]

Hint: Two pointers scan each element once per outer iteration [OK]

Common Mistakes:

• Confusing two-pointer scan as O(n^2) per iteration
• Ignoring sorting cost or assuming it dominates
• Assuming binary search is used inside two-pointer

2. Identify the bug in the following code snippet that attempts to remove duplicates allowing at most two occurrences from a sorted array.

medium

A. Line 5: Incorrectly resetting count only when read_index == 0

B. Line 9: Allowing count <= 2 instead of count < 2

C. Line 6: Not resetting count when element changes

D. Line 3: Initializing count to 0 instead of 1

Solution

1. Step 1: Analyze count initialization

   Count is initialized to 0 before the loop, but since the first element is always counted, it should start at 1 to reflect the first occurrence.

2. Step 2: Impact of incorrect initialization

   Starting count at 0 can cause off-by-one errors in counting duplicates, potentially allowing more than two duplicates or skipping valid ones.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Count should start at 1 to correctly count the first element [OK]

Hint: Initialize count to 1 before loop to count first element [OK]

Common Mistakes:

• Initializing count to 0 causes off-by-one errors
• Not resetting count properly
• Misplaced count increment

3. What is the time complexity of the optimal two pointers approach for the trapping rain water problem, and why might some candidates mistakenly think it is higher?

medium

A. O(n^2) because each pointer moves inside a nested loop

B. O(n log n) due to sorting or priority queue operations

C. O(n) but with O(n) extra space for auxiliary arrays

D. O(n) because each element is visited at most once by either pointer

Solution

1. Step 1: Analyze pointer movements

   Each pointer (left and right) moves inward only, never revisiting elements, so total steps ≤ n.

2. Step 2: Understand common misconception

   Some think nested if-else inside while implies nested loops, leading to O(n^2) assumption, but loop is single while with two pointers.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two pointers traverse array once -> O(n) time [OK]

Hint: Two pointers move inward once each -> O(n) time [OK]

Common Mistakes:

• Confusing nested if-else with nested loops
• Assuming extra arrays increase time complexity
• Thinking sorting is involved

4. Suppose the input array can contain negative integers and zeros, and you want to partition the array so that all even numbers (including negative evens and zero) come before all odd numbers. Which modification to the original two-pointer algorithm is necessary to handle this correctly?

hard

A. Change the parity check to use abs(nums[i]) % 2 == 0 to handle negative numbers

B. Use a sorting-based approach since parity is ambiguous with negative numbers

C. No change needed; the original parity check nums[i] % 2 == 0 works correctly for negatives and zero

D. Add a separate pass to move zeros to the front before partitioning evens and odds

Solution

1. Step 1: Understand parity with negatives and zero

   In Python, num % 2 == 0 correctly identifies even numbers including negatives and zero.

2. Step 2: Confirm no algorithm change needed

   The original two-pointer approach works unchanged since parity check is valid for all integers.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Modulo operator handles negative evens and zero correctly [OK]

Hint: Modulo operator works for negative evens and zero [OK]

Common Mistakes:

• Thinking abs() is needed for parity check
• Assuming zeros need special handling
• Believing sorting is required for negatives

5. Suppose you want to reverse a string but the input is a very large immutable string (e.g., Python str) instead of a mutable list. Which approach correctly handles this constraint efficiently?

hard

A. Convert the string to a list, reverse it using two pointers, then join back to a string.

B. Use a brute force approach creating a new reversed string by concatenation in a loop.

C. Use the recursive two-pointer approach on the string directly, swapping characters in-place.

D. Use a dynamic programming approach to build the reversed string from substrings.

Solution

1. Step 1: Understand immutability constraint

   Strings are immutable in Python, so in-place swaps are impossible directly on the string.

2. Step 2: Choose efficient workaround

   Converting to a list allows in-place two-pointer swaps, then joining back creates the reversed string efficiently in O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only Convert the string to a list, reverse it using two pointers, then join back to a string. respects immutability and is efficient [OK]

Hint: Immutable strings require conversion to mutable type for in-place reversal [OK]

Common Mistakes:

• Trying to swap characters in immutable string
• Using inefficient string concatenation in loop
• Misapplying DP to string reversal