LeetCode 330: Patching Array

Problem Description

LeetCode Problem 330

Given a sorted integer array nums and an integer n, add/patch elements to the array such that any number in the range [1, n] inclusive can be formed by the sum of some elements in the array.

Return the minimum number of patches required.

Example 1:

Input: nums = [1,3], n = 6
Output: 1
Explanation:
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

Example 2:

Input: nums = [1,5,10], n = 20
Output: 2
Explanation: The two patches can be [2, 4].

Example 3:

Input: nums = [1,2,2], n = 5
Output: 0

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 104
• nums is sorted in ascending order.
• 1 <= n <= 231 - 1

Difficulty: Hard

Tags: array, greedy

Rating: 92.25%

Solution Approach

The key to solving this problem lies in understanding a crucial insight: if we can form all numbers up to x, and we have a number y that is less than or equal to x+1, then by adding y to our collection, we can form all numbers up to x+y.

Solution

class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        patches = 0      # Count of numbers we need to add
        covered = 0      # Numbers we can form up to this value
        i = 0           # Current index in nums array
        
        while covered < n:
            # If we have a number in array that can extend our range
            if i < len(nums) and nums[i] <= covered + 1:
                covered += nums[i]    # Extend our coverage
                i += 1
            else:
                # We need to patch covered + 1
                patches += 1
                covered += (covered + 1)
                
        return patches

How It Works

Let’s break down the algorithm with an example using nums = [1,5,10] and n = 20:

1. Initial State:

   • covered = 0 (we can’t form any numbers yet)
   • i = 0 (pointing to first number)
   • patches = 0

2. First Iteration:

   • nums[0] = 1 ≤ covered + 1 (1 ≤ 1)
   • Add 1 to covered
   • covered = 1, i = 1

3. Second Iteration:

   • nums[1] = 5 > covered + 1 (5 > 2)
   • Need to patch 2
   • covered += 2 (now covered = 3)
   • patches = 1

4. Third Iteration:

   • Need to patch 4
   • covered += 4 (now covered = 7)
   • patches = 2

5. Continue:

   • With patches 2 and 4, plus original numbers [1,5,10],
   • We can now form all numbers from 1 to 20

Time and Space Complexity

• Time Complexity: $O(n)$

  • We process each number in the array once
  • The while loop continues until we cover all numbers up to n

• Space Complexity: $O(1)$

  • We only use a few variables regardless of input size