Sponsored
Sponsored
This approach involves sorting the array and then using a sliding window technique to identify the minimal range that can lead to a continuous array by transformation.
Steps:
nums.length - 1.Time Complexity: O(N log N) due to sorting. Space Complexity: O(N) for the extra space used by the set and sorted list.
1#include <bits/stdc++.h>
2using namespace std;
3
4int minOperations(vector<int>& nums) {
5 set<int> unique_nums(nums.begin(), nums.end());
6 vector<int> sorted_nums(unique_nums.begin(), unique_nums.end());
7 int n = nums.size();
8 int max_valid_count = 0;
9 for (int i = 0, j = 0; j < sorted_nums.size(); ++j) {
10 while (sorted_nums[j] - sorted_nums[i] >= n) {
11 ++i;
12 }
13 max_valid_count = max(max_valid_count, j - i + 1);
14 }
15 return n - max_valid_count;
16}
17
18// Example usage
19int main() {
20 vector<int> nums1 = {4, 2, 5, 3};
21 vector<int> nums2 = {1, 2, 3, 5, 6};
22 vector<int> nums3 = {1, 10, 100, 1000};
23 cout << minOperations(nums1) << endl; // Output: 0
24 cout << minOperations(nums2) << endl; // Output: 1
25 cout << minOperations(nums3) << endl; // Output: 3
26 return 0;
27}This C++ solution uses a set to remove duplicates and sort the numbers. A sliding window is then applied to find the maximum subrange that meets the condition, with the calculation requiring the difference in counts to determine operations.
This approach optimally uses binary search for potentially faster window limits:
Time Complexity: O(N log N) due to sorting. Space Complexity: O(N) for data storage.
1function minOperations(nums) {
2 nums =
The JavaScript implementation leverages a set to deduplicate and sort the list, utilizing a loop to find the longest subarray where limits sustain the validity. Binary search simplifies range checks.