2009. Minimum Number of Operations to Make Array Continuous - Explanation

1. Brute Force

Intuition

An array is continuous if it contains n unique elements where the difference between the maximum and minimum is exactly n - 1. This means a valid continuous array is just a range of consecutive integers. We can replace any element with any value, so the goal is to keep as many original elements as possible and replace the rest.

For each unique element, we treat it as the potential minimum of our final array. Then we count how many other unique elements fall within the valid range (from that minimum to minimum + n - 1). The elements outside this range need to be replaced.

Algorithm

Remove duplicates from the array and sort the unique elements.
For each unique element at index i, treat it as the minimum of the target range.
Count how many elements fall within the range [nums[i], nums[i] + n - 1].
The number of operations needed is n - count (total elements minus those already in range).
Return the min operations across all starting positions.

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        N = len(nums)
        res = float("inf")
        nums = sorted(set(nums))
        n = len(nums)

        for i in range(n):
            noChange = 1
            for j in range(i + 1, n):
                if nums[i] < nums[j] < nums[i] + N:
                    noChange += 1
            res = min(res, N - noChange)

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Binary Search

Intuition

Instead of using a nested loop to count elements in range, we can use binary search. Once the array is sorted, for each starting element, we binary search for the first element that exceeds the valid range. The number of valid elements is the difference between the found position and the starting index.

Algorithm

Remove duplicates and sort the unique elements.
For each unique element at index i, use binary search to find the first position l where nums[l] >= nums[i] + n.
The count of elements in range is l - i.
Track the min value of n - count across all positions.
Return the minimum operations found.

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        N = len(nums)
        res = float("inf")
        nums = sorted(set(nums))
        n = len(nums)

        for i in range(n):
            l, r = i, n
            while l < r:
                mid = (l + r) // 2
                if nums[mid] < nums[i] + N:
                    l = mid + 1
                else:
                    r = mid
            noChange = l - i
            res = min(res, N - noChange)

        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

3. Sliding Window

Intuition

Since the sorted unique elements are in increasing order, we can use a sliding window instead of binary search. As the left pointer moves right, the right pointer only needs to move forward (never backward) because the valid range shifts up. This gives us an efficient two-pointer approach.

Algorithm

Remove duplicates and sort the unique elements.
Use two pointers l (left) and r (right) starting at 0.
For each left pointer position:
- Expand the right pointer while elements are within range [nums[l], nums[l] + n - 1].
- The window size r - l represents elements that can stay.
- Update the result as min(result, n - window).
Return the minimum operations.

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        length = len(nums)
        nums = sorted(set(nums))
        res = length
        r = 0

        for l in range(len(nums)):
            while r < len(nums) and nums[r] < nums[l] + length:
                r += 1
            window = r - l
            res = min(res, length - window)

        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

4. Sliding Window (Optimal)

Intuition

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.

Algorithm

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

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)

Time & Space Complexity

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

Common Pitfalls

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.