Formatted question description: https://leetcode.ca/all/2009.html

# 2009. Minimum Number of Operations to Make Array Continuous (Hard)

You are given an integer array `nums`

. In one operation, you can replace **any** element in `nums`

with **any** integer.

`nums`

is considered **continuous** if both of the following conditions are fulfilled:

- All elements in
`nums`

are**unique**. - The difference between the
**maximum**element and the**minimum**element in`nums`

equals`nums.length - 1`

.

For example, `nums = [4, 2, 5, 3]`

is **continuous**, but `nums = [1, 2, 3, 5, 6]`

is **not continuous**.

Return *the minimum number of operations to make *

`nums`

**.**

*continuous*

**Example 1:**

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

**Example 2:**

Input:nums = [1,2,3,5,6]Output:1Explanation: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:3Explanation: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:**

`1 <= nums.length <= 10`

^{5}`1 <= nums[i] <= 10`

^{9}

**Similar Questions**:

- Longest Repeating Character Replacement (Medium)
- Continuous Subarray Sum (Medium)
- Moving Stones Until Consecutive II (Medium)
- Minimum One Bit Operations to Make Integers Zero (Hard)
- Minimum Adjacent Swaps for K Consecutive Ones (Hard)

## Solution 1. Sliding Window

Check out “C++ Maximum Sliding Window Cheatsheet Template!”.

**Intuition**: Sort and only keep unique elements. The problem is the same as “get the length of the longest subarray whose difference between min and max elements is `N - 1`

”.

**Algorithm**:

The brute force way is to pick each `A[i]`

as the start of the subarray and count the number of elements that are `<= A[i] + N - 1`

, which takes `O(N^2)`

time.

Since the array is already sorted, we can use sliding window so that we only traverse the entire array once.

```
// OJ: https://leetcode.com/problems/minimum-number-of-operations-to-make-array-continuous/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
int minOperations(vector<int>& A) {
int N = A.size(), ans = N, j = 0;
sort(begin(A), end(A));
A.erase(unique(begin(A), end(A)), end(A)); // only keep unique elements
int M = A.size();
for (int i = 0; i < M; ++i) {
while (j < M && A[j] < A[i] + N) ++j; // let `j` point to the first element that is out of range -- `>= A[i] + N`.
ans = min(ans, N - j + i); // The length of this subarray is `j - i`. We need to replace `N - j + i` elements to make it continuous.
}
return ans;
}
};
```

Use Shrinkable Sliding Window Template:

```
// OJ: https://leetcode.com/problems/minimum-number-of-operations-to-make-array-continuous/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
int minOperations(vector<int>& A) {
int N = A.size(), i = 0, j = 0, ans = 0;
sort(begin(A), end(A));
A.erase(unique(begin(A), end(A)), end(A)); // only keep unique elements
for (int M = A.size(); j < M; ++j) {
while (A[i] + N <= A[j]) ++i; // let `i` point to the first element that is in range -- `A[i] + N > A[j]`
ans = max(ans, j - i + 1);
}
return N - ans;
}
};
```

Use Non-shrinkable Sliding Window Template:

```
// OJ: https://leetcode.com/problems/minimum-number-of-operations-to-make-array-continuous/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
int minOperations(vector<int>& A) {
int N = A.size(), i = 0, j = 0;
sort(begin(A), end(A));
A.erase(unique(begin(A), end(A)), end(A)); // only keep unique elements
for (int M = A.size(); j < M; ++j) {
if (A[i] + N <= A[j]) ++i;
}
return N - j + i;
}
};
```

## Discuss

https://leetcode.com/problems/minimum-number-of-operations-to-make-array-continuous/discuss/1470857/C%2B%2B-Sliding-Window