330. Patching Array
Problem Description
The problem is focused on a concept called patching array
. Given a sorted array of integer numbers nums
and an integer n
, the task is to modify this array (by potentially adding new numbers to it), so that every number in the set {1, 2, ..., n} can be expressed as the sum of some elements in the array. You need to find the minimum number of new numbers (patches) that you have to add to the array to achieve this.
In simple terms, the question asks: "What is the smallest amount of numbers we can add to nums
so that we can create every integer from 1 up to n
using sums of numbers in nums
?"
Intuition
The intuition behind this solution comes from the idea of exploring "ranges" of numbers that can be created using the current array elements and the numbers we add (patch). The strategy is to start with the smallest possible range [1, 1]
and then expand this range as far as possible until we can reach n
.
If the next number in the array (nums[i]
) is within the current range we can reach (<= x
), it helps us extend the range further without needing to patch the array (since every number up to x
can be formed, adding nums[i]
lets us now form every number up to x + nums[i]
). Each time this happens, we take the next number in nums
and adjust our range accordingly.
However, when the next number in nums
is beyond the current reach (nums[i] > x
), we can't use it to expand our range and must add (patch) a new number. The most efficient number to add is the next number just after the current reach (x
itself), which maximally extends the range by doubling it (since before the patch we could reach x - 1
, after adding x
, we can reach 2x - 1
).
The algorithm keeps track of the patches added and the current range that can be formed. When the range expands to include n
or more, we've added enough patches and can stop the process, returning the number of patches as our answer.
Learn more about Greedy patterns.
Solution Approach
The algorithm makes use of a greedy approach, as it always tries to extend the range as much as possible with each step by either using the next available number in nums
or by patching the smallest number possible to increase the coverage range.
Here is the step-by-step explanation of the implementation:
-
Initialize two pointers:
x
starts at one, representing the current smallest number that we want to make sure can be formed bynums
.i
keeps track of the current position in thenums
array, starting at zero. -
Initialize
ans
to zero, which will keep track of the number of patches needed. -
Start a
while
loop that continues as long asx
is less than or equal ton
. This is because we need to ensure that we can form all the numbers in the range[1, n]
. -
Inside the loop, we check if we have not yet used all numbers in
nums
and whether the current number atnums[i]
can be used to extend the range. Ifnums[i]
is less than or equal tox
, then it means we can usenums[i]
to create new sums up tox + nums[i]
. Thus, we updatex
tox + nums[i]
and incrementi
, moving to the next number innums
. -
If, however, the current number in
nums
is larger thanx
, it cannot be used to extend our range. At this point, we must add a patch. The patch will bex
, doubling the current range we can reach (x <<= 1
is equivalent tox = x * 2
). We also increment theans
since we've used a patch. -
This process continues, either extending the range with the current numbers in
nums
or adding patches untilx
exceedsn
. -
When the loop finishes,
ans
holds the minimum number of patches added to achieve the goal, and we returnans
.
It is important to note that this algorithm runs efficiently because:
- We only iterate through
nums
once. - We use a while loop that runs in O(log n) time in the worst case scenario (when patches are added until
x
exceedsn
). - We do not use any additional data structures, which keeps our space complexity at O(1).
With this approach, we then can return the minimum amount of patches needed to nums
to ensure that all numbers within the range [1, n]
can be formed.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example:
Suppose we have an array nums = [1, 3]
and we want to ensure we can form every number from 1 to n = 7
using sums of numbers from nums
. We want to find the minimum number of patches needed.
-
Initialize
x
to 1 (since we need to start forming sums from 1) andi
to 0 (the index of the first number innums
).ans
is also initialized to 0 as no patches have been added. -
Start the
while
loop sincex = 1 <= n = 7
. -
Inside the loop, check if
i
is within bounds ofnums
and ifnums[i] <= x
. For the first iteration,nums[0] = 1
is equal tox = 1
. Therefore, we can usenums[0]
to form numbers up to1 + 1 = 2
. Updatex
to 2 and incrementi
to 1. -
Next, with
x = 2
andnums[i] = 3
, we can see thatnums[1]
can be used to extend the range. We updatex
to2 + 3 = 5
and incrementi
to 2 (which is now beyond the bounds ofnums
). -
With
x = 5
andi
out of bounds, we need to patch. The optimal patch isx
itself, so we add 5 (the patch) tonums
. The range extends to5 + 5 = 10
, which is beyondn = 7
, so we updatex = 10
. Increaseans
by 1, since we added a patch. -
The
while
loop ends becausex = 10
is now greater thann = 7
. We can now form all the numbers from 1 to 7 using[1, 3, 5]
. -
The
ans
has counted a single patch (5). Therefore, we returnans = 1
.
Through this process, we find that we only need to add one patch (the number 5) to the array [1, 3]
to be able to form every number between 1 and 7 inclusively.
Solution Implementation
1from typing import List
2
3class Solution:
4 def minPatches(self, nums: List[int], n: int) -> int:
5 # Initialize the smallest number that cannot be formed
6 # by summing elements in nums up to index i
7 missing_number = 1
8
9 # Initialize the count of numbers we need to patch (add) to nums
10 patches_count = 0
11
12 # Initialize index for iterating through nums
13 index = 0
14
15 # While the smallest missing number is not greater than n
16 while missing_number <= n:
17 # If current index is within bounds and nums[index] can be used to form missing_number
18 if index < len(nums) and nums[index] <= missing_number:
19 # Increase missing_number by nums[index],
20 # as we can form numbers up to missing_number + nums[index]
21 missing_number += nums[index]
22
23 # Move to the next element in nums
24 index += 1
25 else:
26 # Otherwise, no element in nums can form missing_number.
27 # Therefore, we need to patch (add) missing_number itself
28 patches_count += 1
29
30 # When we add missing_number, we can now form numbers up to missing_number * 2 - 1
31 # We use bit shifting as a fast way to multiply missing_number by 2
32 missing_number <<= 1
33
34 # Return the total count of numbers we needed to patch to nums
35 return patches_count
36
1class Solution {
2 public int minPatches(int[] nums, int n) {
3 long coverage = 1; // This will keep track of the largest number that can be formed by the sum of subsets of sorted nums
4 int patches = 0; // This will count the number of patches (numbers) we need to add
5 int index = 0; // Index to iterate through the nums array
6
7 // Loop until the coverage is less than or equal to n
8 while (coverage <= n) {
9 // If the current index is within the bounds of the nums array
10 // and the current number at nums[index] can be used to extend coverage
11 if (index < nums.length && nums[index] <= coverage) {
12 // Increment coverage by nums[index] and move to the next number in nums
13 coverage += nums[index++];
14 } else {
15 // Increment patches since we need to add a new number to extend coverage
16 patches++;
17 // Double the coverage, simulating the addition of the number equal to the current coverage
18 coverage <<= 1;
19 }
20 }
21
22 // Return the number of patches needed to ensure a complete range from 1 to n
23 return patches;
24 }
25}
26
1#include <vector>
2
3class Solution {
4public:
5 // Function to calculate the minimum number of patches required
6 int minPatches(vector<int>& nums, int n) {
7 long long coverLimit = 1; // Start with a coverage limit of 1
8 int patchesCount = 0; // Initialize the count of patches needed
9 size_t idx = 0; // Initialize the current index for the nums vector
10
11 // Loop until the coverage limit exceeds n
12 while (coverLimit <= n) {
13 // Check if the current index is within bounds and the current number is within the coverage limit
14 if (idx < nums.size() && nums[idx] <= coverLimit) {
15 // The current number can extend the coverage limit
16 coverLimit += nums[idx++]; // Extend the coverage range and move to the next number
17 } else {
18 // The current coverage limit cannot be extended with the existing numbers
19 ++patchesCount; // Increment the number of patches
20 coverLimit <<= 1; // Double the coverage limit
21 }
22 }
23
24 // Return the number of patches needed to cover the range [1, n]
25 return patchesCount;
26 }
27};
28
1function minPatches(nums: number[], n: number): number {
2 let currentMax = 1; // Initialize current maximum possible sum
3 let patchesNeeded = 0; // Initialize count of patches needed
4 let currentIndex = 0; // Initialize current index in the input array `nums`
5
6 // Loop until the current maximum sum is less than or equal to `n`
7 while (currentMax <= n) {
8 // If we haven't reached the end of the input array `nums`
9 // and the current number is less than or equal to the current max sum,
10 // we can use this number to extend the range of representable sums.
11 if (currentIndex < nums.length && nums[currentIndex] <= currentMax) {
12 currentMax += nums[currentIndex++]; // Add the current number to the max sum and increment index
13 } else {
14 // If the condition above is not true, we need to add a patch (a new number)
15 // That number is always the current maximum sum itself, which doubles the range of representable sums.
16 patchesNeeded++; // Increment the patches needed
17 currentMax *= 2; // Double the current max sum
18 }
19 }
20
21 // Return the total number of patches needed
22 return patchesNeeded;
23}
24
Time and Space Complexity
Time Complexity:
The algorithm loops while x
is less than or equal to n
. Within each loop, the code either adds a number from nums
to x
(if the current element in nums
is less than or equal to x
), or it doubles x
(if there is no such element or all elements have been used). The key point is that x
grows exponentially (either by adding a number from nums
that's less than or equal to x
or by doubling through patches). Hence, the number of times the loop can iterate is logarithmic in relation to n
. Specifically, it will iterate O(log(n))
times because x
can double at most O(log(n))
times to exceed n
.
In each iteration, the algorithm performs a constant amount of work unless it's adding a number from nums
, in which case it works in O(1)
time to add a number and move the i
pointer. Since it moves through each element of nums
at most once, the number of these operations is bounded by the length of nums
. Therefore, the total time complexity is O(len(nums) + log(n))
.
Space Complexity:
The extra space used by the algorithm is constant, as it only uses a few variables (x
, ans
, i
) and does not allocate any additional space that grows with the size of the input. Thus, the space complexity is O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Is the following code DFS or BFS?
void search(Node root) { if (!root) return; visit(root); root.visited = true; for (Node node in root.adjacent) { if (!node.visited) { search(node); } } }
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Don’t Miss This!