LeetCode 330: Patching Array

Problem Restatement

We are given a sorted positive integer array nums and an integer n.

We may add new numbers to nums. These added numbers are called patches.

After patching, every number in the range [1, n] must be formable as the sum of some elements from the array.

Return the minimum number of patches required. The array is sorted in ascending order, and n can be as large as 2^31 - 1.

Input and Output

Function shape:

def minPatches(nums: list[int], n: int) -> int:
    ...

Examples

Example 1:

Input: nums = [1, 3], n = 6
Output: 1

Before patching, possible sums include:

1, 3, 4

The number 2 is missing.

Patch 2.

Now with [1, 2, 3], we can form:

1, 2, 3, 4, 5, 6

So the answer is 1.

Example 2:

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

The two patches can be:

[2, 4]

Example 3:

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

The original array already covers all numbers from 1 to 5.

First Thought: Track All Possible Sums

A direct idea is to store every subset sum we can form.

For every number in nums, update a set of reachable sums.

Then check which values from 1 to n are missing.

But this does not scale. Since n can be very large, storing every possible sum up to n can take too much time and memory.

We need a compressed way to describe what sums are reachable.

Key Insight

Instead of storing every reachable sum, track the smallest positive integer that we cannot form yet.

Call it miss.

The invariant is:

All numbers in [1, miss) can already be formed.

At the beginning:

miss = 1

This means we cannot form 1 yet, and the covered range [1, 1) is empty.

Now consider the next available number x.

If:

x <= miss

then we can use x to extend coverage.

Before using x, we can form every value in:

[1, miss)

After adding x, we can also form:

x + [0, miss)

That gives new sums from x to x + miss - 1.

Because x <= miss, this connects directly with the old covered range.

So coverage expands to:

[1, miss + x)

Then update:

miss += x

If the next number is greater than miss, then no existing number can form miss.

The best patch is exactly miss.

Patching miss expands coverage from:

[1, miss)

to:

[1, 2 * miss)

This is the largest possible expansion from one patch, because any patch larger than miss still leaves miss uncovered.

Algorithm

Use three variables:

Steps:

1. Set miss = 1.
2. Set i = 0.
3. Set patches = 0.
4. While miss <= n:
   1. If i < len(nums) and nums[i] <= miss, use nums[i].
   2. Update miss += nums[i].
   3. Move i forward.
   4. Otherwise, patch miss.
   5. Update miss += miss.
   6. Increment patches.
5. Return patches.

Walkthrough

Use:

nums = [1, 5, 10]
n = 20

Initial state:

miss = 1
covered = [1, 1)

The next number is 1.

Since 1 <= miss, use it:

miss = 1 + 1 = 2
covered = [1, 2)

Now we can form 1.

The next number is 5.

But 5 > miss, so we cannot form 2.

Patch 2:

miss = 2 + 2 = 4
patches = 1
covered = [1, 4)

Now we can form 1, 2, 3.

The next number is still 5.

But 5 > miss, so we cannot form 4.

Patch 4:

miss = 4 + 4 = 8
patches = 2
covered = [1, 8)

Now we can form 1 through 7.

The next number is 5.

Since 5 <= miss, use it:

miss = 8 + 5 = 13
covered = [1, 13)

The next number is 10.

Since 10 <= miss, use it:

miss = 13 + 10 = 23
covered = [1, 23)

Now miss = 23, which is greater than n = 20.

So every number from 1 to 20 is covered.

The answer is:

2

Correctness

The algorithm maintains this invariant:

Before each loop, every number in [1, miss) can be formed.

At the start, miss = 1, so the range [1, 1) is empty. The invariant is true.

If the next array number nums[i] is at most miss, then all old sums in [1, miss) remain formable. By adding nums[i] to any old formable sum, and also using nums[i] alone, we form every value from nums[i] through nums[i] + miss - 1.

Because nums[i] <= miss, this new interval touches or overlaps the old covered interval. So the full covered range becomes [1, miss + nums[i]).

If the next array number is greater than miss, then miss cannot be formed by existing numbers. All existing formable sums are less than miss, and the next unused array value is already too large. Therefore, some patch is necessary.

Among all possible patches, choosing miss is optimal. It immediately covers the missing value miss, and because all values in [1, miss) are already covered, it extends coverage to [1, 2 * miss). Any smaller patch extends the range less, and any larger patch leaves miss uncovered.

So every patch made by the algorithm is necessary at that moment and gives the maximum possible coverage.

The loop stops only when miss > n. At that point, the invariant says every number in [1, miss) can be formed, which includes every number from 1 to n.

Therefore, the algorithm returns the minimum number of patches.

Complexity

Implementation

class Solution:
    def minPatches(self, nums: list[int], n: int) -> int:
        miss = 1
        i = 0
        patches = 0

        while miss <= n:
            if i < len(nums) and nums[i] <= miss:
                miss += nums[i]
                i += 1
            else:
                miss += miss
                patches += 1

        return patches

Code Explanation

Start with:

miss = 1

This means 1 is the smallest value we cannot form yet.

The index i points to the next unused number in nums:

i = 0

The answer counter starts at zero:

patches = 0

The loop continues while some number up to n is still missing:

while miss <= n:

If the next number can help extend the current covered range, use it:

if i < len(nums) and nums[i] <= miss:
    miss += nums[i]
    i += 1

Otherwise, we must patch. The best patch is miss itself:

else:
    miss += miss
    patches += 1

When the loop ends, miss > n, so the covered range includes all values from 1 to n.

Testing

def run_tests():
    s = Solution()

    assert s.minPatches([1, 3], 6) == 1
    assert s.minPatches([1, 5, 10], 20) == 2
    assert s.minPatches([1, 2, 2], 5) == 0

    assert s.minPatches([], 7) == 3
    assert s.minPatches([2], 3) == 1
    assert s.minPatches([1, 2, 31, 33], 2147483647) == 28
    assert s.minPatches([1, 2, 3, 8], 20) == 2

    print("all tests passed")

run_tests()

Test meaning: