LC-2009 Hard LeetCode

2009. Minimum Number of Operations to Make Array Continuous

Array Hash Table Binary Search Sliding Window

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 52% Topics: Array, Hash Table, Binary Search, Sliding Window

Reading material

Arrays & Hashing 12 min Binary Search 12 min Sliding Window 11 min

Reference solution (spoiler · python)

# Time:  O(nlogn)
# Space: O(1)

class Solution(object):
    def minOperations(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def unique(nums):
            left = 0
            for right in xrange(1, len(nums)):
                if nums[left] != nums[right]:
                    left += 1
                    nums[left] = nums[right]
            return left

        def erase(nums, i):
            while len(nums) > i+1:
                nums.pop()

        n = len(nums)
        nums.sort()
        erase(nums, unique(nums))
        result = l = 0
        for i in xrange(len(nums)):
            if nums[i] <= nums[i-l]+n-1:
                l += 1
        return n-l


# Time:  O(nlogn)
# Space: O(n)
class Solution2(object):
    def minOperations(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        nums = sorted(set(nums))
        result = right = 0
        for left in xrange(len(nums)):
            while right < len(nums) and nums[right] <= nums[left]+n-1:
                right += 1
            result = max(result, right-left)
        return n-result

Solution from kamyu104/LeetCode-Solutions · MIT