330. Patching Array

Difficulty: Hard

Topics: Array, Greedy

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 <= 1000
1 <= nums[i] <= 10⁴
nums is sorted in ascending order.
1 <= n <= 2³¹ - 1
Only one valid answer exists.

Solution:

We need to ensure that every number in the range [1, n] can be formed by the sum of some elements in the given array. We can use a greedy algorithm to determine the minimum number of patches required.

Solution Explanation:

Key Insight:
- Start with the smallest missing number miss which starts at 1.
- Iterate through the array nums. If the current number in nums is less than or equal to miss, then miss can be covered by adding this number. Otherwise, we need to patch miss to the array, effectively doubling the range that can be covered.
Algorithm:
- Initialize miss = 1 and patches = 0.
- Loop through the array while miss <= n:
  - If the current number in nums can cover miss, move to the next number in nums.
  - If the current number is greater than miss, patch miss and double the range covered by setting miss = miss * 2.
- Continue until the entire range [1, n] is covered.
Complexity:
- The time complexity is O(m + log n), where m is the size of the array nums.

Let's implement this solution in PHP: 330. Patching Array

<?php
/**
* @param String $n
* @return String
*/
function minPatches($nums, $n) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:

// Example 1
$nums1 = [1, 3];
$n1 = 6;
echo minPatches($nums1, $n1); // Output: 1

// Example 2
$nums2 = [1, 5, 10];
$n2 = 20;
echo minPatches($nums2, $n2); // Output: 2

// Example 3
$nums3 = [1, 2, 2];
$n3 = 5;
echo minPatches($nums3, $n3); // Output: 0
?>

Explanation:

Initial Setup: We initialize miss as 1, meaning we want to ensure we can generate the number 1.
While Loop: We loop until miss exceeds n (the maximum number we need to cover). In each iteration:
- If the current number in nums can help cover miss, we add it to miss and move to the next number.
- If not, we "patch" the array by effectively adding miss to it (without changing the array itself) and then update miss to cover the new range.
Output: The total number of patches required is returned.

This algorithm ensures that we cover the entire range [1, n] with the minimum number of patches.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub