#330

Hard

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Patching Array

Patching Array requires adding the minimum numbers to cover all sums from 1 to n using greedy choices and invariant checks.

array greedy

Problem Statement

Given a sorted integer array nums and a target integer n, you must add the minimum number of elements to nums so that every integer from 1 to n can be formed as the sum of some subset of the array. Your goal is to determine the fewest patches needed to cover the full range.

For example, if nums = [1,3] and n = 6, the sums 1, 3, and 4 can be formed, but 2, 5, and 6 cannot. By adding 2, all sums from 1 to 6 become possible, resulting in one patch. Return the minimum number of such patches required for any given input.

Examples

Example 1

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

Output: 1

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

The two patches can be [2, 4].

Example 3

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

Output: 0

Example details omitted.

Constraints

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

Solution Approach

Greedy Expansion of Reachable Sums

Maintain a variable 'miss' representing the smallest sum not yet reachable. Iterate through nums and, whenever the current number is less than or equal to miss, add it to extend the reachable range. Otherwise, patch miss itself to cover the gap.

Invariant Maintenance

After each step, the invariant is that all numbers less than 'miss' can be formed. This allows you to confidently add either the next array element or a patch without rechecking all previous sums, ensuring correctness while minimizing patches.

Iterative Patching Until Coverage

Continue iterating and patching until miss exceeds n. Count each patch added. This ensures the greedy choice always maximally increases coverage, and the algorithm terminates with the minimum number of patches required.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m + log n) where m is the length of nums and log n accounts for patches, since each patch doubles the reachable sum. Space complexity is O(1) extra space, using only variables to track coverage and patch count.

What Interviewers Usually Probe

Check if candidates understand the greedy invariant principle in sum coverage.
Listen for reasoning about why adding the smallest missing number extends coverage optimally.
Observe if they track 'miss' correctly and iterate efficiently without recalculating sums.

Common Pitfalls or Variants

Common pitfalls

Trying to test all subset sums explicitly, which is too slow for large n.
Failing to update 'miss' correctly after adding a patch, leading to incorrect counts.
Assuming adding any number works rather than the minimal missing number, causing suboptimal patching.

Follow-up variants

Modify the problem to track which specific numbers need patching, not just the count.
Restrict patches to only odd numbers or powers of two, testing adaptation of the greedy strategy.
Ask for the maximum sum achievable with a fixed number of patches instead of minimal patch count.

FAQ

What is the key greedy insight in Patching Array?

The smallest missing sum 'miss' should be added whenever the next array element is larger, as it maximally increases coverage without extra patches.

Can subset sums be precomputed to solve this problem?

Precomputing all subset sums is inefficient for large n; using greedy plus invariant tracking is much faster and avoids exponential computation.

How do we know the number of patches is minimal?

Each patch directly addresses the smallest missing sum, ensuring that each addition covers the largest possible new range and no redundant patches occur.

Does the array need to remain sorted after patching?

Sorting is not strictly required after each patch, but processing in order simplifies maintaining the invariant and implementing the greedy approach.

Is Patching Array always solved with greedy plus invariant validation?

Yes, this pattern ensures minimal patches efficiently and is the standard approach for the problem, handling all edge cases and large n.

terminal

Solution

Solution 1: Greedy

Let's assume that the number $x$ is the smallest positive integer that cannot be represented. Then all the numbers in $[1,..x-1]$ can be represented. In order to represent the number $x$, we need to add a number that is less than or equal to $x$:

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        x = 1
        ans = i = 0
        while x <= n:
            if i < len(nums) and nums[i] <= x:
                x += nums[i]
                i += 1
            else:
                ans += 1
                x <<= 1
        return ans

Continue Practicing

#334 increasing triplet subsequence #324 wiggle sort ii #321 create maximum number