LeetCode 330: Patching Array

Explanation

To solve this problem, we need to iteratively build up the range [1, n] using the existing elements in the array nums. We can do this by keeping track of the maximum reachable value reachable from the elements we have processed so far. If the next element in nums is greater than reachable + 1, we need to add a patch to the array to cover the gap between reachable + 1 and the next element. By adding a patch, we can extend the range that can be formed by summing the elements in the array.

Algorithm

1. Initialize the variables patchCount to 0, reachable to 0, and index to 0.
2. While reachable is less than n, check if the current element in nums at index index is less than or equal to reachable + 1. If it is, update reachable to reachable + nums[index] and move to the next element.
3. If the current element in nums is greater than reachable + 1, increment patchCount, add reachable + 1 to the array, and update reachable to 2 * reachable + 1.
4. Repeat steps 2 and 3 until reachable is greater than or equal to n.
5. Return the patchCount.

Time Complexity

The time complexity of this algorithm is O(log(n)) since the number of patches required grows logarithmically with n.

Space Complexity

The space complexity is O(1) as we are using only a constant amount of extra space.

class Solution {
    public int minPatches(int[] nums, int n) {
        long reachable = 0;
        int patchCount = 0;
        int index = 0;

        while (reachable < n) {
            if (index < nums.length && nums[index] <= reachable + 1) {
                reachable += nums[index];
                index++;
            } else {
                patchCount++;
                reachable = 2 * reachable + 1;
            }
        }

        return patchCount;
    }
}