Patching Array — Solution in Python, Java & C++
Patching Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.
Patching Array is a hard coding problem on arrays and greedy, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a sorted array of positive integers nums and an integer n. You may patch the array by inserting any positive integer into it.
Return the minimum number of patches needed so that every integer in the range [1, n] can be written as the sum of some elements of the array (each element used at most once).
Example 1
Input: nums = [2,4], n = 10
Output: 2
Explanation: Adding 1 makes every value up to 7 reachable; adding 8 then covers 8 to 15.
Example 2
Input: nums = [1,2,2], n = 5
Output: 0
Explanation: 1, 2, 1+2, 2+2 and 1+2+2 already cover 1 to 5.
Example 3
Input: nums = [3,7], n = 50
Output: 4
Explanation: Patch 1, 2, 14 and 28.
Constraints
1 <= nums.length <= 10001 <= nums[i] <= 10^4nums is sorted in ascending order1 <= n <= 2^31 - 1
Hints for Patching Array
Hint 1
Suppose every value in
[1, reach]can already be formed. What happens when you add a numberx <= reach + 1?Hint 2
Then every value up to
reach + xcan be formed. If the next array element is larger thanreach + 1, the valuereach + 1can never be formed without a patch.Hint 3
Patch with exactly
reach + 1— it doubles the covered range, the most any single patch can do.
How to solve Patching Array
Track the prefix [1, reach] of values that can be formed. An element x <= reach + 1 extends it to reach + x; when the next element is too big, the gap reach + 1 must be patched, and patching exactly reach + 1 extends the range the furthest.
Approach
- Start with
miss = 1(the smallest value not yet formable), indexi = 0andpatches = 0. Use 64-bit arithmetic:misscan exceed2^31. - While
miss <= n: ifiis in range andnums[i] <= miss, setmiss += nums[i]and advancei. - Otherwise patch with
missitself:miss += missand count a patch. - Return
patches.
Why it works
If every value below miss is formable and we add x <= miss, every value below miss + x becomes formable (old sums, plus x added to them). If the next element exceeds miss, no subset of the remaining elements can form miss, so some patch p <= miss is required, and p = miss gives the largest new range [1, 2·miss). Any optimal solution can be exchanged for this one without needing more patches.
Complexity
- Time —
O(len(nums) + log n) - Space —
O(1)
Pitfalls
misscan reach about2^32whennis near2^31 - 1— use a 64-bit counter.- Use the array elements whenever they fit; patching is only for real gaps.
- Elements larger than
nare simply never needed.
Reference solution
Python
from typing import List
def minPatches(nums: List[int], n: int) -> int:
miss = 1
i = 0
patches = 0
while miss <= n:
if i < len(nums) and nums[i] <= miss:
miss += nums[i]
i += 1
else:
miss += miss
patches += 1
return patchesJava
public static int minPatches(int[] nums, int n) {
long miss = 1;
int i = 0, patches = 0;
while (miss <= n) {
if (i < nums.length && nums[i] <= miss) { miss += nums[i]; i++; }
else { miss += miss; patches++; }
}
return patches;
}C++
int minPatches(vector<int>& nums, int n) {
long long miss = 1;
int i = 0, patches = 0;
while (miss <= n) {
if (i < (int)nums.size() && nums[i] <= miss) { miss += nums[i]; i++; }
else { miss += miss; patches++; }
}
return patches;
}JavaScript
var minPatches = function(nums, n) {
var miss = 1, i = 0, patches = 0;
while (miss <= n) {
if (i < nums.length && nums[i] <= miss) { miss += nums[i]; i++; }
else { miss += miss; patches++; }
}
return patches;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms