330. Patching Array

Problem Description

Given a sorted integer array nums and an integer n, we need to find the minimum number of patches required to make sure that any number in the range [1, n] (inclusive) can be formed by the sum of some elements in the array.

Solution Approach: Greedy Algorithm

The solution employs a greedy approach. The core idea is to maintain a reach variable. reach represents the largest number we can currently form using the existing elements in nums and any patches added so far. We iterate through the nums array and the process is as follows:

1. Initialization: Start with reach = 0 and patches = 0.

2. Iteration:

   • If the current element nums[i] is less than or equal to reach + 1, it means we can extend our reach. We update reach to reach + nums[i]. We can form all numbers up to reach.
   • If nums[i] is greater than reach + 1, it means there's a gap. We need to add a patch of size reach + 1 to cover this gap. This extends our reach to reach + reach + 1 = 2 * reach + 1. We increment patches.

3. Termination: The loop continues until reach becomes greater than or equal to n. At this point, we can form all numbers in the range [1, n], and the value of patches represents the minimum number of patches needed.

Time and Space Complexity Analysis

• Time Complexity: O(m + log n), where m is the length of nums. The algorithm iterates through nums once, and the while loop's iterations are bounded by the logarithmic growth of reach.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space.

Code Implementation (Python)

class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        patches = 0
        reach = 0
        i = 0
        while reach < n:
            if i < len(nums) and nums[i] <= reach + 1:
                reach += nums[i]
                i += 1
            else:
                patches += 1
                reach += reach + 1  # Add a patch of size reach + 1
        return patches
 

Code Implementation (Java)

class Solution {
    public int minPatches(int[] nums, int n) {
        int patches = 0;
        long reach = 0; // Use long to avoid integer overflow
        int i = 0;
        while (reach < n) {
            if (i < nums.length && nums[i] <= reach + 1) {
                reach += nums[i];
                i++;
            } else {
                patches++;
                reach += reach + 1;
            }
        }
        return patches;
    }
}

Code Implementation (C++)

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

Note that in Java and C++, long or long long are used for reach to prevent potential integer overflow issues, especially when n is large. The Python implementation implicitly handles large integers. The logic remains consistent across all languages.