Problem Description

You are given a sorted array of positive integers nums and a positive integer n. Your goal is to add as few numbers as possible (called "patches") to nums such that you can form every number in the range [1, n] as the sum of some subset of the array (each number can be used at most once).

Key constraints:

• You may add any positive integer as a patch, as many times as needed, but should minimize the number of patches added.
• Each number in nums can be used only once per sum.
• There is always at least one valid solution.
• The input array nums is sorted in ascending order.

Thought Process

At first glance, you might think of generating all possible subset sums and checking which numbers between 1 and n are missing, then patching those. However, this quickly becomes infeasible for large n due to the exponential number of subsets.

The optimization comes from realizing that we can always keep track of the smallest number we cannot form yet, and greedily patch in a way that maximizes our coverage. Instead of brute-forcing all sums, we focus on extending the range of numbers we can represent, step by step, using either the next number in nums or by adding a patch.

The core insight is: if we can already form all sums up to x-1, and the next number in nums is at most x, we can extend our range to x + nums[i] - 1. If not, we patch by adding x itself, thereby doubling our covered range.

Solution Approach

Here’s how we solve the problem step by step:

1. Initialize variables:
   • miss: the smallest number in [1, n] we cannot yet form (start with 1).
   • i: index for traversing nums.
   • patches: counter for how many numbers we've added.
2. Iterate while miss ≤ n:
   • If i is within bounds and nums[i] ≤ miss:
     • Add nums[i] to our "coverage" (i.e., now we can form numbers up to miss + nums[i] - 1).
     • Increment i.
   • Otherwise, patch by adding miss:
     • Increment patches by 1.
     • Now, our coverage extends to miss + miss - 1 (since we can now form all sums up to miss-1, and with the new miss, all sums up to 2*miss-1).
   • Update miss to the new coverage limit + 1.
3. Return patches as the answer.

This greedy approach ensures we always make the optimal patch at each step, and efficiently covers all numbers up to n.

Example Walkthrough

Let's walk through the example nums = [1, 3], n = 6:

• Start: miss = 1, i = 0, patches = 0
• nums[0] = 1 ≤ miss (1 ≤ 1):
  • Add 1 to coverage. Now, can form all sums up to miss + nums[0] - 1 = 2 - 1 = 1 (but actually, coverage extends to miss + nums[0] = 2).
  • Update miss = miss + nums[0] = 2, i = 1
• nums[1] = 3 > miss (3 > 2):
  • Patch with miss = 2.
  • Now, can form all sums up to miss + miss - 1 = 4 - 1 = 3 (but coverage is up to miss + miss = 4).
  • Update miss = miss + miss = 4, patches = 1
• nums[1] = 3 ≤ miss (3 ≤ 4):
  • Add 3 to coverage. Now, can form all sums up to miss + nums[1] = 7.
  • Update miss = miss + nums[1] = 7, i = 2
• miss = 7 > n = 6, so stop.

Result: Only one patch (2) is needed.

Time and Space Complexity

• Brute-force approach:
  • Would require generating all subset sums, which is O(2^m) where m is the length of nums. This is infeasible for large arrays.
• Optimized greedy approach (current solution):
  • Each step either consumes a number from nums or adds a patch, so the loop runs at most O(m + log n) times. The log n comes from the fact that each patch at least doubles the coverage.
  • Time Complexity: O(m + log n)
  • Space Complexity: O(1) (uses only a few variables; does not store additional data structures).

Summary

The "Patching Array" problem is elegantly solved by greedily tracking the smallest number we cannot form and extending our coverage optimally at each step. Instead of brute-forcing all subset sums, we use the insight that either the next number in nums or a patch can maximize the range of numbers we can form. This approach is both efficient and minimal, ensuring the fewest patches are added.

Code Implementation

class Solution:
    def minPatches(self, nums, n):
        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 patches
      

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        long miss = 1;
        int i = 0, patches = 0;
        while (miss <= n) {
            if (i < nums.size() && nums[i] <= miss) {
                miss += nums[i];
                ++i;
            } else {
                miss += miss;
                ++patches;
            }
        }
        return patches;
    }
};
      

class Solution {
    public 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;
    }
}
      

var minPatches = function(nums, n) {
    let 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;
};