Minimum Operations to Make Array Continuous

Share

Find minimum operations to make array continuous (all distinct, max-min = n-1).

Example 1
Input: nums=[4,2,5,3] → Output: 0
Example 2
Input: nums=[1,2,3,5,6] → Output: 1
Example 3
Input: nums=[1,10,100,1000] → Output: 3

Solution Approach

Sort and deduplicate. Use sliding window to find max elements that can be kept in window [x, x+n-1].

  • Sort and remove duplicates
  • For each unique value as window start x: window = [x, x+n-1]
  • Binary search or two-pointer to count elements in window
  • Operations = n - count (replace elements outside window)
  • Return minimum operations
Java
public int minOperations(int[] nums) {
    int n = nums.length;
    Arrays.sort(nums);
    int[] unique = Arrays.stream(nums).distinct().toArray();
    int m = unique.length, max = 0;
    int j = 0;
    for (int i = 0; i < m; i++) {
        while (j < m && unique[j] < unique[i] + n) j++;
        max = Math.max(max, j - i);
    }
    return n - max;
}
  • Time Complexity: O(n log n)
  • Space Complexity: O(n)