Minimum Difference After 3 Operations - Detailed Analysis

This algorithm finds the minimum possible difference between the maximum and minimum values in an array after performing at most 3 operations (changing any element to any value).

Problem Understanding

Goal: Minimize max(array) - min(array) after changing at most 3 elements.

Key Insight: To minimize the difference, we should either:

1. Remove the largest elements, or

2. Remove the smallest elements, or

3. Remove some combination of both

Since we can change 3 elements, we have 4 strategies:

• Change 3 largest elements

• Change 2 largest + 1 smallest

• Change 1 largest + 2 smallest

• Change 3 smallest elements

Algorithm Walkthrough

public int minDifference(int[] nums) {

    // Edge case: If array has 4 or fewer elements

    if (nums.Length <= 4) return 0;

    

    Array.Sort(nums); // Sort the array

    int n = nums.Length;

    

    // Compare 4 possible strategies

    return Math.Min(

        Math.Min(nums[n - 1] - nums[3],     // Strategy 1: Remove 3 smallest

                 nums[n - 4] - nums[0]),    // Strategy 2: Remove 3 largest

        Math.Min(nums[n - 2] - nums[2],     // Strategy 3: Remove 2 smallest, 1 largest

                 nums[n - 3] - nums[1])     // Strategy 4: Remove 1 smallest, 2 largest

    );

}

The 4 Strategies Explained

After sorting, we consider removing elements from ends:

| Strategy | Remove From | New Range | Formula |

|----------|-------------|-----------|---------|

| 1 | 3 smallest | [nums[3], nums[n-1]] | nums[n-1] - nums[3] |

| 2 | 3 largest | [nums[0], nums[n-4]] | nums[n-4] - nums[0] |

| 3 | 2 smallest, 1 largest | [nums[2], nums[n-2]] | nums[n-2] - nums[2] |

| 4 | 1 smallest, 2 largest | [nums[1], nums[n-3]] | nums[n-3] - nums[1] |

Detailed Examples

Example 1: [1, 5, 6, 14, 15]

Step 1: Sort the array → [1, 5, 6, 14, 15]

• n = 5

• Indices: [0, 1, 2, 3, 4]

Step 2: Calculate each strategy:

| Strategy | Calculation | Result | Meaning |

|----------|-------------|--------|---------|

| 1 | nums[4] - nums[3] = 15 - 14 | 1 | Remove [1,5,6], keep [14,15] |

| 2 | nums[1] - nums[0] = 5 - 1 | 4 | Remove [6,14,15], keep [1,5] |

| 3 | nums[3] - nums[2] = 14 - 6 | 8 | Remove [1,5,15], keep [6,14] |

| 4 | nums[2] - nums[1] = 6 - 5 | 1 | Remove [1,14,15], keep [5,6] |

Step 3: Math.Min(1, 4, 8, 1) = 1

Result: 1 (achieved by strategies 1 or 4)

Example 2: [10, 10, 10, 10, 10]

Step 1: Already sorted → [10, 10, 10, 10, 10]

Step 2: All strategies give: 10 - 10 = 0

Result: 0

Example 3: [1, 100, 200, 300, 400]

Step 1: Already sorted → [1, 100, 200, 300, 400]

Step 2: Calculate each strategy:

| Strategy | Calculation | Result | Meaning |

|----------|-------------|--------|---------|

| 1 | 400 - 300 = 100 | 100 | Keep [300,400] |

| 2 | 100 - 1 = 99 | 99 | Keep [1,100] |

| 3 | 300 - 200 = 100 | 100 | Keep [200,300] |

| 4 | 200 - 100 = 100 | 100 | Keep [100,200] |

Step 3: Math.Min(100, 99, 100, 100) = 99

Result: 99

Visual Representation

For array [1, 5, 6, 14, 15]:

Original: [1,  5,  6, 14, 15]  → difference = 15-1 = 14

           ↑   ↑   ↑   ↑   ↑

Index:     0   1   2   3   4



Strategy 1: Remove 3 smallest

[X,  X,  X, 14, 15]  → difference = 15-14 = 1



Strategy 2: Remove 3 largest  

[1,  5,  X,  X,  X]  → difference = 5-1 = 4



Strategy 3: Remove 2 smallest + 1 largest

[X,  X,  6, 14,  X]  → difference = 14-6 = 8



Strategy 4: Remove 1 smallest + 2 largest

[X,  5,  6,  X,  X]  → difference = 6-5 = 1

Edge Case Analysis

Arrays with ≤ 4 elements:

if (nums.Length <= 4) return 0;

Reason: We can change 3 elements, so:

• 1 element: Change 0, difference = 0

• 2 elements: Change 1, make them equal → difference = 0

• 3 elements: Change 2, make them equal → difference = 0

• 4 elements: Change 3, make them equal → difference = 0

Time & Space Complexity

Time Complexity: O(n log n)

• Sorting: Array.Sort(nums) → O(n log n)

• Calculations: O(1) for 4 comparisons

• Overall: O(n log n)

Space Complexity: O(1)

• In-place sorting: No extra arrays needed

• Variables: Only a few integer variables

• Overall: O(1)

Algorithm Correctness

Why only 4 strategies?

Since we can change at most 3 elements, and we want to minimize max - min, the optimal strategy is always to remove elements from the extremes (smallest or largest).

Proof by contradiction:

• Changing a middle element to any value won't improve the min-max difference as much as removing an extreme element.

• The 4 strategies cover all possible combinations of removing 0-3 elements from each end.

Why sorting is necessary?

• To identify the smallest and largest elements efficiently

• To calculate the new min and max after hypothetical removals

Alternative Implementation (More Readable)

public int minDifference(int[] nums) {

    if (nums.Length <= 4) return 0;

    

    Array.Sort(nums);

    int n = nums.Length;

    

    // Four strategies: remove (small, large) counts

    int[] strategies = {

        nums[n-1] - nums[3],    // (3, 0): Remove 3 smallest

        nums[n-4] - nums[0],    // (0, 3): Remove 3 largest  

        nums[n-2] - nums[2],    // (2, 1): Remove 2 smallest, 1 largest

        nums[n-3] - nums[1]     // (1, 2): Remove 1 smallest, 2 largest

    };

    

    return strategies.Min();

}

Summary

| Aspect | Details |

|--------|---------|

| Problem Type | Array manipulation, optimization |

| Key Insight | Remove extreme values to minimize range |

| Time Complexity | O(n log n) due to sorting |

| Space Complexity | O(1) |

| Edge Cases | Arrays with ≤ 4 elements always return 0 |

| Strategies | 4 combinations of removing from ends |

The algorithm efficiently finds the optimal solution by considering all meaningful ways to use the 3 allowed changes.