Problem statement

https://leetcode.com/problems/minimum-number-of-operations-to-make-array-continuous/

Solution

Reformulate the problems: found the range [x, x + n - 1], such that we have maximum number of values from nums. This problem can be solved with use of binary indexed tree. The idea is to put all numbers in sparse binary indexed tree and then check for each range [num, num + n - 1]. Notice that we only need to check ranges which starts with some number from nums.

Complexity

It is O(n*log M), where n = len(nums) and M = 10**9 + 10**5 is the maximum value of number + n`.

Code

class BIT:
    def __init__(self, n):
        self.sums = defaultdict(int)
        self.n = n
    
    def update(self, i, delta):
        while i < self.n + 1:
            self.sums[i] += delta
            i += i & (-i)
    
    def query(self, i):
        res = 0
        while i > 0:
            res += self.sums[i]
            i -= i & (-i)
        return res

    def sum(self, i, j):
        return self.query(j) - self.query(i-1)

class Solution:
    def minOperations(self, nums):
        n, ans = len(nums), 0
        bit = BIT(10**9 + 10**5 + 10)
        for num in set(nums):
            bit.update(num, 1)

        for num in nums:
            ans = max(ans, bit.sum(num, num + n - 1))
        return n - ans

Solution 2

In fact we do not need bit, we can use binary search idea as well. Notice that if we sort all numbers, then all we need to find is number of values in range [x, x + n - 1], which can be done using binary search.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def minOperations(self, nums):
        sArray = sorted(set(nums))    
        cand = [(i, n + len(nums) - 1) for i, n in enumerate(sArray)]
        
        ans = float("inf")
        for i, high in cand:
            idx = bisect.bisect_left(sArray, high)
            if idx >= len(sArray) or sArray[idx] != high: idx -= 1
            ans = min(ans, len(nums) - idx + i - 1)
        return ans

If you have any questions, feel free to ask. If you like solution and explanations, please Upvote!