Minimum Number of Operations to Make Array Continuous

How it works

We can optimize space by removing duplicates in-place after sorting. Instead of creating a new array, we overwrite the original array with unique elements. The sliding window logic remains the same, but we avoid allocating extra space for the deduplicated array.

Steps

1. Sort the array in place.
2. Remove duplicates by keeping a write pointer n that tracks the position for the next unique element.
3. Use a sliding window with the left pointer advancing when the range exceeds length - 1.
4. After processing, return length - (n - l), where n - l is the max window size found.

Complexity

• Time complexity: O(n log n)
• Space complexity: O(1) or O(n) depending on the sorting algorithm.

Things to watch for

Forgetting to Remove Duplicates

The continuous array must have n unique elements. If you count duplicates when determining how many elements can stay unchanged, you will overcount and return an incorrect (smaller) number of operations. Always deduplicate before processing.

Using Original Array Length Instead of Unique Count

After removing duplicates, the unique array may be shorter than the original. If you use the original length n for window size calculations but iterate over the shorter unique array, your indexing will be off. Use the original n for the target range size but the unique array length for iteration bounds.

Off-by-One in Range Boundary

The valid range for a continuous array starting at value min is [min, min + n - 1]. A common mistake is using min + n as the upper bound, which allows one extra value. This causes the algorithm to count elements that should not be in the window.

Not Counting the Starting Element

When calculating how many elements are already in the valid range, some implementations forget to count the starting element itself. If the element at position i is the minimum, it should always be counted as one element that does not need replacement.

Binary Search Target Error

When using binary search to find elements in range, the search should find the first position where nums[j] >= nums[i] + n. Searching for nums[j] > nums[i] + n - 1 is equivalent but easy to get wrong. Off-by-one errors in binary search bounds lead to incorrect window sizes.

from typing import List

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        length = len(nums)
        nums.sort()
        res = length
        n = 1

        for i in range(1, length):
            if nums[i] != nums[i - 1]:
                nums[n] = nums[i]
                n += 1

        l = 0
        for r in range(n):
            l += (nums[r] - nums[l] > length - 1)

        return length - (n - l)

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int length = nums.size();
        sort(nums.begin(), nums.end());
        int n = 1;

        for (int i = 1; i < length; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[n] = nums[i];
                n++;
            }
        }

        int l = 0;
        for (int r = 0; r < n; r++) {
            if (nums[r] - nums[l] > length - 1) {
                l++;
            }
        }

        return length - (n - l);
    }
};