Minimum Number of Operations to Make (#2009)

lcpy gen -n 2009   # by problem number
lcpy gen -s minimum_number_of_operations_to_make_array_continuous   # by problem name

Input: nums = [4,2,5,3]
Output: 0
Explanation: nums is already continuous.

Input: nums = [1,2,3,5,6]
Output: 1
Explanation: One possible solution is to change the last element to 4.
The resulting array is [1,2,3,5,4], which is continuous.

Input: nums = [1,10,100,1000]
Output: 3
Explanation: One possible solution is to change the last three elements to 2, 3 and 4.
The resulting array is [1,2,3,4], which is continuous.

class Solution:
    # Time: O(n log n)
    # Space: O(n)
    def min_operations(self, nums: list[int]) -> int:
        n = len(nums)
        vals = sorted(set(nums))
        best = 0
        left = 0
        for right in range(len(vals)):
            while vals[right] - vals[left] > n - 1:
                left += 1
            best = max(best, right - left + 1)
        return n - best