⚡Flashcard Drill➔
NeetCode #257LC-2009HardSliding Window
← Back to All Problems

#257 · #2009 · Minimum Number of Operations to Make Array Continuous(使数组连续的最少操作数)

📌 Problem Statement & Constraints

Given an integer array nums, you may increment or decrement elements arbitrarily. The array is continuous if all elements are distinct and the maximum minus the minimum equals n - 1. Return the minimum number of operations to make nums continuous. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^9.

💡 Core Algorithmic Approaches

  1. A continuous array is exactly a set of n distinct consecutive integers.
  2. Sort and deduplicate. Then find the longest window of distinct values satisfying max - min <= n - 1.
  3. Every value outside that window must be changed, so the answer is n - (longest window length).
  4. Deduplication is essential: duplicates cannot be part of a valid continuous array, and the window is over distinct values.

💻 Benchmark Python3 Implementation

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums)
        uniq = sorted(set(nums))       # dedupe first
        l = 0
        best = 0
        for r in range(len(uniq)):
            # the values in the window must fit in a span of n - 1
            while uniq[r] - uniq[l] > n - 1:
                l += 1
            best = max(best, r - l + 1)
        return n - best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): the sort dominates; the window scan is O(n).
💾 Space Complexity
O(n) for the deduplicated array.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting to deduplicate: duplicates would inflate the window length and produce an answer that is too small.
  • Using > n instead of > n - 1: n distinct consecutive integers span n - 1.
  • Sorting the original array and keeping duplicates: the window must be over distinct values.
  • Trying to make the array exactly [min, min+1, ...]: the target range can start anywhere, which is why the window slides.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems