Minimum Number Of Operations To Make Array Continuous - Leetcode Solution

Problem Description:

You are given an integer array nums that may not contain all numbers from 0 to n - 1 (where n is the length of nums). In addition, you have an uninterrupted sequence [0, 1, 2, ..., n - 1] of integers.

Return the minimum number of operations needed to make nums continuous. To make nums continuous, you can insert any missing elements and move any elements within the array.

Example 1:

Input: nums = [1,2,4,5,7,8,9] Output: 2 Explanation: The optimal solution is to insert 3 and 6 in the array to form [1,2,3,4,5,6,7,8,9].

Example 2:

Input: nums = [4,2,3,5,6] Output: 0 Explanation: nums already takes the form [2,3,4,5,6]. No elements need to be inserted.

Solution:

To make the given array continuous, we need to first sort the array and then count the maximum number of contiguous subarrays of length (n-i) where i is the index of the first element of the subarray. We can then return the total number of elements minus the maximum number of contiguous subarrays.

For example, let's consider the given array nums=[1,2,4,5,7,8,9]. After sorting, the array becomes nums=[1,2,4,5,7,8,9]. Now, we can create subarrays of length (n-i) where n is the length of the array and i is the index of the first element of the subarray. Here, we can create subarrays of length 7 starting from index 0, subarrays of length 6 starting from index 1, and so on. The maximum number of contiguous subarrays is 4 which can be created from the subarrays [1,2,4,5,7,8,9], [2,4,5,7,8,9], [4,5,7,8,9], and [5,7,8,9]. Therefore, the solution is 7-4=3.

Here is the Python code for the given problem:

def minOperations(nums):
    n = len(nums)
    nums.sort()
    cnt = 1
    max_cnt = 0
    for i in range(1, n):
        if nums[i] - nums[i-1] == 1:
            cnt += 1
        elif nums[i] == nums[i-1]:
            continue
        else:
            max_cnt = max(max_cnt, cnt)
            cnt = 1
    max_cnt = max(max_cnt, cnt)
    return n - max_cnt

print(minOperations([1,2,4,5,7,8,9])) # Output: 2
print(minOperations([4,2,3,5,6])) # Output: 0

1