We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Operations to Make Array Continuous

Number: 2119

Difficulty: Hard

Paid? No

Companies: Uber, Google, Adobe

Problem Description

Given an integer array nums, you can perform operations in which you replace any element with any integer. An array is considered continuous if the following two conditions hold:

  1. All elements are unique.
  2. The difference between the maximum and minimum elements equals nums.length - 1.

Return the minimum number of operations required to make nums continuous.

Key Insights

  • First, extract the unique elements from nums and sort them.
  • Use a sliding window technique on the sorted unique array to find the largest block of numbers that can potentially be part of a continuous sequence.
  • The valid window is one where the difference between the maximum and the minimum in the window is at most n - 1 (n is the original length).
  • The number of operations equals n (total numbers) minus the size of the largest window.
  • There is one special case: if the window size is n - 1 and the range of the window is exactly n - 2, then it is impossible to fill the gap with a single operation; the answer in this scenario becomes 2.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing the unique elements.

Solution

The solution works by first converting the array into a sorted list of its unique elements. Then it uses a two-pointer (sliding window) technique to determine the maximum number of unique values that form almost a continuous sequence (i.e. the difference between the window’s maximum and minimum is at most n - 1). The minimum operations needed is computed as n minus the size of this window. A special edge case is handled where the window size equals n - 1 and its range is exactly n - 2; in that situation, one extra move is required, resulting in an answer of 2 rather than n - (n - 1).

This approach uses sorting (to enable binary-like sliding window) along with simple arithmetic conditions to decide when a window is valid. The sliding-window algorithm ensures that we check intervals in linear time after the sort.

Code Solutions

# Python solution for Minimum Number of Operations to Make Array Continuous

class Solution:
    def minOperations(self, nums: list[int]) -> int:
        n = len(nums)
        # Extract unique values and sort them.
        unique_nums = sorted(set(nums))
        m = len(unique_nums)
        ans = n  # Initialize with the maximum possible operations.
        j = 0  # End pointer for the sliding window.
        # Iterate through the unique list with i as the window start.
        for i in range(m):
            # Expand j while the window's range is at most n - 1.
            while j < m and unique_nums[j] - unique_nums[i] <= n - 1:
                j += 1
            # The current number of elements in the window.
            current_window_size = j - i
            # Special case: if window has n - 1 numbers and the range is exactly n - 2, then 1 move is not enough.
            if current_window_size == n - 1 and unique_nums[j - 1] - unique_nums[i] == n - 2:
                operations = 2
            else:
                operations = n - current_window_size
            ans = min(ans, operations)
        return ans

# Example usage:
# sol = Solution()
# print(sol.minOperations([1,2,3,5,6]))  # Expected output: 1
← Back to All Questions