Minimum Number of Operations to Make Array Continuous — Hard Problem & Solution

An array is continuous when all its elements are different and the gap between its largest and smallest element is exactly nums.length - 1.

Difficulty: Hard
Topics: Arrays, Hash Table, Binary Search, Sliding Window
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

An array is continuous when all its elements are different and the gap between its largest and smallest element is exactly nums.length - 1.

In one operation you may replace any element with any integer. Return the minimum number of operations that makes nums continuous.

Example 1

Input: nums = [4,2,5,3]
Output: 0
Explanation: Already continuous.

Example 2

Input: nums = [1,2,3,5,6]
Output: 1
Explanation: Change the 1 to a 4, giving `[4,2,3,5,6]`.

Example 3

Input: nums = [1,10,100,1000]
Output: 3
Explanation: Only one element can be kept.

Constraints

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9

How to solve Minimum Number of Operations to Make Array Continuous

Turn it around: count what can be kept. The result spans n consecutive integers, so keep the distinct values lying inside some window [x, x + n - 1] and rewrite the rest. Maximise the kept count with a sliding window over the sorted distinct values.

Approach

De-duplicate and sort the values.
Slide a window whose right end is each value in turn, advancing the left end while the span exceeds n - 1.
Track the largest window size.
The answer is n - largest.

Why it works

Duplicates must be removed first, because a repeated value can only ever be kept once — counting it twice would over-estimate what survives. The window is anchored on actual values rather than scanned over the 10^9 range, which is what keeps the sweep linear after the sort.

Complexity

Time — O(n log n)
Space — O(n)

Pitfalls

Forgetting to de-duplicate inflates the keep count.
The window spans n - 1, not n — it holds n integers inclusive.
The answer counts rewrites, so it is n minus the best keep count.

Reference solution

Python

from typing import List

def minOperations(nums: List[int]) -> int:
    n = len(nums)
    seen = sorted(set(nums))
    best = 0
    j = 0
    for i in range(len(seen)):
        while seen[i] - seen[j] > n - 1:
            j += 1
        best = max(best, i - j + 1)
    return n - best

JavaScript

var minOperations = function(nums) {
    var n = nums.length, i;
    var mark = {};
    var seen = [];
    for (i = 0; i < nums.length; i++) {
        var key = "" + nums[i];
        if (mark[key]) continue;
        mark[key] = true;
        seen.push(nums[i]);
    }
    seen.sort(function(a, b) { return a - b; });
    var best = 0, j = 0;
    for (i = 0; i < seen.length; i++) {
        while (seen[i] - seen[j] > n - 1) j++;
        var cnt = i - j + 1;
        if (cnt > best) best = cnt;
    }
    return n - best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue