330. Patching Array LeetCode Solution

Last updated: February 17, 2025

In this guide, you will get 330. Patching Array LeetCode Solution with the best time and space complexity. The solution to Patching Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Patching Array solution in C++
Patching Array solution in Java
Patching Array solution in Python
Additional Resources

330. Patching Array LeetCode Solution image

Problem Statement of Patching Array

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] <= 104
nums is sorted in ascending order.
1 <= n <= 231 – 1

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

330. Patching Array LeetCode Solution in C++

class Solution {
 public:
  int minPatches(vector<int>& nums, int n) {
    int ans = 0;
    int i = 0;      // nums' index
    long miss = 1;  // the minimum sum in [1, n] we might miss

    while (miss <= n)
      if (i < nums.size() && nums[i] <= miss) {
        miss += nums[i++];
      } else {
        // Greedily add `miss` itself to increase the range from
        // [1, miss) to [1, 2 * miss).
        miss += miss;
        ++ans;
      }

    return ans;
  }
};
/* code provided by PROGIEZ */

330. Patching Array LeetCode Solution in Java

class Solution {
  public int minPatches(int[] nums, int n) {
    int ans = 0;
    int i = 0;     // nums' index
    long miss = 1; // the minimum sum in [1, n] we might miss

    while (miss <= n)
      if (i < nums.length && nums[i] <= miss) {
        miss += nums[i++];
      } else {
        // Greedily add `miss` itself to increase the range from
        // [1, miss) to [1, 2 * miss).
        miss += miss;
        ++ans;
      }

    return ans;
  }
}
// code provided by PROGIEZ

330. Patching Array LeetCode Solution in Python

class Solution:
  def minPatches(self, nums: list[int], n: int) -> int:
    ans = 0
    i = 0  # nums' index
    miss = 1  # the minimum sum in [1, n] we might miss

    while miss <= n:
      if i < len(nums) and nums[i] <= miss:
        miss += nums[i]
        i += 1
      else:
        # Greedily add `miss` itself to increase the range from
        # [1, miss) to [1, 2 * miss).
        miss += miss
        ans += 1

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents