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
numsare unique. - The difference between the maximum element and the minimum element in
numsequalsnums.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 <= 1051 <= nums[i] <= 109
Companies: Amazon, Apple, Uber
Related Topics:
Array, Binary Search
Similar Questions:
- Longest Repeating Character Replacement (Medium)
- Continuous Subarray Sum (Medium)
- Moving Stones Until Consecutive II (Medium)
- Minimum One Bit Operations to Make Integers Zero (Hard)
- Minimum Adjacent Swaps for K Consecutive Ones (Hard)
Hints:
- Sort the array.
- For every index do a binary search to get the possible right end of the window and calculate the possible answer.
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/
// Author: github.com/lzl124631x
// 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/
// Author: github.com/lzl124631x
// 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/
// Author: github.com/lzl124631x
// 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;
}
};