2119. Minimum Number of Operations to Make Array Continuous

Hard

---

Solution

First, remove duplications and sort, and let this sortedDistinct Note that the duplicated numbers must be replaced.

Let e the element from sortedDistinct. Consider an interval [e, e + nums.size - 1]. Then any element in sortedDistinct is correctly placed if it's in the interval. Otherwise, it must be replaced.

Using binary search, find the index of e + nums.size - 1. Then we can calculate the number of the elements in sortedDistinct which are also in [e, e + nums.size - 1], using indices of e and e + nums.size - 1. The number of elements that must be replaced is subtraction from nums.size.

Do this to all the elements in sortedDistinct.

Time: O(n log n) Space: O(n). Using in-place sort, O(1)

---

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 nums are unique.
• The difference between the maximum element and the minimum element in 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 <= 105
• 1 <= nums[i] <= 109