# LC 2009. Minimum Number of Operations to Make Array Continuous

### [Problem link](https://leetcode.com/problems/minimum-number-of-operations-to-make-array-continuous/)

###### tags: `leedcode` `hard` `c++` `Sliding Window`

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

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

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

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

Return the **minimum** number of operations to make <code>nums</code> **continuous** .

**Example 1:**

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

**Example 2:**

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.

**Example 3:**

Input: nums = [1,10,100,1000]
Output: 3
Explanation: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.

**Constraints:**

- <code>1 <= nums.length <= 10⁵</code>
- <code>1 <= nums[i] <= 10⁹</code>

## Solution 1 - Sliding Window
#### C++

class Solution {
public:
    int minOperations(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int m = unique(nums.begin(), nums.end()) - nums.begin();
        int ans = 0;
        int l = 0;
        for (int r = 0; r < m; r++) {
            while (nums[r] - nums[l] + 1 > n) {
                l++;
            }
            ans = max(ans, r - l + 1);
        }
        return n - ans;
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(nlogn) | O(1) |

## Note
Sol1:
正難則反，去想要留幾個元素。

ex: 2,3,4,6
    l     r
nums[r] - nums[l] + 1 = 5, 代表至少需要5個數字在[l, r]之間，又知道[l, r]間的數字不重複，且r - l + 1 = 4，代表需要換一個數字，反過來說就是留三個數字。
while (nums[r] - nums[l] + 1 > n) {
    l++;
}