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

1
2
3

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

Example 2

1
2
3
4

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

1
2
3
4
5
6
7

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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.