Minimum Number of Operations to Make Array Continuous
You are given an integer array nums. In one operation, you can replace any element of nums with any value. nums is called continuous if, after sorting, each pair of adjacent elements differs by exactly 1 and all elements are distinct . Return the minimum number of operations needed to make nums continuous. A continuous array of length n is really just n consecutive distinct integers — so the question becomes: how many of the existing values can we keep, and treat everything else as replaceable? First deduplicate and sort the values, since duplicates can never both survive and out-of-order values do not affect which ones fit a window. Then slide a window over these unique sorted values , where a window is valid if its span is less than n (it could all fit inside some length-n block of consecutive integers). The largest such window is the most values you get to keep — everything outside it must be replaced.
Constraints
- 1 ≤ nums.length ≤ 105
- 1 ≤ numsi ≤ 109
Example
nums = [1, 2, 3, 5, 6]1Explanation Replace 5 with 4: nums becomes [1, 2, 3, 4, 6], still not continuous, but replacing 1 with 4 instead gives [4, 2, 3, 5, 6] which sorts to [2, 3, 4, 5, 6] — continuous with a single change.
In plain terms
- Continuous array
- An array whose values, once sorted, form an unbroken run like 4, 5, 6, 7 — no gaps, no repeats.
The row is the unique sorted values, with a window sliding over them
n=5. Unique sorted values: [1, 2, 3, 5, 6]. left=0 (value1): limit = 1 + 5 - 1 = 5. The window starts on the first value and grows while values stay <= 5.
What happens in this step
n = 5, unique = [1, 2, 3, 5, 6] left = 0 (value 1), limit = 1 + n - 1 = 5 Values 1, 2, 3, 5 are all <= 5; 6 is not — right stops at index 4 (value 6, excluded).
Steps to visualize
- The row below is the unique sorted values. It never changes; only the window over it moves.
- The highlight box covers the values being kept. In the code, the variable right sits one place past the last kept value, so the box ends one cell before it.
- Deduplicate and sort nums into a list of unique values.
- For each left position, compute the largest value still allowed in an n-length consecutive block: uniqueleft + n - 1.
- Grow right as far as possible while uniqueright stays within that limit — everything from left to right can be kept as-is.
- Track the largest such window across every left position.
- The answer is n minus that largest window: everything outside the best-kept window must be replaced.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
n=5. Unique sorted values: [1, 2, 3, 5, 6]. left=0 (value1): limit = 1 + 5 - 1 = 5. The window starts on the first value and grows while values stay <= 5.
What happens in this step
n = 5, unique = [1, 2, 3, 5, 6] left = 0 (value 1), limit = 1 + n - 1 = 5 Values 1, 2, 3, 5 are all <= 5; 6 is not — right stops at index 4 (value 6, excluded).
Solution
function minOperations(nums) {
const n = nums.length;
const unique = Array.from(new Set(nums)).sort((a, b) => a - b);
let best = 0;
let right = 0;
for (let left = 0; left < unique.length; left++) {
const limit = unique[left] + n - 1;
while (right < unique.length && unique[right] <= limit) {
right++;
}
best = Math.max(best, right - left);
}
return n - best;
}- Time
- O(n log n)
- Space
- O(n)
Test cases
| Input | Expected | Covers |
|---|---|---|
nums = [1, 2, 3, 5, 6] | 1 | example from the docstring |
nums = [1] | 0 | smallest valid input: a single element is already continuous |
nums = [4, 2, 5, 3] | 0 | already-continuous values in unsorted order need no changes |
nums = [1, 1, 1, 1] | 3 | all-duplicate values must become four distinct consecutive numbers |
nums = [1, 10, 100, 1000] | 3 | widely spread values where only one can be kept |
nums = [1, 2, 2, 3, 8] | 2 | a duplicate mixed with an outlier that both must be replaced |