LeetCode Problem 330

Difficulty: 🔴 Hard
Topics: Array, Greedy

Solution

LeetCode 330 - Patching Array

Problem Understanding

The problem gives us a sorted array of positive integers, nums, and a target integer n. We are allowed to insert additional numbers into the array, called patches. The goal is to ensure that every number in the range [1, n] can be formed as the sum of some subset of the array elements.

We need to return the minimum number of patches required to achieve this.

The important detail is that we are not trying to generate all subsets explicitly. Instead, we need to guarantee coverage of every integer in the range. For example, if we can form all numbers from 1 through 6, then the coverage is continuous. If 7 cannot be formed, then there is a gap.

The input array is already sorted in ascending order, which is extremely important for the greedy solution. Since all numbers are positive, once a gap appears in the representable range, later larger numbers cannot fill it unless we patch appropriately.

The constraints are also important:

• nums.length <= 1000
• n <= 2^31 - 1

The target value n can be very large, so any solution that explicitly tracks all possible subset sums is infeasible. We need a much more efficient strategy.

Several edge cases are important:

• The array may not start with 1. In that case, we cannot even form the number 1, so a patch is immediately required.
• The array may already cover the entire range, requiring zero patches.
• Large gaps between numbers can force multiple patches.
• Since n can approach 2^31 - 1, integer overflow must be considered in languages with fixed-size integers like Go.
• The optimal strategy must minimize patches, not just achieve coverage.

Approaches

Brute Force Approach

A brute force solution would attempt to track every possible subset sum that can be formed from the array. Whenever a gap appears in the range [1, n], we could try inserting candidate patches and recomputing reachable sums.

One possible implementation uses dynamic programming or a set of reachable sums. Starting from {0}, for every number we add all new sums formed by including that number. If some value in [1, n] is missing, we try patching numbers until full coverage is achieved.

This approach is correct because it explicitly computes all achievable sums. However, it becomes computationally infeasible when n is large. Since n can exceed two billion, maintaining reachable states up to n is impossible within memory and time limits.

Optimal Greedy Approach

The key insight is that we do not need to know every individual subset sum. Instead, we only need to track the continuous range of values we can already construct.

Suppose we can currently form every number in the range [1, x - 1]. Then:

• If the next array value is <= x, we can extend coverage.
• If the next array value is > x, then x itself cannot be formed, so we must patch.

The optimal patch is exactly x.

Why? Because adding x extends the reachable range from [1, x - 1] to [1, 2x - 1], which is the maximum possible extension from a single patch.

This greedy observation leads to a very efficient logarithmic-style solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * target) or worse	O(target)	Tracks all subset sums explicitly
Optimal	O(len(nums))	O(1)	Greedily expands reachable range

Algorithm Walkthrough

Core Greedy Invariant

At every step, maintain a variable miss, representing the smallest value that cannot currently be formed.

If we can form all numbers in [1, miss - 1], then:

• Using a number num <= miss, we can extend coverage to [1, miss + num - 1].
• If num > miss, then miss is impossible to form unless we patch it directly.

Step-by-Step Algorithm

1. Initialize:

• miss = 1
• index = 0
• patches = 0

Initially, we cannot form any positive number, so the smallest missing value is 1. 2. Continue while miss <= n.

If miss > n, then every value in [1, n] is already covered. 3. Check whether the current array value can help.

If index < len(nums) and nums[index] <= miss, then this number can safely extend the reachable range. 4. Extend coverage using the current array value.

Since we already cover [1, miss - 1], adding nums[index] lets us cover:

[1, miss + nums[index] - 1]

Therefore:

miss += nums[index]

Move to the next array element. 5. Otherwise, patch the array with miss.

If the next number is larger than miss, then miss cannot be formed.

The optimal patch is exactly miss. 6. Update coverage after patching.

Adding miss extends the reachable range from:

[1, miss - 1]

to:

[1, 2 * miss - 1]

Therefore:

miss += miss

Increment the patch counter. 7. Repeat until coverage exceeds n.

Why it works

The invariant is that before every iteration, we can form every number in [1, miss - 1].

If the next array value is at most miss, then combining it with existing reachable sums extends coverage continuously without gaps.

If the next array value is larger than miss, then no subset can form miss. Any valid solution must patch a value at most miss. Choosing exactly miss maximizes the newly covered range, making it the greedy optimal choice.

Because every step either consumes an array element or doubles the reachable range, the algorithm is both correct and efficient.

Python Solution

from typing import List

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

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

        return patches

The implementation directly follows the greedy strategy.

The variable miss represents the smallest value we cannot currently construct. Initially, this is 1.

The index variable tracks which array element we are currently processing. Since the array is sorted, every usable number appears in increasing order.

Inside the loop, we first check whether the current array element is small enough to extend the reachable range. If it is, we add it to miss.

Otherwise, we must patch. The optimal patch is exactly miss, so we double the reachable range by performing miss += miss.

The loop terminates once miss > n, meaning all numbers up to n are representable.

Go Solution

func minPatches(nums []int, n int) int {
    miss := int64(1)
    patches := 0
    index := 0
    target := int64(n)

    for miss <= target {
        if index < len(nums) && int64(nums[index]) <= miss {
            miss += int64(nums[index])
            index++
        } else {
            miss += miss
            patches++
        }
    }

    return patches
}

The Go implementation is nearly identical to the Python version, but there is one important difference.

Since n can be as large as 2^31 - 1, repeated doubling may overflow a 32-bit integer. To avoid this, the implementation uses int64 for miss and target.

The input slice may be nil or empty, but the logic naturally handles both cases correctly.

Worked Examples

Example 1

Input:

nums = [1, 3]
n = 6

Step	miss	Current Num	Action	New Coverage	Patches
Start	1	1	Use 1	[1,1]	0
Next	2	3	Patch 2	[1,3]	1
Next	4	3	Use 3	[1,6]	1

Now miss = 7, which is greater than n.

Answer:

1

Example 2

Input:

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

Step	miss	Current Num	Action	New Coverage	Patches
Start	1	1	Use 1	[1,1]	0
Next	2	5	Patch 2	[1,3]	1
Next	4	5	Patch 4	[1,7]	2
Next	8	5	Use 5	[1,12]	2
Next	13	10	Use 10	[1,22]	2

Coverage exceeds 20.

Answer:

2

Example 3

Input:

nums = [1,2,2]
n = 5

Step	miss	Current Num	Action	New Coverage	Patches
Start	1	1	Use 1	[1,1]	0
Next	2	2	Use 2	[1,3]	0
Next	4	2	Use 2	[1,5]	0

Coverage already reaches 5.

Answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(len(nums))	Each array element is processed at most once
Space	O(1)	Only a few variables are used

Although patch operations may occur, each patch doubles the reachable range. Therefore, the number of patches is at most logarithmic in n.

The algorithm is extremely efficient because it never generates subset sums explicitly.

Test Cases

from typing import List

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

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

        return patches

sol = Solution()

assert sol.minPatches([1, 3], 6) == 1  # Basic example with one missing gap
assert sol.minPatches([1, 5, 10], 20) == 2  # Requires multiple patches
assert sol.minPatches([1, 2, 2], 5) == 0  # Already fully covered

assert sol.minPatches([], 7) == 3  # Empty array requires powers of two
assert sol.minPatches([1, 2, 31, 33], 2147483647) == 28  # Large n stress test
assert sol.minPatches([1], 1) == 0  # Smallest valid coverage
assert sol.minPatches([2], 3) == 1  # Missing initial 1
assert sol.minPatches([1, 2, 4, 8], 15) == 0  # Perfect power-of-two coverage
assert sol.minPatches([1, 10], 20) == 3  # Large gap forces patches
assert sol.minPatches([1, 1, 1], 20) == 3  # Repeated small numbers
assert sol.minPatches([1, 2, 4, 13, 43], 100) == 2  # Mixed coverage and gaps

Test	Why
[1,3], 6	Validates single patch scenario
[1,5,10], 20	Validates multiple greedy patches
[1,2,2], 5	Confirms no unnecessary patches
[], 7	Tests completely empty input
[1,2,31,33], 2147483647	Stress test for very large target
[1], 1	Smallest valid case
[2], 3	Tests missing initial coverage
[1,2,4,8], 15	Perfect continuous coverage
[1,10], 20	Tests large internal gap
[1,1,1], 20	Tests repeated small values
[1,2,4,13,43], 100	Complex mixed scenario

Edge Cases

Empty Array

If nums is empty, we initially cannot form any positive number. The algorithm repeatedly patches the current missing value:

1 -> 2 -> 4 -> 8 ...

This creates powers of two and maximally expands coverage each time. The implementation naturally handles this because the array access condition fails immediately.

Missing Initial 1

If the first element is greater than 1, then the number 1 cannot be formed. This is a common source of bugs because some implementations assume the array already starts with 1.

For example:

nums = [2]

The algorithm correctly patches 1 first before processing 2.

Very Large n

Since n can be close to 2^31 - 1, repeated doubling can overflow 32-bit integers in some languages.

The Go implementation avoids this by using int64 for all arithmetic involving miss. Python integers automatically expand, so no special handling is needed there.

Large Gaps Between Numbers

Arrays like:

[1, 100]

contain large unreachable regions. A naive strategy might insert arbitrary values inefficiently.

The greedy approach always patches the smallest missing value, guaranteeing the maximum expansion of reachable coverage and minimizing the number of patches.