Minimum Difference Between Largest and Smallest Value in Three Moves — LeetCode 1509 Python Solution

The problem

You are given an integer array nums. In one move, you can choose one element of nums and change it to any value.

Example

Input

nums = [5,3,2,4]

Output

0

Explanation

We can make at most 3 moves.

Python solution

class Solution:
    def minDifference(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 5:
            return 0
        nums.sort()
        ans = inf
        for l in range(4):
            r = 3 - l
            ans = min(ans, nums[n - 1 - r] - nums[l])
        return ans

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 1509. Minimum Difference Between Largest and Smallest Value in Three Moves is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems