# Minimum Number of Operations to Make Array Continuous
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-number-of-operations-to-make-array-continuous)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-operations-to-make-array-continuous
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Hash Table
---
## Problem
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:** 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:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 109`

# Approaches
## Iteration with Binary Search
This approach tackles the problem by first simplifying the input array. Since a continuous array must contain unique elements, we start by removing duplicates. After sorting these unique elements, we iterate through each one, treating it as the potential starting number of our target continuous sequence. For each potential start, we use binary search to efficiently find how many of the other unique numbers could fit into the required range (`[start, start + n - 1]`). By keeping track of the maximum number of elements that can fit into any such window, we can determine the minimum number of changes needed.
**Time:** O(N log N), where N is the number of elements in the input array. Let M be the number of unique elements. The complexity is O(N) for creating the unique set, O(M log M) for sorting, and O(M log M) for the loop with binary search. Since M <= N, the total complexity is dominated by O(N log N). · **Space:** O(N), where N is the number of elements in the input array. This is for storing the unique elements in a set and an auxiliary array. In the worst case, all elements are unique.
**Pros:** A correct and logical approach that is significantly more efficient than a naive brute-force check.; The use of binary search improves the search for the window's end from linear to logarithmic time.
**Cons:** While having the same big-O time complexity as the optimal solution, it is practically slower due to the repeated binary searches inside a loop.
### Explanation
The core idea is to rephrase the problem: instead of minimizing operations, we aim to maximize the number of elements we can *keep* from the original array. An element can be kept if it can be part of a final continuous array.

A continuous array of length `n` has unique elements and its maximum element minus its minimum element equals `n - 1`. This means if we keep a subset of numbers from the original `nums`, say with minimum `min_val` and maximum `max_val`, they must satisfy `max_val - min_val < n` to fit into a continuous sequence of length `n`.

Our algorithm proceeds as follows:
1.  First, we filter `nums` to get a list of unique elements, as duplicates cannot exist in the final continuous array. Let's call this new array `unique_nums`.
2.  We sort `unique_nums`. This allows us to easily check ranges.
3.  We then iterate through each element `unique_nums[i]` and consider it the minimum element of a potential subsequence we can keep.
4.  For a window starting with `unique_nums[i]`, the largest possible element must be less than `unique_nums[i] + n`. We can find the right boundary of this window using binary search. Specifically, we search for the first element in `unique_nums` that is greater than or equal to `unique_nums[i] + n`.
5.  The number of elements in this valid window gives us a potential count of elements to keep. We find the maximum such count over all possible starting elements.
6.  The minimum number of operations is the total number of elements `n` minus the maximum number of elements we can keep.

```java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int minOperations(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return 0;
        }

        // Step 1: Get unique elements
        Set<Integer> uniqueSet = new HashSet<>();
        for (int num : nums) {
            uniqueSet.add(num);
        }
        int[] uniqueNums = new int[uniqueSet.size()];
        int index = 0;
        for (int num : uniqueSet) {
            uniqueNums[index++] = num;
        }

        // Step 2: Sort the unique elements
        Arrays.sort(uniqueNums);

        int maxKeep = 0;
        // Step 3 & 4: Iterate and use binary search
        for (int i = 0; i < uniqueNums.length; i++) {
            int startVal = uniqueNums[i];
            int target = startVal + n;
            
            // Find the insertion point for 'target'
            int endIdx = binarySearch(uniqueNums, i, target);
            
            // Step 5: Update maxKeep
            maxKeep = Math.max(maxKeep, endIdx - i);
        }

        // Step 6: Calculate result
        return n - maxKeep;
    }

    // Custom binary search to find the insertion point of 'target'
    // This finds the index of the first element >= target
    private int binarySearch(int[] arr, int startIdx, int target) {
        int left = startIdx;
        int right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
```
### Algorithm
- Get the length `n` of the input array `nums`.
- Create a new array `unique_nums` containing only the unique elements from `nums`. This can be done using a `HashSet`.
- Sort `unique_nums` in ascending order.
- Initialize a variable `maxKeep = 0` to store the maximum number of elements we can keep.
- Iterate through the `unique_nums` array with an index `i` from `0` to `unique_nums.length - 1`.
- For each `unique_nums[i]`, consider it as the minimum value of a potential continuous sequence.
- The maximum value in this sequence would be `unique_nums[i] + n - 1`.
- Use binary search on `unique_nums` to find the index of the first element that is strictly greater than `unique_nums[i] + n - 1`. Let this be `end_idx`.
- The number of elements from the original array that can be part of this continuous sequence is `end_idx - i`.
- Update `maxKeep = max(maxKeep, end_idx - i)`.
- After iterating through all possible start elements, the minimum number of operations required is `n - maxKeep`.

## Sliding Window on Sorted Unique Array
This is the most optimal approach. It also begins by creating a sorted array of unique elements. However, instead of re-calculating the size of the valid window for each starting element, it uses a more efficient sliding window (two-pointer) technique. One pointer (`right`) expands the window, and another pointer (`left`) shrinks it when the condition for a continuous sequence is violated. This allows us to find the longest possible valid subsequence in a single linear pass over the unique elements, making it faster than the binary search approach.
**Time:** O(N log N), where N is the number of elements in the input array. Let M be the number of unique elements. The complexity is O(N) for creating the unique set, O(M log M) for sorting, and O(M) for the sliding window. Since M <= N, the total complexity is dominated by the sorting step, resulting in O(N log N). · **Space:** O(N), where N is the number of elements in the input array. This space is used to store the unique elements.
**Pros:** This is the most efficient solution for this problem.; The sliding window part runs in linear time with respect to the number of unique elements, which is an improvement over the binary search approach.
**Cons:** The overall time complexity is limited by the sorting step, not the sliding window itself.
### Explanation
This approach refines the previous one by replacing the repeated binary searches with a more efficient sliding window method. The initial setup is the same: we find the maximum number of elements we can keep (`maxKeep`) and the answer will be `n - maxKeep`.

1.  First, we create a sorted array of unique elements, `unique_nums`, from the input `nums`.
2.  We use two pointers, `left` and `right`, both starting at index 0 of `unique_nums`. These pointers define a 'window' of elements we are considering to keep.
3.  We iterate through `unique_nums` by advancing the `right` pointer. This expands our window to include a new, larger element.
4.  With each expansion, we check if the window remains valid. A window `[left, right]` is valid if the elements within it can be part of a continuous sequence of length `n`. The condition for this is `unique_nums[right] - unique_nums[left] <= n - 1`.
5.  If the condition is violated (`unique_nums[right] - unique_nums[left] > n - 1`), it means our window is too wide. We must shrink it by incrementing the `left` pointer until the condition is satisfied again.
6.  At each step, the length of the valid window `[left, right]` is `right - left + 1`. We keep track of the maximum length seen so far in `maxKeep`.
7.  By the time the `right` pointer reaches the end, we will have found the longest subarray of `unique_nums` that can fit into a continuous sequence of length `n`. The final answer is `n - maxKeep`.

This method is more efficient because each pointer (`left` and `right`) only traverses the `unique_nums` array once.

```java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int minOperations(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return 0;
        }

        // Step 1: Get unique elements and sort them
        Set<Integer> uniqueSet = new HashSet<>();
        for (int num : nums) {
            uniqueSet.add(num);
        }
        int[] uniqueNums = new int[uniqueSet.size()];
        int index = 0;
        for (int num : uniqueSet) {
            uniqueNums[index++] = num;
        }
        Arrays.sort(uniqueNums);

        int maxKeep = 0;
        int left = 0;
        // Step 2: Use a sliding window
        for (int right = 0; right < uniqueNums.length; right++) {
            // Step 3: Shrink window if condition is violated
            while (uniqueNums[right] - uniqueNums[left] >= n) {
                left++;
            }
            // Step 4: Update maxKeep with current valid window size
            int currentKeep = right - left + 1;
            maxKeep = Math.max(maxKeep, currentKeep);
        }

        // Step 5: Calculate result
        return n - maxKeep;
    }
}
```
### Algorithm
- Get the length `n` of the input array `nums`.
- Create a sorted array `unique_nums` from the unique elements of `nums`.
- Initialize two pointers, `left = 0` and `right = 0`, to define a sliding window on `unique_nums`.
- Initialize `maxKeep = 0`.
- Iterate with the `right` pointer from the beginning to the end of `unique_nums`.
- In each iteration, expand the window by moving `right`.
- Check if the current window is valid: `unique_nums[right] - unique_nums[left] < n`. 
- If the window is invalid (the difference is too large), shrink the window from the left by incrementing the `left` pointer until the window becomes valid again.
- After each adjustment, the current window `[left, right]` is the largest valid window ending at `right`. Its length is `right - left + 1`.
- Update `maxKeep = max(maxKeep, right - left + 1)`.
- After the loop finishes, the result is `n - maxKeep`.

# Solutions
### Java

```java
class Solution {
public
  int minOperations(int[] nums) {
    int n = nums.length;
    Arrays.sort(nums);
    int m = 1;
    for (int i = 1; i < n; ++i) {
      if (nums[i] != nums[i - 1]) {
        nums[m++] = nums[i];
      }
    }
    int ans = n;
    for (int i = 0; i < m; ++i) {
      int j = search(nums, nums[i] + n - 1, i, m);
      ans = Math.min(ans, n - (j - i));
    }
    return ans;
  }
private
  int search(int[] nums, int x, int left, int right) {
    while (left < right) {
      int mid = (left + right) >> 1;
      if (nums[mid] > x) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minOperations(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    int m = unique(nums.begin(), nums.end()) - nums.begin();
    int n = nums.size();
    int ans = n;
    for (int i = 0; i < m; ++i) {
      int j = upper_bound(nums.begin() + i, nums.begin() + m, nums[i] + n - 1) -
              nums.begin();
      ans = min(ans, n - (j - i));
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minOperations(self, nums: List[int]) -> int: ans = n = len(nums) nums = sorted(set(nums)) for i, v in enumerate(nums): j = bisect_right(nums, v + n - 1) ans = min(ans, n - (j - i)) return ans

```