Minimum Number of Operations to Make Array Continuous solution in Java

Problem Description

Imagine you’re at a party, and everyone is dancing in a line. But wait! Some people are out of sync, and you need to make them dance in a continuous sequence. How many people do you need to ask to leave the dance floor to achieve that?

In this problem, you’re given an array of integers, and your task is to determine the minimum number of operations required to make the array continuous. An operation consists of removing an element from the array. The goal is to ensure that the remaining elements can form a continuous sequence.

Approach

The solution involves sorting the array and removing duplicates to focus on unique values. For each unique starting point in the array, we calculate the end of the continuous sequence we want to form. Using binary search, we find how many unique elements fall within that range. The minimum number of elements to remove is then calculated based on the total number of elements minus the length of the unique sequence.

Code Solution


class Solution {
  public int minOperations(int[] nums) {
    final int n = nums.length;
    int ans = n;

    Arrays.sort(nums);
    nums = Arrays.stream(nums).distinct().toArray();

    for (int i = 0; i < nums.length; ++i) {
      final int start = nums[i];
      final int end = start + n - 1;
      final int index = firstGreater(nums, end);
      final int uniqueLength = index - i;
      ans = Math.min(ans, n - uniqueLength);
    }

    return ans;
  }

  private int firstGreater(int[] A, int target) {
    final int i = Arrays.binarySearch(A, target + 1);
    return i < 0 ? -i - 1 : i;
  }
}

Time and Space Complexity

Time Complexity: O(n log n) due to sorting and binary search operations.
Space Complexity: O(n) for storing the distinct elements.

Real-World Example

Imagine you’re organizing a marathon, and you have a list of participants with their bib numbers. However, some numbers are missing, and you need to ensure that the remaining participants have continuous bib numbers. You can’t just let anyone run with a random number, right? By determining how many participants need to be removed to achieve a continuous sequence, you can ensure a smooth and organized event.