Formatted question description: https://leetcode.ca/all/2009.html

2009. Minimum Number of Operations to Make Array Continuous (Hard)

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 the minimum number of operations to make nums continuous.

 

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 <= 105
  • 1 <= nums[i] <= 109

Similar Questions:

Solution 1. Sliding Window

Check out “C++ Maximum Sliding Window Cheatsheet Template!”.

Intuition: Sort and only keep unique elements. The problem is the same as “get the length of the longest subarray whose difference between min and max elements is N - 1”.

Algorithm:

The brute force way is to pick each A[i] as the start of the subarray and count the number of elements that are <= A[i] + N - 1, which takes O(N^2) time.

Since the array is already sorted, we can use sliding window so that we only traverse the entire array once.

// OJ: https://leetcode.com/problems/minimum-number-of-operations-to-make-array-continuous/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int minOperations(vector<int>& A) {
        int N = A.size(), ans = N, j = 0;
        sort(begin(A), end(A));
        A.erase(unique(begin(A), end(A)), end(A)); // only keep unique elements
        int M = A.size();
        for (int i = 0; i < M; ++i) {
            while (j < M && A[j] < A[i] + N) ++j; // let `j` point to the first element that is out of range -- `>= A[i] + N`.
            ans = min(ans, N - j + i); // The length of this subarray is `j - i`. We need to replace `N - j + i` elements to make it continuous.
        }
        return ans;
    }
};

Use Shrinkable Sliding Window Template:

// OJ: https://leetcode.com/problems/minimum-number-of-operations-to-make-array-continuous/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int minOperations(vector<int>& A) {
        int N = A.size(), i = 0, j = 0, ans = 0;
        sort(begin(A), end(A));
        A.erase(unique(begin(A), end(A)), end(A)); // only keep unique elements
        for (int M = A.size(); j < M; ++j) {
            while (A[i] + N <= A[j]) ++i; // let `i` point to the first element that is in range -- `A[i] + N > A[j]`
            ans = max(ans, j - i + 1);
        }
        return N - ans;
    }
};

Use Non-shrinkable Sliding Window Template:

// OJ: https://leetcode.com/problems/minimum-number-of-operations-to-make-array-continuous/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int minOperations(vector<int>& A) {
        int N = A.size(), i = 0, j = 0;
        sort(begin(A), end(A));
        A.erase(unique(begin(A), end(A)), end(A)); // only keep unique elements
        for (int M = A.size(); j < M; ++j) {
            if (A[i] + N <= A[j]) ++i;
        }
        return N - j + i;
    }
};

Discuss

https://leetcode.com/problems/minimum-number-of-operations-to-make-array-continuous/discuss/1470857/C%2B%2B-Sliding-Window

All Problems

All Solutions