⚡Flashcard Drill➔
NeetCode #788LC-1509MediumGreedy
← Back to All Problems

#788 · #1509 · Minimum Difference Between Largest and Smallest Value in Three Moves(三次操作后最大值与最小值的最小差值)

📌 Problem Statement & Constraints

Given an array nums, in one move you may change any element to any value. Return the minimum difference between the largest and smallest values after at most three moves. Constraints: 1 <= nums.length <= 10^5, -10^9 <= nums[i] <= 10^9.

💡 Core Algorithmic Approaches

  1. Changing an element to any value is equivalent to removing it from consideration, since it can always be set to match the remaining extremes.
  2. With three moves, you may remove up to three elements, all from the low end, all from the high end, or a mix.
  3. Sort the array; the remaining range after removing i smallest and 3 - i largest is [i, n - 4 + i].
  4. Try all four splits i = 0..3 and take the smallest range.

💻 Benchmark Python3 Implementation

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 4:
            return 0                   # all elements can be equalised
        nums.sort()
        return min(nums[n - 4 + i] - nums[i] for i in range(4))

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): the sort dominates; the four candidates are O(1).
💾 Space Complexity
O(1) beyond the sort.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the n <= 4 case: with four or fewer elements all of them can be changed to one value, giving 0.
  • Only removing from one end: the optimal removal may split between the low and high ends.
  • Changing elements to values inside the range: the best move is always to equalise with an extreme, so removal is the right model.
  • Trying all C(n, 3) removals: only the four sorted-window candidates matter.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems