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 <= 10001 <= nums[i] <= 104nums is sorted in ascending order.1 <= n <= 231 - 1Problem Overview: You receive a sorted array nums and an integer n. The goal is to add the minimum number of integers (patches) so every number in the range [1, n] can be formed as a sum of elements from the array. Each number can be used once per sum.
Approach 1: Exhaustive Coverage Check (Brute Force) (Time: O(2^n) to generate sums, Space: O(2^n))
A straightforward idea is to track every possible subset sum that can be formed from the current array. After computing all reachable sums, scan the range [1, n] to find missing values. Whenever a gap appears, add that number as a patch and recompute the reachable sums. This guarantees correctness because every missing value is explicitly patched, but generating subset sums grows exponentially. Even with pruning or a hash set, the solution quickly becomes infeasible for large inputs. This approach mainly demonstrates the problem structure rather than serving as a practical solution.
Approach 2: Greedy Patching (Time: O(m + k), Space: O(1))
The optimal solution relies on a greedy coverage insight. Suppose you can already form every value in the range [1, miss). If the next array element nums[i] is ≤ miss, you can extend the reachable range to [1, miss + nums[i]) by including it in sums. If nums[i] is greater than miss, a gap appears because miss cannot be formed. The best patch is exactly miss, which doubles the coverage to [1, 2 * miss). Repeat this process until the coverage exceeds n. This greedy rule works because adding the smallest missing value maximizes the expansion of reachable sums with the fewest patches. The algorithm iterates once through the array while maintaining a running coverage boundary.
The logic fits naturally with problems involving sorted arrays and interval expansion using greedy decisions. Instead of tracking individual sums, you track the largest continuous range of sums that can already be built.
Recommended for interviews: Interviewers expect the greedy coverage approach. Brute force shows you understand the subset‑sum interpretation, but the greedy insight demonstrates algorithmic maturity. Recognizing that maintaining the reachable range [1, miss) eliminates the need for subset enumeration is the key step that leads to the optimal O(n) solution.
This approach uses a greedy strategy to find the minimum number of patches required to cover the entire range [1, n]. Starting with a number missing initialized to 1, which represents the smallest sum we cannot form, we iterate through the array. If the current number in the array is less than or equal to missing, we increment our range to missing + nums[i]. Otherwise, we add missing to the array, effectively patching it, and increment our missing sum by itself.
The C solution first initializes the count of patches and an iterator at zero, and sets missing to 1. It then iterates until missing is greater than n. For each iteration, if the current number in nums is less than or equal to missing, missing is incremented by nums[i] and the array index is incremented. If not, it increments missing by its current value and increments the patch count.
Time complexity: O(m + log n) where m is the length of nums. The loop runs through nums and potentially adds new numbers until missing > n.
Space complexity: O(1), since no auxiliary space is used apart from a few variables.
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:
x, since all numbers in [1,..x-1] can be represented, after adding x, all numbers in the range [1,..2x-1] can be represented, and the smallest positive integer that cannot be represented becomes 2x.x, let's assume it's x', since all numbers in [1,..x-1] can be represented, after adding x', all numbers in the range [1,..x+x'-1] can be represented, and the smallest positive integer that cannot be represented becomes x+x' \lt 2x.Therefore, we should greedily add the number x to cover a larger range.
We use a variable x to record the current smallest positive integer that cannot be represented, initialized to 1. At this time, [1,..x-1] is empty, indicating that no number can be covered; we use a variable i to record the current index of the array being traversed.
We perform the following operations in a loop:
i is within the range of the array and nums[i] \le x, it means that the current number can be covered, so we add the value of nums[i] to x, and increment i by 1.x is not covered, so we need to supplement a number x in the array, and then update x to 2x.x is greater than n.The final answer is the number of supplemented numbers.
The time complexity is O(m + log n), where m is the length of the array nums. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Patching Approach | Time complexity: O(m + log n) where m is the length of Space complexity: O(1), since no auxiliary space is used apart from a few variables. |
| Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Subset Sum Enumeration (Brute Force) | O(2^n) | O(2^n) | Conceptual understanding of all possible sums; impractical for real constraints |
| Greedy Coverage Expansion | O(m + k) | O(1) | Optimal solution when the array is sorted and you need minimal patches |
Patching Array | Thought Process | Dry Runs | GOOGLE | Leetcode 330 | codestorywithMIK • codestorywithMIK • 14,537 views views
Watch 9 more video solutions →Practice Patching Array with our built-in code editor and test cases.
Practice on FleetCode