Watch 10 video solutions for Minimum Number of Operations to Make Array Continuous, a hard level problem involving Array, Hash Table, Binary Search. This walkthrough by NeetCodeIO has 21,004 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 109Problem 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 | 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 |