Watch 10 video solutions for Patching Array, a hard level problem involving Array, Greedy. This walkthrough by codestorywithMIK has 11,311 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |