Minimum Number of Operations to Make Array Continuous

Hard
971.

Minimum Number of Operations to Make Array Continuous

Minimum Number of Operations to Make Array Continuous is a hard coding problem on arrays, hash table and binary search, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var minOperations = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of Operations to Make Array Continuous Solution

Minimum Number of Operations to Make Array Continuous solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Number of Operations to Make Array Continuous is a hard coding problem on arrays, hash table and binary search, asked in Amazon, Google and Microsoft interviews.

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

Hints for Minimum Number of Operations to Make Array Continuous

  1. Hint 1

    The final array occupies some window of n consecutive integers.

  2. Hint 2

    Elements already inside that window can be kept; everything else must be rewritten.

  3. Hint 3

    So maximise the number of distinct values falling inside any window of width n - 1.

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

  1. De-duplicate and sort the values.
  2. Slide a window whose right end is each value in turn, advancing the left end while the span exceeds n - 1.
  3. Track the largest window size.
  4. 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

Java

public static int minOperations(int[] nums) {
    int n = nums.length;
    int[] sorted = nums.clone();
    Arrays.sort(sorted);
    int[] seen = new int[n];
    int m = 0;
    for (int i = 0; i < n; i++) {
        if (i > 0 && sorted[i] == sorted[i - 1]) continue;
        seen[m++] = sorted[i];
    }
    int best = 0, j = 0;
    for (int i = 0; i < m; i++) {
        while (seen[i] - seen[j] > n - 1) j++;
        best = Math.max(best, i - j + 1);
    }
    return n - best;
}

C++

int minOperations(vector<int>& nums) {
    int n = (int) nums.size();
    vector<int> seen = nums;
    sort(seen.begin(), seen.end());
    seen.erase(unique(seen.begin(), seen.end()), seen.end());
    int best = 0, j = 0;
    for (int i = 0; i < (int) seen.size(); i++) {
        while (seen[i] - seen[j] > n - 1) j++;
        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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets