2009. Minimum Number of Operations to Make Array Continuous
Approach
Sort + deduplicate; sliding window of size n; minimize elements outside window to replace.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Binary search reduces search space by half each step, giving O(log n) time. Beyond sorted arrays, apply it on the answer space ("binary search on result") when you can define a monotonic predicate — e.g., "can we achieve X with k resources?"
The sliding window technique maintains a dynamic sub-array (or substring) of interest, expanding the right boundary and shrinking the left boundary based on a constraint. It reduces O(n²) substring enumeration to O(n). Track state (frequency map, sum, distinct count) incrementally.
// Approach: Sort + deduplicate; sliding window of size n; minimize elements outside window to replace.
// Time: O(n log n) Space: O(n)
public class Solution
{
public int MinOperations(int[] nums)
{
int n = nums.Length;
int ans = n;
Array.Sort(nums);
nums = nums.Distinct().ToArray();
for (int i = 0; i < nums.Length; ++i)
{
int start = nums[i];
int end = start + n - 1;
int index = FirstGreater(nums, end);
int uniqueLength = index - i;
ans = Math.Min(ans, n - uniqueLength);
}
return ans;
}
private int FirstGreater(int[] A, int target)
{
int i = Array.BinarySearch(A, target + 1);
return i < 0 ? ~i : i;
}
}