Minimum Number of Operations to Make Array Continuous

hard array binary search

Problem

You are given an integer array nums. In one operation you may replace any element with any integer. The array is continuous when its sorted form contains n consecutive integers with no duplicates. Return the minimum operations required.

Inputnums = [1, 2, 3, 5, 6]

Output1

Keep {1,2,3} or {5,6} — best window of length 5 over the unique sorted values covers 4 of them, so 5 − 4 = 1.

nums (comma-separated)

def min_operations(nums):
    n = len(nums)
    uniq = sorted(set(nums))
    best = 0
    j = 0
    for i, lo in enumerate(uniq):
        hi = lo + n - 1
        while j < len(uniq) and uniq[j] <= hi:
            j += 1
        best = max(best, j - i)
    return n - best

function minOperations(nums) {
  const n = nums.length;
  const uniq = [...new Set(nums)].sort((a, b) => a - b);
  let best = 0, j = 0;
  for (let i = 0; i < uniq.length; i++) {
    const hi = uniq[i] + n - 1;
    while (j < uniq.length && uniq[j] <= hi) j++;
    best = Math.max(best, j - i);
  }
  return n - best;
}

class Solution {
    public int minOperations(int[] nums) {
        int n = nums.length;
        int[] uniq = java.util.Arrays.stream(nums).distinct().sorted().toArray();
        int best = 0, j = 0;
        for (int i = 0; i < uniq.length; i++) {
            long hi = (long) uniq[i] + n - 1;
            while (j < uniq.length && uniq[j] <= hi) j++;
            best = Math.max(best, j - i);
        }
        return n - best;
    }
}

int minOperations(vector<int>& nums) {
    int n = nums.size();
    vector<int> uniq(nums.begin(), nums.end());
    sort(uniq.begin(), uniq.end());
    uniq.erase(unique(uniq.begin(), uniq.end()), uniq.end());
    int best = 0, j = 0;
    for (int i = 0; i < (int)uniq.size(); i++) {
        long long hi = (long long)uniq[i] + n - 1;
        while (j < (int)uniq.size() && uniq[j] <= hi) j++;
        best = max(best, j - i);
    }
    return n - best;
}

Explanation

A continuous array of length n is just n consecutive integers with no duplicates. We can replace any element with anything, so the real question is: how many original values can we keep? Whatever we keep, the rest get replaced, so we want to maximize the keepers.

First sort and dedupe the values (duplicates can never both survive in a continuous array). The final array spans some window of values [a, a + n - 1]. Any unique value already inside that window can stay; everything else must be replaced.

We slide a two-pointer window over the unique values. For each left value uniq[i], the window upper bound is uniq[i] + n - 1; we advance j while uniq[j] stays within it. The count of values inside is j - i, and we track the best.

The answer is n - best: the elements we could not keep are exactly the ones we replace.

Example: nums = [1,2,3,5,6], n = 5. The window starting at 1 covers [1,5] and keeps 1,2,3,5 (4 values). So the answer is 5 - 4 = 1.

Time: O(n log n) Space: O(n)