Patching Array solution and explanation
Google
9 more videos on this problem
Patching Array | Thought Process | Dry Runs | GOOGLE | Leetcode 330 | codestorywithMIKcodestorywithMIK · 32:03 · 15K views
330. Patching Array | Greedy | Array | Math | Why not Bitset TrickAryan Mittal · 23:19 · 7K views
Patching Array | Leetcode 330 | Leetcode Hard | Live coding session 🔥🔥🔥Coding Decoded · 21:39 · 7K views
Leetcode - Patching Array (Python)Timothy H Chang · 6:21 · 5K views
LeetCode 330 : Patching Array | Easy ExplanationComprehensive Code · 8:34 · 4K views
LeetCode: Patching Array | Observation Based Approach ExplainedTanishq Chaudhary · 11:02 · 3K views
Best Explanation 330. Patching Array | Math in DSA | LeetCode Daily Challenge | DSAShashCode · 21:35 · 3K views
330. Patching Array | LeetCode SolutionHimanshu Yadav · 9:31 · 3K views
Patching Array - Leetcode 330 - PythonTechError · 6:56 · 2K views
✅Patching Array - 330 LeetCode Hard in 6 mins - Arrays - Explained in Detail - Interview SolutionLeet Logics · 6:16 · 1K views
The problem
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
Approach overview
Problem 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 1: Greedy Patching Approach
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.
class Solution:
def minPatches(self, nums, n):
patches, i, missing = 0, 0, 1
while missing <= n:
if i < len(nums) and nums[i] <= missing:
missing += nums[i]
i += 1
else:
missing += missing
patches += 1
return patches
# Example usage
solution = Solution()
result = solution.minPatches([1, 3], 6)
print(result) # Output: 1import java.util.*;
class Solution {
public int minPatches(int[] nums, int n) {
int patches = 0, i = 0;
long missing = 1;
while (missing <= n) {
if (i < nums.length && nums[i] <= missing) {
missing += nums[i++];
} else {
missing += missing;
patches++;
}
}
return patches;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 3};
int n = 6;
System.out.println(sol.minPatches(nums, n)); // Output: 1
}
}#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
int minPatches(vector<int>& nums, int n) {
int patches = 0, i = 0;
long missing = 1;
while (missing <= n) {
if (i < nums.size() && nums[i] <= missing) {
missing += nums[i++];
} else {
missing += missing;
patches++;
}
}
return patches;
}
};
int main() {
Solution s;
vector<int> nums = {1, 3};
int n = 6;
cout << s.minPatches(nums, n) << endl; // Output: 1
return 0;
}var minPatches = function(nums, n) {
let patches = 0, i = 0;
let missing = 1;
while (missing <= n) {
if (i < nums.length && nums[i] <= missing) {
missing += nums[i++];
} else {
missing += missing;
patches++;
}
}
return patches;
};
console.log(minPatches([1, 3], 6)); // Output: 1#include <stdio.h>
int minPatches(int* nums, int numsSize, int n) {
int patches = 0, i = 0;
long missing = 1;
while (missing <= n) {
if (i < numsSize && nums[i] <= missing) {
missing += nums[i++];
} else {
missing += missing;
patches++;
}
}
return patches;
}
int main() {
int nums[] = {1, 3};
int n = 6;
printf("%d\n", minPatches(nums, 2, n)); // Output: 1
return 0;
}using System;
public class Solution {
public int MinPatches(int[] nums, int n) {
int patches = 0, i = 0;
long missing = 1;
while (missing <= n) {
if (i < nums.Length && nums[i] <= missing) {
missing += nums[i++];
} else {
missing += missing;
patches++;
}
}
return patches;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {1, 3};
int n = 6;
Console.WriteLine(sol.MinPatches(nums, n)); // Output: 1
}
}The Python solution is easy to read and concise. By iterating through the sorted list of numbers, it keeps a running tally of the smallest missing sum and applies patches when necessary to ensure full coverage up to n.
Time complexity: O(m + log n). Space complexity: O(1).
Approach 2: 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:
- If the added number equals
x, since all numbers in[1,..x-1]can be represented, after addingx, all numbers in the range[1,..2x-1]can be represented, and the smallest positive integer that cannot be represented becomes2x. - If the added number is less than
x, let's assume it'sx', since all numbers in[1,..x-1]can be represented, after addingx', all numbers in the range[1,..x+x'-1]can be represented, and the smallest positive integer that cannot be represented becomesx+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:
- If
iis within the range of the array andnums[i] \le x, it means that the current number can be covered, so we add the value ofnums[i]tox, and incrementiby1. - Otherwise, it means that
xis not covered, so we need to supplement a numberxin the array, and then updatexto2x. - Repeat the above operations until the value of
xis greater thann.
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).
function minPatches(nums: number[], n: number): number {
let x = 1;
let ans = 0;
for (let i = 0; x <= n; ) {
if (i < nums.length && nums[i] <= x) {
x += nums[i++];
} else {
++ans;
x *= 2;
}
}
return ans;
}func minPatches(nums []int, n int) (ans int) {
x := 1
for i := 0; x <= n; {
if i < len(nums) && nums[i] <= x {
x += nums[i]
i++
} else {
ans++
x <<= 1
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Patching Approach | Time complexity: O(m + log n). Space complexity: O(1). |
| Greedy | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Patching Array easy or hard?
Patching Array is labeled Hard because the greedy insight is not immediately obvious. Many candidates initially attempt subset-sum or dynamic programming approaches. Recognizing that tracking a continuous coverage range eliminates the need for explicit sum generation is the key challenge.
Patching Array Python/Java solution
The Python or Java implementation follows the same logic: maintain a variable `miss`, iterate through the array, and either extend coverage with the current number or add a patch equal to `miss`. This results in an O(n) greedy algorithm with constant extra space.
How to solve Patching Array in O(n)?
Track the smallest missing sum `miss` that cannot be formed yet. If the next element in the sorted array is ≤ miss, add it to extend coverage. If it is larger, insert a patch equal to miss, doubling the reachable range. Continue until miss exceeds n.
What is the best approach for Patching Array?
The greedy coverage expansion approach is the optimal solution. Maintain the smallest missing value `miss` that cannot yet be formed. If the next array value is ≤ miss, extend coverage; otherwise patch with `miss`. This expands the reachable range efficiently and minimizes the number of patches.
Is Patching Array asked at Google/Amazon/Meta?
Patching Array is considered a classic greedy interview problem and has appeared in interviews and preparation lists for companies like Google, Amazon, and Meta. It tests the ability to recognize range coverage and apply greedy reasoning instead of brute force subset generation.
What data structure is used in Patching Array?
The optimal solution does not require complex data structures. It uses a simple variable to track the current coverage boundary and iterates through the input array. The problem mainly relies on greedy reasoning rather than specialized structures.
What is the time complexity of Patching Array?
The optimal greedy solution runs in O(m + k) time, where m is the length of the input array and k is the number of patches added. Each step either consumes an array element or inserts a patch, so the algorithm processes elements in a single pass. Space complexity is O(1).