2009. Minimum Number of Operations to Make Array Continuous LeetCode Solution

In this guide, you will get 2009. Minimum Number of Operations to Make Array Continuous LeetCode Solution with the best time and space complexity. The solution to Minimum Number of Operations to Make Array Continuous problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Minimum Number of Operations to Make Array Continuous solution in C++
  4. Minimum Number of Operations to Make Array Continuous solution in Java
  5. Minimum Number of Operations to Make Array Continuous solution in Python
  6. Additional Resources
2009. Minimum Number of Operations to Make Array Continuous LeetCode Solution image

Problem Statement of Minimum Number of Operations to Make Array Continuous

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.

See also  1575. Count All Possible Routes LeetCode Solution

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

Complexity Analysis

  • Time Complexity: O(\texttt{sort})
  • Space Complexity: O(n)

2009. Minimum Number of Operations to Make Array Continuous LeetCode Solution in C++

class Solution {
 public:
  int minOperations(vector<int>& 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<int>& arr, int target) {
    return ranges::upper_bound(arr, target) - arr.begin();
  }
};
/* code provided by PROGIEZ */

2009. Minimum Number of Operations to Make Array Continuous LeetCode Solution in Java

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[] arr, int target) {
    final int i = Arrays.binarySearch(arr, target + 1);
    return i < 0 ? -i - 1 : i;
  }
}
// code provided by PROGIEZ

2009. Minimum Number of Operations to Make Array Continuous LeetCode Solution in Python

class Solution:
  def minOperations(self, nums: list[int]) -> int:
    n = len(nums)
    ans = n
    nums = sorted(set(nums))

    for i, start in enumerate(nums):
      end = start + n - 1
      index = bisect_right(nums, end)
      uniqueLength = index - i
      ans = min(ans, n - uniqueLength)

    return ans
# code by PROGIEZ

Additional Resources

See also  1631. Path With Minimum Effort LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.