Minimum Number of Operations to Make Array Continuous solution in C++

Problem Description

Ah, the classic dilemma of making an array continuous! It’s like trying to convince your friends to stop being so “unique” and just get along. The problem is simple yet profound: given an array of integers, you need to determine the minimum number of operations required to make the array continuous.

Imagine you have a group of friends who all have different hobbies. You want them to form a continuous line of activities, but some of them are just too quirky. You can only remove some of them to achieve this continuous line. The goal is to figure out how many friends (or numbers) you need to kick out to make the rest of them form a nice, neat line.

Code Solution

Copy Code

class Solution {
 public:
  int minOperations(vector& nums) {
    const int n = nums.size();
    int ans = n;

    ranges::sort(nums);
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

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

    return ans;
  }

 private:
  int firstGreater(const vector& A, int target) {
    return ranges::upper_bound(A, target) - A.begin();
  }
};
    

Approach

The approach taken in this solution is quite elegant. First, we sort the array and remove duplicates. Then, for each unique number, we determine the range of numbers that can form a continuous sequence starting from that number. By calculating how many numbers fall within this range, we can easily find out how many need to be removed to achieve continuity. The minimum number of removals across all unique numbers gives us the answer.

Time and Space Complexity

Time Complexity: O(n log n) due to sorting the array, where n is the number of elements in the array.

Space Complexity: O(n) for storing the unique elements after removing duplicates.

Real-World Example

Let’s say you’re organizing a marathon, and you have a list of participants with their bib numbers. However, some participants have unique bib numbers that don’t fit into a continuous range. To make the race smoother, you need to figure out how many participants you can keep while ensuring their bib numbers form a continuous sequence. This problem is essentially the same as the one we just solved!