Course4all
Join us on telegram
Home/dsa/Greedy/Patching Array

Patching Array

Master this topic with zero to advance depth.

Patching Array

Add minimum elements to a sorted array so all numbers in [1, n] can be formed by sums.

Visual Representation

nums = [1, 3], n = 6 Reach: [1, 1] (via 1) Next miss: 2. nums[i]=3 > 2. PATCH 2. Reach: [1, 3] (via 1, 2) Next miss: 4. nums[i]=3 <= 4. Use 3. Reach: [1, 6] (via 1, 2, 3) Done. Patches: 1
Hard

Examples

Input: nums = [1,3], n = 6
Output: 1

Adding 2 allows forming sums up to 6.

Approach 1

Level I: Brute Force (Recursion / Subsets)

Intuition

Try all possible combinations of patches (numbers from 1 to n) and check if each subset sum can form all numbers in [1, n]. This is extremely slow but guaranteed to find the minimum patches.

Thought Process

  1. isPossible(current_nums, n): Checks if all numbers in [1, n] can be formed.
  2. solve(current_nums, count): Recursively tries adding each possible number p that is not in current_nums.
  3. Return the minimum count such that isPossible is true.
⏱ O(2^n * n^2) roughly.💾 O(n)

Detailed Dry Run

nums = [1, 3], n = 6

  1. isPossible([1, 3], 6)? No (cannot form 2).
  2. Try adding 2: [1, 2, 3]. sums: 1, 2, 3, 4(1+3), 5(2+3), 6(1+2+3). YES. Min patches = 1.
java
// Brute Force: Exponential complexity
// 1. Generate all power sets of [1, n].
// 2. Check each subset to see if it covers [1, n].
// 3. Return the smallest subset size minus original array size.
Approach 2

Level II: Dynamic Programming (Boolean Knapsack)

Intuition

Treat this as a variation of the Subset Sum problem. For a given set of numbers, maintain a boolean array can_form where can_form[i] is true if sum i can be reached.

Thought Process

  1. dp[i] = true if sum i is possible.
  2. Start with original nums. Update dp for each number.
  3. If dp[miss] is false for some miss <= n, we must add a patch.
  4. Greedy choice for patch is always the smallest missing number to maximize coverage.
⏱ O(N * n) where N is array size and n is target.💾 O(n)

Detailed Dry Run

nums = [1, 3], n = 6, dp=[T, F, F, F, F, F, F] (dp[0]=T)

  1. Use 1: dp=[T, T, F, F, F, F, F]
  2. Use 3: dp=[T, T, F, T, T, F, F]
  3. Miss = 2. Patch 2.
  4. Use 2: dp=[T, T, T, T, T, T, T]. DONE.
java
public class Solution {
    public int minPatches(int[] nums, int n) {
        // DP-based simulation to check reachability
        // This still requires a greedy choice for *which* number to patch.
        return -1; 
    }
}
Approach 3

Level III: Optimal Greedy (Reachability Range)

Intuition

Maintain the smallest number miss that cannot be formed. If nums[i] <= miss, use it to extend the range. Otherwise, patch miss to double the reach.

Thought Process

  1. miss = current gap.
  2. If nums[i] <= miss: miss += nums[i++].
  3. Else: miss += miss, count++.

Pattern: Greedy Range Extension

⏱ O(M + log N).💾 O(1).

Detailed Dry Run

nums = [1, 5, 10], n = 20 miss=1: Use 1, miss=2 miss=2: nums[1]=5 > 2. Patch 2, miss=4 miss=4: nums[1]=5 > 4. Patch 4, miss=8 miss=8: Use 5, miss=13 miss=13: Use 10, miss=23. DONE.

java
public class Solution {
    public int minPatches(int[] nums, int n) {
        long miss = 1; int patches = 0, i = 0;
        while (miss <= n) {
            if (i < nums.length && nums[i] <= miss) miss += nums[i++];
            else {
                miss += miss;
                patches++;
            }
        }
        return patches;
    }
}
← Previous QuestionMinimum Cost to Connect Sticks
Next Question →Reorganize String