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.
1import java.util.*;
2
3
This Java solution first constructs a deduplicated sorted list and utilizes binary search to determine the longest valid subarray within constraints, minimizing transformation operations needed.