Patching Array

Patching Array

What is this problem about?

The Patching Array problem asks for the minimum number of elements to add to a sorted array such that you can represent every integer in [1, n] as the sum of some subset of the array. This hard coding problem uses a greedy approach based on the "reachable range" concept. The array and greedy interview pattern is the core.

Why is this asked in interviews?

Uber, Microsoft, Meta, Amazon, TikTok, and Google ask this hard greedy problem because the key insight — maintaining the range [1, reach) that you can form with current elements — is non-obvious. The greedy decision to add reach (the next missing number) when needed is elegant.

Algorithmic pattern used

Greedy reachable range extension. Maintain reach = the smallest number not yet representable. Initially reach=1. For each element arr[i]: if arr[i] <= reach, extend reach to reach + arr[i] (all numbers up to new reach are now reachable). Else: there's a gap — add reach to the array (patch++), extend reach to 2*reach. Repeat until reach > n.

Example explanation

arr=[1,5,10], n=20.

• reach=1. arr[0]=1 ≤ 1: reach=2.
• arr[1]=5 > 2: patch! Add 2. reach=4.
• arr[1]=5 > 4: patch! Add 4. reach=8.
• arr[1]=5 ≤ 8: reach=13.
• arr[2]=10 ≤ 13: reach=23>20. Done. Answer = 2 patches.

Common mistakes candidates make

• Not recognizing that adding reach (not some arbitrary number) is optimal.
• Processing array elements out of order.
• Not handling gaps in the array correctly.
• Terminating when reach > n (correct) vs continuing unnecessarily.

Interview preparation tip

Patching Array is one of the hardest greedy problems to derive from scratch. The "reachable range" invariant — "with current elements and patches, I can form all numbers in [1, reach)" — is the key. Greedily add the next gap-filling element (reach itself) when a gap is found. Practice deriving greedy invariants on paper before coding. This problem is a strong differentiator at top companies.