Leetcode problems explained – 330 – Patching Array

In this series, I hope not only to show my solutions for Leetcode problems but also to explain them in the simplest way possible.

330 - Patching Array [Hard]

Problem statement

From Leetcode:

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.

Constraints:

1 <= nums.length <= 1000

1 <= nums[i] <= 10^4

nums is sorted in ascending order.

1 <= n <= 2^31 - 1

To figure it out, as always, it helps to understand the elements in the problem and what is being asked. A patch in this context is just a new number added to the array, while n is the target number we want to be able to achieve by summing some elements of the array.

Let's imagine we cook with numbers

Imagine you’re in a kitchen, and your goal is to make dishes that require a certain range of ingredients. These ingredients are numbers, and I can only achieve a certain recipe if I can sum those numbers to what the recipe asks for.

Let's say my kitchen is very simple at the moment and I only have two ingredients: 1 and 3.

I look at my cookbook and I see a couple of recipes:

• Rice - 1
• Chicken - 2
• Fried eggs - 3
• Apple pie - 4
• Feijoada - 7

So, based on my list of ingredients, what recipes can I cook right now?

The answer is: rice, fried eggs, and apple pie.

I can use any amount of the numbers or sum them all.

What if I went to the number market and bought me a 4?

Now my ingredients list would be: 1, 3, and 4.

I still can cook rice, fried eggs, and apple pie, but now I can also cook a feijoada!

That means, if my N was 7 (a feijoada), my answer would be 1 because I only had to add a single other item to my list.

What if I wanted to cook chicken? In that case, I'd have two options, I could either add another 1 or add a 2!

Let's code

Now let's think in code.

Let's start by initializing three variables:

• sum = 0: it represents the maximum sum that can be achieved with the given nums and any patches.
• patches = 0: counting how many numbers we need to add to our array.
• i = 0: this is our pointer and we are initializing it here just because a while loop is slightly faster than a for loop in JS.

function minPatches(nums, n) {
    let patches = 0;
    let sum = 0;
    let i = 0;

    // more code here
    
    return patches;
}

You will notice I'm also already returning patches before I do anything else. It is a good practice to cover your base case right away.

Now we can loop until sum is lesser than our target value n. If the sum is more, it means we can achieve our target.

function minPatches(nums, n) {
    let patches = 0;
    let sum = 0;
    let i = 0;

    while (sum < n) {
      // more code here
    }    
    return patches;
}

If the current number nums[i] can be used to extend the sum without missing any numbers (nums[i] <= sum + 1), we add it to sum.

We also increment i, since the current number has been used.

function minPatches(nums, n) {
    let patches = 0;
    let sum = 0;
    let i = 0;

    while (sum < n) {
      if (i < nums.length && nums[i] <= sum + 1) {
            sum += nums[i]; 
            i++;
        }

        // more code here    
    }    
    return patches;
}

If not, we need to patch. The optimal number is always sum + 1 because it exactly fills the gap needed to continue.

Since all the question

is interested in is the number of patches we add, all we need to do is increase our patches by 1.

Note we don't increment i, because the number might be repeated.

And here's the final solution:

function minPatches(nums, n) {
    let patches = 0;
    let sum = 0;
    let i = 0;

    while (sum < n) {
      if (i < nums.length && nums[i] <= sum + 1) {
            sum += nums[i]; 
            i++;
        }
      else {
        sum += sum + 1;
        patches++;
      }
    }    
    return patches;
}

Time Complexity

The function's complexity primarily depends on how many times the while loop executes.

The loop condition is sum < n. In each iteration, sum increases significantly (either by at least nums[i] which is always optimal to be used, or by sum + 1 which doubles sum plus 1).

If nums[i] is always optimal and small, we might add each nums[i] once until nums is exhausted (O(m) iterations, with m being the length of nums).

The number of patches added depends on the gaps between sum and nums[i] values or n. Each patch effectively doubles the range of sum, meaning the number of patches required to reach or exceed n from a smaller sum is logarithmic concerning n.

Consequently, the total time complexity is O(m + log n), or simply O(log n), where m is the number of elements in nums and log n represents the logarithmic number of patches needed to reach n.

Space Complexity

The space complexity is O(1) as the function uses a fixed amount of extra space (for patches, sum, i, and a few conditional variables) regardless of the input size.

Speed

As we can see, our solition did quite good as compared to the overall right solution on Leetcode

Why is this important?

The array patching problem, while seemingly abstract, has significant implications and applications in real-world scenarios. This problem teaches crucial concepts such as coverage, optimality, and efficiency.

It's a fairly common problem to be asked, and one that you can actually apply to frequent daily tasks.

At its core, the array patching problem is about optimizing the use of resources (numbers in the array) to achieve a comprehensive set of outcomes (sums). This is directly applicable to resource allocation problems where the goal is to satisfy a range of requirements with minimal additions.

Some real-life applications you will see might include:

Network Packet Transmission:

In networking, ensuring that packets can be reconstructed regardless of the order of arrival or the presence of all packets is critical. Using techniques similar to the array patching problem, systems can be designed to tolerate packet loss, where the 'patches' are additional packets that help in reconstructing the original message.

Error Correction Codes

In data transmission, error-correcting codes (such as Reed-Solomon) use principles akin to array patching to add redundant data that can be used to reconstruct the original data even in the case of errors (loss or corruption of parts of the data). Here, the 'patches' are extra bits or symbols added to ensure all possible errors up to a certain limit can be corrected.

Financial Risk Assessment

Assessing and covering ranges of risks can involve strategies similar to array patching, where the goal is to ensure that all potential financial risks within a certain scope are accounted for with minimal but sufficient safeguards.

Cryptographic Functions

Constructing functions or systems that can cover all necessary conditions with minimal components can involve adding specific 'elements' to ensure the system's security. This is somewhat analogous to adding the minimal numbers needed to reach every possible sum within a range.