Last updated on January 14th, 2025 at 06:19 am
Here, we see a Patching Array LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Greedy
Companies
Level of Question
Hard
Patching Array LeetCode Solution
Table of Contents
1. Problem Statement
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
2. Coding Pattern Used in Solution
The coding pattern used in this problem is “Greedy Algorithm”. The goal is to iteratively ensure that all numbers up to n can be formed using the given array nums and the minimum number of patches (new numbers added). The algorithm greedily adds the smallest missing number (miss) to cover the range of numbers that cannot yet be formed.
3. Code Implementation in Different Languages
3.1 Patching Array C++
class Solution {
public:
int minPatches(vector<int>& nums, int n) {
int len = nums.size();
int sum = 0;
int patch = 0;
int count = 0;
while (sum < n) {
if (count != len && nums[count] <= sum + 1) {
sum += nums[count];
count ++;
}
else {
patch ++;
if (sum > (INT_MAX - 1) / 2) {
sum = INT_MAX;
}
else {
sum = sum * 2 + 1;
}
}
}
return patch;
}
};
3.2 Patching Array Java
class Solution {
public int minPatches(int[] nums, int n) {
int count = 0;
long priorSum = 0;
for(int i=0; i<nums.length; i++) {
if(priorSum>=n) return count;
while(priorSum<n && nums[i]>priorSum+1) {
++count;
priorSum = (priorSum<<1) + 1;
}
priorSum += nums[i];
}
while(priorSum<n) {
++count;
priorSum = (priorSum<<1) + 1;
}
return count;
}
}
3.3 Patching Array JavaScript
var minPatches = function(nums, n) {
var covered=1,count=0,i=0;
while(covered<=n){
if(i>=nums.length||covered<nums[i]){
count++;
covered+=covered;
}else covered+=nums[i++];
}
return count;
};
3.4 Patching Array Python
class Solution(object):
def minPatches(self, nums, n):
miss, i, added = 1, 0, 0
while miss <= n:
if i < len(nums) and nums[i] <= miss:
miss += nums[i]
i += 1
else:
miss += miss
added += 1
return added
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(m + log(n)) | O(1) |
| Java | O(m + log(n)) | O(1) |
| JavaScript | O(m + log(n)) | O(1) |
| Python | O(m + log(n)) | O(1) |