Minimum Number of Operations to Make Array Continuous - Solution & Explanation
Problem Statement
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
Approach Overview
Problem Overview: You are given an integer array and can replace any element with any integer. The goal is to make the array continuous: all elements must be unique and the difference between the maximum and minimum values must be n - 1. The task is to compute the minimum number of replacements required.
Approach 1: Sort + Sliding Window (O(n log n) time, O(n) space)
The key observation: a valid continuous array of length n must fit inside a value range [x, x + n - 1]. First remove duplicates by converting the array into a sorted unique list. Then use a sliding window over this sorted list. For each left index l, expand the right pointer r while nums[r] - nums[l] <= n - 1. This window represents values that can already fit inside a valid continuous range without replacement. The number of elements you keep is the window size, so the number of operations needed is n - window_size. Track the maximum window size across the array. Sorting costs O(n log n), and the two-pointer scan is linear.
This approach works because the best strategy is always to preserve the largest set of numbers that already fit within a valid continuous interval. The array is sorted once, and the window ensures you never revisit elements.
Approach 2: Binary Search with a Set (O(n log n) time, O(n) space)
Another way to think about the problem is to treat each number as a possible start of a continuous range. Insert all values into a hash table or set to remove duplicates, then sort the unique values. For every index i, compute the maximum allowed value nums[i] + n - 1. Use binary search to find the rightmost index whose value fits within this limit. The count of valid elements is right - i + 1, and the required operations become n - count. Iterate over all starting points and keep the minimum.
This approach explicitly searches the farthest element that still fits inside the allowed range. The complexity stays O(n log n) due to sorting and repeated binary searches.
Recommended for interviews: The Sort + Sliding Window approach is the one most interviewers expect. It shows you recognize the continuous-range constraint and can convert the problem into a two-pointer window over sorted unique values. Mentioning the binary search variant demonstrates deeper understanding of range queries, but the sliding window solution is usually cleaner and easier to implement under time pressure.
Approach 1: Sort and Sliding Window
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:
- Sort the array to easily determine the valid range.
- Use a two-pointer sliding window approach to maintain unique elements within a feasible range of size
nums.length - 1. - The minimal number of elements to be replaced will be equal to the original array size minus the maximal length of this window.
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.
Complexity
Time Complexity: O(N log N) due to sorting. Space Complexity: O(N) for the extra space used by the set and sorted list.
Approach 2: Binary Search with a Set
This approach optimally uses binary search for potentially faster window limits:
- Sort and deduplicate the array.
- Use binary search to maintain the longest subarray fulfilling the difference constraint.
- Calculate necessary operations from this subarray size.
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.
Code
JavaScript
Java
Complexity
Time Complexity: O(N log N) due to sorting. Space Complexity: O(N) for data storage.
Approach 3: Sorting + Deduplication + Binary Search
First, we sort the array and remove duplicates.
Then, we traverse the array, enumerating the current element nums[i] as the minimum value of the consecutive array. We use binary search to find the first position j that is greater than nums[i] + n - 1. Then, j-i is the length of the consecutive array when the current element is the minimum value. We update the answer, i.e., ans = min(ans, n - (j - i)).
Finally, we return ans.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array.
Approach 4: Sorting + Deduplication + Two Pointers
Similar to Solution 1, we first sort the array and remove duplicates.
Then, we traverse the array, enumerating the current element nums[i] as the minimum value of the consecutive array. We use two pointers to find the first position j that is greater than nums[i] + n - 1. Then, j-i is the length of the consecutive array when the current element is the minimum value. We update the answer, i.e., ans = min(ans, n - (j - i)).
Finally, we return ans.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array.
Complexity Comparison
| 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. |
| Sorting + Deduplication + Binary Search | — |
| Sorting + Deduplication + Two Pointers | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort + Sliding Window | O(n log n) | O(n) | Best general solution; clean two-pointer logic after sorting unique values |
| Binary Search with Set | O(n log n) | O(n) | Useful when framing the problem as repeated range queries on a sorted array |
Video Solution
Minimum Number of Operations to Make Array Continuous - Leetcode 2009 - Python • NeetCodeIO • 21,607 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Number of Operations to Make Array Continuous easy or hard?
Minimum Number of Operations to Make Array Continuous Python/Java solution
How to solve Minimum Number of Operations to Make Array Continuous in O(n)?
What is the best approach for Minimum Number of Operations to Make Array Continuous?
Is Minimum Number of Operations to Make Array Continuous asked at Google/Amazon/Meta?
What data structure is used in Minimum Number of Operations to Make Array Continuous?
What is the time complexity of Minimum Number of Operations to Make Array Continuous?
Ready to solve this problem?
Practice Minimum Number of Operations to Make Array Continuous with our built-in code editor and test cases.
Practice on FleetCode