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.
Example 1:
Input: nums = [1,3], n = 6 Output: 1 Explanation: Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4. Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3]. Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6]. So we only need 1 patch.
Example 2:
Input: nums = [1,5,10], n = 20 Output: 2 Explanation: The two patches can be [2, 4].
Example 3:
Input: nums = [1,2,2], n = 5 Output: 0
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 104nums is sorted in ascending order.1 <= n <= 231 - 1This approach uses a greedy strategy to find the minimum number of patches required to cover the entire range [1, n]. Starting with a number missing initialized to 1, which represents the smallest sum we cannot form, we iterate through the array. If the current number in the array is less than or equal to missing, we increment our range to missing + nums[i]. Otherwise, we add missing to the array, effectively patching it, and increment our missing sum by itself.
The C solution first initializes the count of patches and an iterator at zero, and sets missing to 1. It then iterates until missing is greater than n. For each iteration, if the current number in nums is less than or equal to missing, missing is incremented by nums[i] and the array index is incremented. If not, it increments missing by its current value and increments the patch count.
C++
Java
Python
C#
JavaScript
Time complexity: O(m + log n) where m is the length of nums. The loop runs through nums and potentially adds new numbers until missing > n.
Space complexity: O(1), since no auxiliary space is used apart from a few variables.
Patching Array | Thought Process | Dry Runs | GOOGLE | Leetcode 330 | codestorywithMIK • codestorywithMIK • 11,311 views views
Watch 9 more video solutions →Practice Patching Array with our built-in code editor and test cases.
Practice on FleetCode