Minimum Difference Between Largest and Smallest Value in Three Moves

Minimum Difference Between Largest and Smallest Value in Three Moves - Problem

You are given an integer array nums.

In one move, you can choose one element of nums and change it to any value.

Return the minimum difference between the largest and smallest value of nums after performing at most three moves.

Input & Output

Example 1 — Basic Case

$ Input: nums = [5,3,2,4]

› Output: 0

💡 Note: We can change elements to make them all equal. For instance, change 5→3, 2→3, 4→3. Result: [3,3,3,3] with difference = 3-3 = 0.

Example 2 — Optimal Removal

$ Input: nums = [1,5,0,10,14]

› Output: 1

💡 Note: Sort: [0,1,5,10,14]. Try removing 3 extremes: remove 0,10,14 → [1,5] with difference = 5-1 = 4. Or remove 14,10,0 → [1,5] = 4. Best is remove 0,1,14 → [5,10] = 5, or remove 14,10,5 → [0,1] = 1.

Example 3 — Small Array

$ Input: nums = [6,6,0,1,1,4,6]

› Output: 2

💡 Note: Sort: [0,1,1,4,6,6,6]. Remove 3 elements optimally: remove 0,6,6 → [1,1,4,6] with difference = 6-1 = 5. Better: remove 0,1,6 → [1,4,6,6] = 5. Best: remove 6,6,6 → [0,1,1,4] = 4-0 = 4. Actually optimal is remove 0,6,6 → [1,1,4,6] then change to get difference 2.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array with various elements creating a large range

Strategy

Remove or change extreme values to minimize range

Output

Minimum possible difference after 3 moves

Key Takeaway

🎯 Key Insight: With 3 moves on arrays ≤4 elements, we can make all elements equal (difference=0). For larger arrays, greedily remove extreme values.

Asked in

G Google 23 A Amazon 18 M Microsoft 15 🍎 Apple 12

The key insight is that we should always remove extreme values (largest/smallest) to minimize the range. After sorting, we only need to check 4 scenarios of removing elements from the ends. Best approach is Greedy with Sorting. Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(n⁴)	O(1)	Try all possible ways to change up to 3 elements and find minimum difference
Greedy - Always Target Extremes	O(n log n)	O(1)	Greedy approach that always removes the most extreme values (largest or smallest)
Sort and Remove Extremes	O(n log n)	O(1)	Sort array first, then optimally remove elements from ends to minimize difference

Brute Force - Try All Combinations — Algorithm Steps

Step 1: Generate all combinations of 0-3 elements to change
Step 2: For each combination, try optimal values for changed elements
Step 3: Calculate min-max difference and track minimum

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Combinations

Create all possible combinations of 0-3 elements to change

Test Each Combination

For each combination, calculate the difference of remaining elements

Find Minimum

Track the minimum difference across all combinations

Code -

solution.c — C

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

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

int solution(int* nums, int n) {
    if (n <= 4) return 0;
    
    qsort(nums, n, sizeof(int), compare);
    
    int minDiff = INT_MAX;
    
    // Check 4 scenarios: remove 0,1,2,3 from left and 3,2,1,0 from right
    for (int left = 0; left < 4; left++) {
        int right = 3 - left;
        if (left + right < n) {
            int diff = nums[n - 1 - right] - nums[left];
            if (diff < minDiff) {
                minDiff = diff;
            }
        }
    }
    
    return minDiff;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int nums[1000];
    int n = 0;
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token != NULL) {
            nums[n++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n⁴)

Need to try C(n,3) combinations and for each check all remaining elements

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track combinations and minimum difference

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 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

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler