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:
nums are unique.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 <= 1051 <= nums[i] <= 109This 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.This Python solution first creates a sorted and deduplicated list of nums. It uses two pointers to traverse the sorted list, maintaining the largest subarray where the elements fulfill the necessary range condition. The difference between the original size and this subarray's size gives the answer.
C++
Time Complexity: O(N log N) due to sorting. Space Complexity: O(N) for the extra space used by the set and sorted list.
This approach optimally uses binary search for potentially faster window limits:
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.
Java
Time Complexity: O(N log N) due to sorting. Space Complexity: O(N) for data storage.
| Approach | Complexity |
|---|---|
| Sort and Sliding Window | Time Complexity: O(N log N) due to sorting. Space Complexity: O(N) for the extra space used by the set and sorted list. |
| Binary Search with a Set | Time Complexity: O(N log N) due to sorting. Space Complexity: O(N) for data storage. |
Minimum Number of Operations to Make Array Continuous - Leetcode 2009 - Python • NeetCodeIO • 18,440 views views
Watch 9 more video solutions →Practice Minimum Number of Operations to Make Array Continuous with our built-in code editor and test cases.
Practice on FleetCode