problemhardalgorithmsleetcode-2009leetcode 2009leetcode2009

Minimum Number of Operations to Make Array Continuous

HardUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

You are given an integer array nums. In one operation, you can replace any element in nums with any integer.

nums is considered continuous if both of the following conditions are fulfilled:

  • All elements in nums are unique.
  • The difference between the maximum element and the minimum element in nums equals nums.length - 1.

For example, nums = [4, 2, 5, 3] is continuous , but nums = [1, 2, 3, 5, 6] is not continuous.

Return _theminimum number of operations to make _nums __continuous.

Examples

Example 1

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

Example 2

Input: nums = [1,2,3,5,6]
Output: 1
Explanation:  One possible solution is to change the last element to 4.
The resulting array is [1,2,3,5,4], which is continuous.

Example 3

Input: nums = [1,10,100,1000]
Output: 3
Explanation:  One possible solution is to:
- Change the second element to 2.
- Change the third element to 3.
- Change the fourth element to 4.
The resulting array is [1,2,3,4], which is continuous.

Constraints

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

Solution

Method 1 – Sliding Window on Unique Sorted Array

Intuition

We want the array to be a sequence of n unique consecutive numbers. After removing duplicates and sorting, use a sliding window to find the largest possible window of length n. The minimum number of operations is n minus the size of the largest such window.

Approach

  1. Remove duplicates from nums and sort the result.
  2. For each index, use binary search (or two pointers) to find the largest window [i, j] where sorted[j] - sorted[i] < n.
  3. The answer is n minus the size of the largest window.

Code

C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        nums.erase(unique(nums.begin(), nums.end()), nums.end());
        int ans = n, j = 0;
        for (int i = 0; i < nums.size(); ++i) {
            while (j < nums.size() && nums[j] - nums[i] < n) ++j;
            ans = min(ans, n - (j - i));
        }
        return ans;
    }
};
Go
import "sort"
func minOperations(nums []int) int {
    n := len(nums)
    sort.Ints(nums)
    uniq := []int{}
    for i, x := range nums {
        if i == 0 || x != nums[i-1] { uniq = append(uniq, x) }
    }
    ans, j := n, 0
    for i := 0; i < len(uniq); i++ {
        for j < len(uniq) && uniq[j]-uniq[i] < n { j++ }
        if n-(j-i) < ans { ans = n - (j - i) }
    }
    return ans
}
Java
import java.util.*;
class Solution {
    public int minOperations(int[] nums) {
        int n = nums.length;
        Set<Integer> set = new HashSet<>();
        for (int x : nums) set.add(x);
        int[] arr = set.stream().mapToInt(Integer::intValue).toArray();
        Arrays.sort(arr);
        int ans = n, j = 0;
        for (int i = 0; i < arr.length; ++i) {
            while (j < arr.length && arr[j] - arr[i] < n) ++j;
            ans = Math.min(ans, n - (j - i));
        }
        return ans;
    }
}
Kotlin
class Solution {
    fun minOperations(nums: IntArray): Int {
        val n = nums.size
        val arr = nums.toSet().sorted()
        var ans = n
        var j = 0
        for (i in arr.indices) {
            while (j < arr.size && arr[j] - arr[i] < n) j++
            ans = minOf(ans, n - (j - i))
        }
        return ans
    }
}
Python
class Solution:
    def minOperations(self, nums: list[int]) -> int:
        n = len(nums)
        arr = sorted(set(nums))
        ans = n
        j = 0
        for i in range(len(arr)):
            while j < len(arr) and arr[j] - arr[i] < n:
                j += 1
            ans = min(ans, n - (j - i))
        return ans
Rust
use std::collections::HashSet;
impl Solution {
    pub fn min_operations(nums: Vec<i32>) -> i32 {
        let n = nums.len() as i32;
        let mut arr: Vec<i32> = nums.into_iter().collect::<HashSet<_>>().into_iter().collect();
        arr.sort();
        let mut ans = n;
        let mut j = 0;
        for i in 0..arr.len() {
            while j < arr.len() && arr[j] - arr[i] < n { j += 1; }
            ans = ans.min(n - (j as i32 - i as i32));
        }
        ans
    }
}
TypeScript
class Solution {
    minOperations(nums: number[]): number {
        const n = nums.length;
        const arr = Array.from(new Set(nums)).sort((a, b) => a - b);
        let ans = n, j = 0;
        for (let i = 0; i < arr.length; ++i) {
            while (j < arr.length && arr[j] - arr[i] < n) ++j;
            ans = Math.min(ans, n - (j - i));
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n) — n = length of nums, for sorting.
  • 🧺 Space complexity: O(n) — for unique array.

Comments