Problem statement

https://leetcode.com/problems/patching-array/

Solution 1

Let as keep all possible numbers we can get as list of intervals, for example 0, 1, 2, 4, 5, 12 is [[0, 2], [4, 5], [12, 12]]. Then when we add new number we can merge our intervals, using idea of Problem 0056. What numbers we need to add next? We need to add number 3 in our example, the smallest possible number, which are not in our array.

Complexity

Complexity is O(m * log n), where m <= 10000 is the biggest value of num. The idea is that in the beginning we can have not more than m//2 intervals and then on each iteration number of intervals can not increase (?) or increase not too fast. Also number of iterations can not too big, because it is enough log n patches always.

Code

class Solution:
    def merge(self, intervals):
        intervals.sort(key=lambda x: x[0])
        merged = []
        
        for interval in intervals:
            if not merged or merged[-1][1] < interval[0] - 1:
                merged.append(interval)
            else:
                merged[-1][1] = max(merged[-1][1], interval[1])

        return merged


    def minPatches(self, nums, n):
        ints, patches = [[0,0]], 0
        for num in nums:
            ints = self.merge(ints + [[i+num, j+num] for i,j in ints])

        while ints[0][1] < n:
            ints = self.merge(ints + [[i+ints[0][1]+1, j+ints[0][1]+1] for i,j in ints])
            patches += 1

        return patches

Solution 2

We can improve this solution, if we upgrade the idea of smallest number which we do not have yet.

Example: nums = [1, 2, 4, 13, 43]. We go form the smallest number add them one by one and always keep the possible range of numbers we can get in the form [0, k], that is, it is not union of intervals, but only one interval. Let us go through this example.

  1. We did not choose any numbers yet, so we have interval [0, 0].
  2. Are we missing something if we take next number 1? No, let us take it, now we have interval [0, 1].
  3. Are we missing something if we take next number 2? No, let us take it, now we have interval [0, 3].
  4. Are we missing something if we take next number 4? No, let us take it, now we have interval [0, 7].
  5. Are we missing something if we take next number 13? Yes, we missing! What we need to take next patch equal to 8. So now, our interval is [0, 15].
  6. Our next missing number 16 is more, than next number in array: 13. So if fact, we can create [0, 28].
  7. Our next missing number is 29, it is less than 43, so we add 29 as patch. and we have interval [0, 57].

Complexity

Complexity of this solution is O(n).

Code

class Solution:
    def minPatches(self, nums, n):
        reach, ans, idx = 0, 0, 0
        
        while reach < n:
            if idx < len(nums) and nums[idx] <= reach + 1:
                reach += nums[idx]
                idx += 1
            else:
                ans += 1
                reach = 2*reach + 1       
                
        return ans