1509. Minimum Difference Between Largest and Smallest Value in Three Moves

Time: O(n log n)

Space: O(1)

Intuition

Minimum difference after at most 3 changes. Sort. We can change 3 smallest to equal largest, or 3 largest to equal smallest, or mix. Check 4 strategies.

Algorithm

1Sort. Try: remove 3 from left, remove 3 from right, remove 1 left + 2 right, remove 2 left + 1 right.
2Answer = min of nums[n-1-j] - nums[i] for (i+j==3, i in 0..3).

Common Pitfalls

•After sorting and 3 changes, minimum difference = min over 4 strategies of nums[n-1-j] - nums[i].

1509.cs

// Approach: Sort; try all 4 ways of removing 3 elements from the ends; return the minimum resulting range.
// Time: O(n log n) Space: O(1)

public class Solution
{
    public int MinDifference(int[] nums)
    {
        int n = nums.Length;

        if (n < 5)
            return 0;

        int ans = Int32.MaxValue;

        Array.Sort(nums);

        for (int i = 0; i < 4; i++)
            ans = Math.Min(ans, nums[n - 4 + i] - nums[i]);

        return ans;
    }
}

Was this solution helpful?