Patching Array
HardPrompt
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] <= 104numsis sorted in ascending order.1 <= n <= 231 - 1
Approaches
2 approaches with complexity analysis and trade-offs.
This approach simulates the process directly. It first calculates all possible sums that can be formed from the initial nums array. Then, it iteratively finds the smallest number miss in the range [1, n] that cannot be formed. It "patches" the array by adding miss to the set of numbers and re-calculates all possible sums. This process repeats until all numbers from 1 to n can be formed. The number of patches added is the result.
Algorithm
-
- Initialize
patches = 0and a listcurrentNumswith elements from the inputnums.
- Initialize
-
- Start an infinite loop that breaks only when all numbers in
[1, n]are formable.
- Start an infinite loop that breaks only when all numbers in
-
- Inside the loop, create a
Set<Long>calledreachableSumsto store all unique sums, initialized with0.
- Inside the loop, create a
-
- Iterate through each
numincurrentNums. For eachnum, create a temporary set of new sums by addingnumto every existing sum inreachableSums. Add these new sums back toreachableSums.
- Iterate through each
-
- After generating all possible sums, iterate from
1tonto find the smallest integermissthat is not present inreachableSums.
- After generating all possible sums, iterate from
-
- If no such
missis found, it means all numbers in[1, n]are covered. Break the loop.
- If no such
-
- If a
missis found, it means we need to patch the array. Incrementpatches, addmisstocurrentNums, and continue to the next iteration of the main loop to re-evaluate the reachable sums.
- If a
-
- Finally, return the total
patchescount.
- Finally, return the total
Walkthrough
This method attempts to solve the problem by explicitly generating all possible subset sums. It starts with the given numbers and iteratively enhances the set of numbers with patches.
- We maintain a list of numbers,
currentNums, which initially contains the elements ofnums. - We also maintain a count of patches, initialized to 0.
- The main loop continues as long as we haven't covered the entire range
[1, n]. - Inside the loop:
- We use a
SetcalledreachableSumsto store all unique sums that can be formed fromcurrentNums. We initialize it with0(representing the sum of an empty subset). - We iterate through each number in
currentNums. For each number, we iterate through the currentreachableSumsand add the number to each sum, adding the new results back to the set. This is essentially a dynamic programming approach to the subset sum problem. - After generating all sums, we find the smallest integer
missfrom1tonthat is not inreachableSums. - If no such
missexists, it means we can form all numbers up ton, so we break the loop and return the patch count. - If a
missis found, we need to patch. We addmissto ourcurrentNums, increment the patch count, and start the next iteration of the main loop.
- We use a
This approach is conceptually simple but computationally expensive, especially for large n, as the size of reachableSums can grow very large, and the process of generating sums is repeated for each patch.
import java.util.HashSet;import java.util.Set;import java.util.ArrayList;import java.util.List; class Solution { // This solution is too slow and will cause Time Limit Exceeded (TLE). public int minPatches(int[] nums, int n) { int patches = 0; List<Integer> currentNums = new ArrayList<>(); for (int num : nums) { currentNums.add(num); } while (true) { Set<Long> reachableSums = new HashSet<>(); reachableSums.add(0L); for (int num : currentNums) { Set<Long> newSums = new HashSet<>(); for (long sum : reachableSums) { if (sum + num <= n) { newSums.add(sum + num); } } reachableSums.addAll(newSums); } long miss = -1; for (long i = 1; i <= n; i++) { if (!reachableSums.contains(i)) { miss = i; break; } } if (miss == -1) { // All numbers from 1 to n are reachable break; } // Patch with the smallest missing number patches++; currentNums.add((int)miss); } return patches; }}Complexity
Time
O(P * K * S), where `P` is the number of patches, `K` is the number of elements in the array (which grows with patches), and `S` is the number of reachable sums. This complexity is very high and will lead to a "Time Limit Exceeded" error on typical contest platforms for the given constraints.
Space
O(S), where S is the number of unique reachable sums. In the worst case, S can be on the order of `n`. For a large `n`, this would require an enormous amount of memory, making it impractical.
Trade-offs
Pros
Conceptually straightforward and easy to understand.
Directly models the problem statement of forming sums.
Cons
Extremely inefficient in both time and space.
Infeasible for the given constraints on
n(up to 2^31 - 1) due to memory and time limits.Recomputes all subset sums from scratch after every single patch, which is highly redundant.
This is an efficient and optimal approach based on a greedy strategy. The core idea is to keep track of the maximum number, let's call it reachable, such that all integers in the range [1, reachable] can be formed by sums of elements from the (patched) array. We iterate through the numbers and patches, always aiming to extend this reachable range as much as possible until it covers n.
Algorithm
-
- Initialize
miss = 1L(alongto prevent overflow). This variable represents the smallest sum that we cannot currently form.
- Initialize
-
- Initialize
patches = 0to count the number of added elements.
- Initialize
-
- Initialize
i = 0as a pointer for thenumsarray.
- Initialize
-
- Loop as long as
miss <= n. This condition ensures we continue until we can form all numbers up ton.
- Loop as long as
-
- Inside the loop, check if the current number
nums[i](if available) is less than or equal tomiss.
- Inside the loop, check if the current number
-
- Case 1:
nums[i] <= miss. If the condition is true, it means we can usenums[i]to extend our reach. Since we can already form all sums up tomiss - 1, addingnums[i]allows us to form all sums up to(miss - 1) + nums[i]. We updatemisstomiss + nums[i]and advance our pointeri.
- Case 1:
-
- Case 2:
nums[i] > missoriis out of bounds. We cannot formmissusing the available numbers. We must add a patch. The most effective patch ismissitself. Addingmissextends our reachable range to(miss - 1) + miss. We updatemisstomiss + missand incrementpatches.
- Case 2:
-
- After the loop terminates (when
miss > n), return the totalpatches.
- After the loop terminates (when
Walkthrough
The key insight for this problem is to think about the range of sums we can form. Let's say we can form every integer sum in the range [1, k]. What's the next number we need to be able to form? It's k + 1.
We can maintain a variable, let's call it miss, which is the smallest integer that we cannot form with the numbers we've considered so far. Initially, miss is 1.
We then iterate while miss <= n:
- If we have a number
numin our array such thatnum <= miss, we can use it. By taking thisnumand adding it to all the sums we could already form (which is the range[1, miss - 1]), we can now form sums up to(miss - 1) + num. This means our newmissbecomesmiss + num. - If the next number in our array is greater than
miss, or we have no more numbers, we can't formmiss. To fix this, we must add a patch. To be as efficient as possible, we should add a patch that extends our reachable range the furthest. The best number to add ismissitself. If we patch withmiss, our reachable range[1, miss - 1]extends to[1, (miss - 1) + miss]. So, our newmissbecomesmiss + miss. We increment our patch counter for this action.
This greedy choice is optimal because adding any number smaller than miss would result in a smaller extension of our reachable range. Adding a number larger than miss would still leave miss unreachable.
We use a long for miss to avoid integer overflow since n can be large and miss can grow up to n.
class Solution { public int minPatches(int[] nums, int n) { long miss = 1; // Represents the smallest sum that cannot be formed. int patches = 0; int i = 0; while (miss <= n) { if (i < nums.length && nums[i] <= miss) { // If the current number in nums can help us form 'miss', // we use it. This extends our reachable range from [1, miss-1] // to [1, miss-1 + nums[i]]. miss += nums[i]; i++; } else { // If the current number is too large or we've run out of numbers, // we must patch. The most efficient patch is 'miss' itself. // This extends our reachable range from [1, miss-1] // to [1, miss-1 + miss]. miss += miss; patches++; } } return patches; }}Complexity
Time
O(m + log n), where `m` is the length of `nums`. The `while` loop continues as long as `miss <= n`. In each iteration, either the pointer `i` is incremented (which can happen at most `m` times) or `miss` is at least doubled (which can happen at most `log n` times). Therefore, the total number of iterations is bounded by `m + log n`.
Space
O(1). We only use a few variables (`miss`, `patches`, `i`) to keep track of the state, requiring constant extra space regardless of the input size.
Trade-offs
Pros
Highly efficient with a linear time complexity relative to the input size.
Optimal solution for this problem.
Requires constant extra space, making it very memory-efficient.
The logic is simple and elegant once the greedy property is understood.
Cons
The greedy logic, while simple once understood, might not be immediately obvious to come up with.
Solutions
Solution
class Solution {public int minPatches(int[] nums, int n) { long x = 1; int ans = 0; for (int i = 0; x <= n;) { if (i < nums.length && nums[i] <= x) { x += nums[i++]; } else { ++ans; x <<= 1; } } return ans; }}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 ansclass Solution {public: int minPatches(vector<int> &nums, int n) { long long x = 1; int ans = 0; for (int i = 0; x <= n;) { if (i < nums.size() && nums[i] <= x) { x += nums[i++]; } else { ++ans; x <<= 1; } } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.