Minimize the Maximum Difference of Pairs - Practice Coding Problems

Minimize the Maximum Difference of Pairs - Problem

You are given a 0-indexed integer array nums and an integer p. Find p pairs of indices of nums such that the maximum difference amongst all the pairs is minimized. Also, ensure no index appears more than once amongst the p pairs.

Note that for a pair of elements at the index i and j, the difference of this pair is |nums[i] - nums[j]|, where |x| represents the absolute value of x.

Return the minimum maximum difference among all p pairs. We define the maximum of an empty set to be zero.

Input & Output

Example 1 — Basic Case

$ Input: nums = [10,1,2,7,1,3], p = 2

› Output: 1

💡 Note: After sorting: [1,1,2,3,7,10]. We can form pairs (1,1) with diff=0 and (2,3) with diff=1. Maximum difference is 1.

Example 2 — Single Pair

$ Input: nums = [4,2,1,2], p = 1

› Output: 0

💡 Note: After sorting: [1,2,2,4]. We can pair (2,2) with difference 0, which is the minimum possible.

Example 3 — Edge Case p=0

$ Input: nums = [1,2,3,4], p = 0

› Output: 0

💡 Note: When p=0, we need to form 0 pairs. The maximum of an empty set is defined as 0.

Constraints

1 ≤ nums.length ≤ 10⁵
0 ≤ p ≤ (nums.length)/2
0 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array [10,1,2,7,1,3] and p=2 pairs needed

Sort & Strategy

Sort array and use binary search on answer

Output

Minimum maximum difference is 1

Key Takeaway

🎯 Key Insight: Sort first, then binary search on the maximum difference value with greedy validation

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use binary search on the answer space combined with greedy validation. After sorting the array, we binary search on possible maximum difference values and use a greedy approach to check if we can form p pairs with that constraint. Best approach is Binary Search + Greedy with Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer + Greedy	O(n log n)	O(1)	Binary search on the maximum difference value, use greedy to check feasibility
Brute Force - Try All Combinations	O(n^(2p))	O(p)	Generate all possible ways to select p pairs and find minimum maximum difference

Binary Search on Answer + Greedy — Algorithm Steps

Sort the array to enable greedy pairing
Binary search on the maximum difference value
For each candidate, greedily check if p pairs are possible

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Array

Sort to enable greedy adjacent pairing

Binary Search

Search for minimum feasible maximum difference

Greedy Check

For each candidate, greedily form pairs from left to right

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int canFormPairs(int* nums, int nums_size, int p, int maxDiff) {
    int pairs = 0;
    int i = 0;
    
    while (i < nums_size - 1) {
        if (nums[i + 1] - nums[i] <= maxDiff) {
            pairs++;
            i += 2;
            if (pairs >= p) return 1;
        } else {
            i++;
        }
    }
    
    return pairs >= p;
}

int solution(int* nums, int nums_size, int p) {
    if (p == 0) return 0;
    
    qsort(nums, nums_size, sizeof(int), compare);
    
    int left = 0;
    int right = nums[nums_size - 1] - nums[0];
    int result = right;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (canFormPairs(nums, nums_size, p, mid)) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing
    int nums[100];
    int nums_size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL && nums_size < 100) {
        int val = atoi(token);
        if (val != 0 || token[0] == '0') {
            nums[nums_size++] = val;
        }
        token = strtok(NULL, "[,]");
    }
    
    int p;
    scanf("%d", &p);
    
    int result = solution(nums, nums_size, p);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

O(n log n) for sorting + O(log(max_diff) * n) for binary search with greedy validation

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer + Greedy — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler