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
- A continuous array is exactly a set of
ndistinct consecutive integers. - Sort and deduplicate. Then find the longest window of distinct values satisfying
max - min <= n - 1. - Every value outside that window must be changed, so the answer is
n - (longest window length). - 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
> ninstead of> n - 1:ndistinct consecutive integers spann - 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.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner