<p>You are given an integer array <code>nums</code>. In one operation, you can replace <strong>any</strong> element in <code>nums</code> with <strong>any</strong> integer.</p>

<p><code>nums</code> is considered <strong>continuous</strong> if both of the following conditions are fulfilled:</p>

<ul>
	<li>All elements in <code>nums</code> are <strong>unique</strong>.</li>
	<li>The difference between the <strong>maximum</strong> element and the <strong>minimum</strong> element in <code>nums</code> equals <code>nums.length - 1</code>.</li>
</ul>

<p>For example, <code>nums = [4, 2, 5, 3]</code> is <strong>continuous</strong>, but <code>nums = [1, 2, 3, 5, 6]</code> is <strong>not continuous</strong>.</p>

<p>Return <em>the <strong>minimum</strong> number of operations to make </em><code>nums</code><em> </em><strong><em>continuous</em></strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [4,2,5,3]
<strong>Output:</strong> 0
<strong>Explanation:</strong>&nbsp;nums is already continuous.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,5,6]
<strong>Output:</strong> 1
<strong>Explanation:</strong>&nbsp;One possible solution is to change the last element to 4.
The resulting array is [1,2,3,5,4], which is continuous.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,10,100,1000]
<strong>Output:</strong> 3
<strong>Explanation:</strong>&nbsp;One possible solution is to:
- Change the second element to 2.
- Change the third element to 3.
- Change the fourth element to 4.
The resulting array is [1,2,3,4], which is continuous.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

'''
Continuous means exactly what the word is - the order doesnt matter 
So in sorted order the difference in every num in array is 1
The problem asks us to find the min operations to make an array continuous
For example for the case 1 2 3 5 6 if we replace 6 by 4 we get a continuous array
So the range of the array is going to be [x, x + len(arr) - 1] - for above example: [1, 5]
The worst case is that we can keep just ONE number same and change the rest of the array - for example [1, 10, 100, 1000]
The problem is we dont know which number to keep. So we consider every element in array as "X" - and for range[x, x + n - 1] for
every x + 1 in range we check if that exists in array and then we get the number of elements that dont exist which would be
our answer. This is brute force approach.
# Sliding Window Technique
So instead of the brute force approach where we iterate through every element to check if it is in the range, we can be smart about this
We treat every num in nums as the left pointer. Now we just have to calculate the number of nums in range[left, n + left - 1]. So for that
we maintain a right pointer which starts at 0 initally but for a num at left goes until right is out of range. So we know everything before right is in the range. How is this better than brute force? Because for next num left we dont start right from 0. We know that right is 
either at the same position or at +1. And then we just track the minimum for n - window_size where window_size = right - left
'''
class Solution:
    def minOperations(self, nums: List[int]) -> int:
        ''' Brute Force
        def check(x):
            count = 0
            for i in range(x, x + n):
                if i not in nums:
                    count += 1
            return count          
        
        n = len(nums)
        nums.sort()
        nums = set(nums)

        ans = float('inf')
        for num in nums:
            ans = min(ans, check(num))
        
        return ans 
        '''
        n = len(nums)
        nums = sorted(set(nums))
        result = n # worst is gonna be all replaced 

        right = 0
        for left in range(len(nums)):
            while right < len(nums) and nums[right] < n + nums[left]:
                right += 1
            window = right - left
            result = min(result, n - window)
        return result

580