Skip to main content
Talentd

Patching Array - Solution & Explanation

HardArrayGreedy17 min readAsked at: Amazon, Meta, Uber +1
Practice this problem

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

 

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 104
  • nums is sorted in ascending order.
  • 1 <= n <= 231 - 1

Approach Overview

Problem Overview: You receive a sorted array nums and an integer n. The goal is to add the minimum number of integers (patches) so every number in the range [1, n] can be formed as a sum of elements from the array. Each number can be used once per sum.

Approach 1: Exhaustive Coverage Check (Brute Force) (Time: O(2^n) to generate sums, Space: O(2^n))

A straightforward idea is to track every possible subset sum that can be formed from the current array. After computing all reachable sums, scan the range [1, n] to find missing values. Whenever a gap appears, add that number as a patch and recompute the reachable sums. This guarantees correctness because every missing value is explicitly patched, but generating subset sums grows exponentially. Even with pruning or a hash set, the solution quickly becomes infeasible for large inputs. This approach mainly demonstrates the problem structure rather than serving as a practical solution.

Approach 2: Greedy Patching (Time: O(m + k), Space: O(1))

The optimal solution relies on a greedy coverage insight. Suppose you can already form every value in the range [1, miss). If the next array element nums[i] is ≤ miss, you can extend the reachable range to [1, miss + nums[i]) by including it in sums. If nums[i] is greater than miss, a gap appears because miss cannot be formed. The best patch is exactly miss, which doubles the coverage to [1, 2 * miss). Repeat this process until the coverage exceeds n. This greedy rule works because adding the smallest missing value maximizes the expansion of reachable sums with the fewest patches. The algorithm iterates once through the array while maintaining a running coverage boundary.

The logic fits naturally with problems involving sorted arrays and interval expansion using greedy decisions. Instead of tracking individual sums, you track the largest continuous range of sums that can already be built.

Recommended for interviews: Interviewers expect the greedy coverage approach. Brute force shows you understand the subset‑sum interpretation, but the greedy insight demonstrates algorithmic maturity. Recognizing that maintaining the reachable range [1, miss) eliminates the need for subset enumeration is the key step that leads to the optimal O(n) solution.

Approach 1: Greedy Patching Approach

This 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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Greedy

Let's assume that the number x is the smallest positive integer that cannot be represented. Then all the numbers in [1,..x-1] can be represented. In order to represent the number x, we need to add a number that is less than or equal to x:

  • If the added number equals x, since all numbers in [1,..x-1] can be represented, after adding x, all numbers in the range [1,..2x-1] can be represented, and the smallest positive integer that cannot be represented becomes 2x.
  • If the added number is less than x, let's assume it's x', since all numbers in [1,..x-1] can be represented, after adding x', all numbers in the range [1,..x+x'-1] can be represented, and the smallest positive integer that cannot be represented becomes x+x' \lt 2x.

Therefore, we should greedily add the number x to cover a larger range.

We use a variable x to record the current smallest positive integer that cannot be represented, initialized to 1. At this time, [1,..x-1] is empty, indicating that no number can be covered; we use a variable i to record the current index of the array being traversed.

We perform the following operations in a loop:

  • If i is within the range of the array and nums[i] \le x, it means that the current number can be covered, so we add the value of nums[i] to x, and increment i by 1.
  • Otherwise, it means that x is not covered, so we need to supplement a number x in the array, and then update x to 2x.
  • Repeat the above operations until the value of x is greater than n.

The final answer is the number of supplemented numbers.

The time complexity is O(m + log n), where m is the length of the array nums. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Patching Approach

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.

Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Subset Sum Enumeration (Brute Force)O(2^n)O(2^n)Conceptual understanding of all possible sums; impractical for real constraints
Greedy Coverage ExpansionO(m + k)O(1)Optimal solution when the array is sorted and you need minimal patches

Video Solution

Patching Array | Thought Process | Dry Runs | GOOGLE | Leetcode 330 | codestorywithMIK • codestorywithMIK • 15,165 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Patching Array easy or hard?
Patching Array is labeled Hard because the greedy insight is not immediately obvious. Many candidates initially attempt subset-sum or dynamic programming approaches. Recognizing that tracking a continuous coverage range eliminates the need for explicit sum generation is the key challenge.
Patching Array Python/Java solution
The Python or Java implementation follows the same logic: maintain a variable `miss`, iterate through the array, and either extend coverage with the current number or add a patch equal to `miss`. This results in an O(n) greedy algorithm with constant extra space.
How to solve Patching Array in O(n)?
Track the smallest missing sum `miss` that cannot be formed yet. If the next element in the sorted array is ≤ miss, add it to extend coverage. If it is larger, insert a patch equal to miss, doubling the reachable range. Continue until miss exceeds n.
What is the best approach for Patching Array?
The greedy coverage expansion approach is the optimal solution. Maintain the smallest missing value `miss` that cannot yet be formed. If the next array value is ≤ miss, extend coverage; otherwise patch with `miss`. This expands the reachable range efficiently and minimizes the number of patches.
Is Patching Array asked at Google/Amazon/Meta?
Patching Array is considered a classic greedy interview problem and has appeared in interviews and preparation lists for companies like Google, Amazon, and Meta. It tests the ability to recognize range coverage and apply greedy reasoning instead of brute force subset generation.
What data structure is used in Patching Array?
The optimal solution does not require complex data structures. It uses a simple variable to track the current coverage boundary and iterates through the input array. The problem mainly relies on greedy reasoning rather than specialized structures.
What is the time complexity of Patching Array?
The optimal greedy solution runs in O(m + k) time, where m is the length of the input array and k is the number of patches added. Each step either consumes an array element or inserts a patch, so the algorithm processes elements in a single pass. Space complexity is O(1).

Ready to solve this problem?

Practice Patching Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Number of Consecutive Values You Can Make