330. Patching Array

Intuition

Greedily maintain the range [1, reach] that can be formed from the current elements. If nums[i] <= reach+1, it extends reach to reach+nums[i]. Otherwise, patch by adding reach+1 to the array, doubling reach.

Algorithm

1reach=0, patches=0, i=0.
2While reach < n: if i < nums.Length and nums[i] <= reach+1: reach += nums[i]; i++.
3Else: reach += reach+1 (patch); patches++.
4Return patches.

Example Walkthrough

Input: nums = [1,3], n = 6

1.reach=0. nums[0]=1<=1: reach=1.
2.nums[1]=3<=2? No. Patch: add 2, reach=3. patches=1.
3.nums[1]=3<=4: reach=6.
4.reach=6 >= n=6. Done. patches=1.

Output: 1

Common Pitfalls

•When patching, always add reach+1 (the smallest uncoverable number) - this maximally extends reach.

330.cs

// Approach: Greedy interval extension — track 'maxReach', the maximum sum reachable
// using elements already considered (starts at 0, meaning we can form sums [1..maxReach]).
// Iterate through nums: if nums[i] <= maxReach + 1, extend maxReach by nums[i].
// If nums[i] > maxReach + 1, there is a gap — patch by adding (maxReach + 1), doubling maxReach + 1.
// Count each patch; stop when maxReach >= n.
// The key insight: after processing or patching, maxReach always represents the upper bound of [1..maxReach] coverage.
// Time: O(log n + len(nums)) Space: O(1).

public class Solution {
    public int MinPatches(int[] nums, int n) {
        long minPatch = 0, maxNum = 0;
        int i = 0, sz = nums.Length;

        while(maxNum < n)
        {
            if(i < sz && maxNum + 1 >= nums[i])
            {
                maxNum += nums[i];
                i++;
            }
            else
            {
                minPatch++;
                maxNum += (maxNum + 1);
            }
        }

        return (int)minPatch;
    }
}

Was this solution helpful?