Leetcode 330. Patching Array
Problem Explanation
Given an array of positive integers in increasing order and a target integer N, our goal is to be able to form all numbers from 1 to N (inclusive) using the sum of any combination of elements from the array. If the array as it is, cannot form all numbers from 1 to N, then we need to add elements to the array so that this becomes possible. The problem asks for the minimum number of such additional elements we need to add.
For example, if we have the array [1, 3]
and N=6. We cannot form the number 2
and 6
using the current elements, so we need to add 2
to the array. The minimum number of additional elements (patches) needed here is 1
which is 2
.
Solution Approach
To solve this problem, we follow a Greedy strategy. Start with a variable miss = 1
, this variable represents the minimum sum in range [1,n]
that we might miss. Now, iterate through the array, where at each step, we:
- Check if the current array element is smaller than or equal to
miss
- If yes, include this array element in the subset. So, we add the value of the current array element to
miss
. If we have traverse the array till the end, still we are unable to reach to then
then we can add a number into the array which is equal tomiss
. Thenmiss
would be2*miss
- If no, the number
miss
is the number we need to patch/add. So, addmiss
tomiss
itself and increment counter of patches.
- If yes, include this array element in the subset. So, we add the value of the current array element to
Continue this process until miss
is smaller than or equal to n
. Our answer will be the count of these patches.
The logic behind this approach relies on the fact that any n
positive numbers can at most cover the range from 1
to n * (n + 1) / 2
.
Example Walkthrough
Let's consider an example where we have the array [1, 3]
and n=6
.
At start, miss = 1
and we have 0 patches.
- At index 0,
nums[0] = 1 <= miss = 1
, so we addnums[0]
tomiss
andmiss
becomes2
. - Now, there is no
2
in the array and2 <= miss = 2
, so we add2
tomiss
and incrementpatches
by 1. Now,miss
becomes4
. - Next, at index 1,
nums[1] = 3 <= miss = 4
, so we addnums[1]
tomiss
andmiss
becomes7
. - Now
miss = 7
is more thann = 6
, so we stop here. Our answer will bepatches = 1
.
Python Solution
1 2python 3class Solution: 4 def minPatches(self, nums: List[int], n: int) -> int: 5 miss, patches, i = 1, 0, 0 6 size = len(nums) 7 while miss <= n: 8 if i < size and nums[i] <= miss: 9 miss += nums[i] 10 i += 1 11 else: 12 miss += miss 13 patches += 1 14 return patches
Java Solution
1 2java 3class Solution { 4 public int minPatches(int[] nums, int n) { 5 long miss = 1; 6 int patches = 0, i = 0; 7 8 while (miss <= n) { 9 if (i < nums.length && nums[i] <= miss) { 10 miss += nums[i]; 11 i++; 12 } else { 13 miss += miss; 14 patches++; 15 } 16 } 17 18 return patches; 19 } 20}
JavaScript Solution
1 2javascript 3var minPatches = function(nums, n) { 4 let miss = 1, patches = 0, i = 0; 5 while (miss <= n) { 6 if (i < nums.length && nums[i] <= miss) { 7 miss += nums[i++]; 8 } else { 9 miss += miss; 10 patches++; 11 } 12 } 13 return patches; 14};
C# Solution
1 2csharp 3public class Solution { 4 public int MinPatches(int[] nums, int n) { 5 int patches = 0, i = 0; 6 long miss = 1; 7 while (miss <= n) { 8 if (i<nums.Length && nums[i] <= miss) { 9 miss += nums[i++]; 10 } else { 11 miss += miss; 12 patches++; 13 } 14 } 15 return patches; 16 } 17}
C++ Solution
1
2cpp
3class Solution {
4public:
5 int minPatches(vector<int>& nums, int n) {
6 long miss = 1, patches = 0, i = 0;
7
8 while (miss <= n) {
9 if (i < nums.size() && nums[i] <= miss) {
10 miss += nums[i++];
11 } else {
12 miss += miss;
13 patches++;
14 }
15 }
16
17 return patches;
18 }
19};
Time Complexity
The main operation of this algorithm is iterating over the array and comparing each element with the 'miss' variable. Hence, the overall time complexity would be O(n) for all solutions.
Space Complexity
Since this algorithm does not require a significant amount of extra space, the space complexity for Python, Java, JavaScript, C#, and C++ solutions is O(1).
Some Points to Note
In the Java solution, use long
instead of int
to prevent overflow.
In Python, you don't need to define size
separately; this is because dynamically-typed languages such as Python fetch the length of the list on the fly.
In JavaScript, ensure that you increment your i
within the conditional statement to prevent out of bounds exceptions.
In the C# and C++ solutions, make sure to use long
instead of int
to prevent overflow as well.
You can factor in exceptions; for instance, what should happen when n
is 0
or nums
is empty? To make your function safer, include checks for these cases at the beginning of your function.
Overall, the concept of this problem can be hard to grasp at first, particularly the greedy strategy and its implementation. It might help to visualize or walk through the process with several examples until the process makes sense to you. The payoff is an elegant, efficient approach to a complex problem.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.