Patching Array

Hard
1456.

Patching Array

Patching Array is a hard coding problem on arrays and greedy, asked in Amazon and Google interviews.

You are given a sorted array of positive integers nums and an integer n. You may patch the array by inserting any positive integer into it.

Return the minimum number of patches needed so that every integer in the range [1, n] can be written as the sum of some elements of the array (each element used at most once).

Example 1

Input
nums = [2,4], n = 10
Output
2
Explanation
Adding 1 makes every value up to 7 reachable; adding 8 then covers 8 to 15.

Example 2

Input
nums = [1,2,2], n = 5
Output
0
Explanation
1, 2, 1+2, 2+2 and 1+2+2 already cover 1 to 5.

Example 3

Input
nums = [3,7], n = 50
Output
4
Explanation
Patch 1, 2, 14 and 28.

Constraints

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 10^4
  • nums is sorted in ascending order
  • 1 <= n <= 2^31 - 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} n
 * @return {number}
 */
var minPatches = function(nums, n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Patching Array — Solution in Python, Java & C++

Patching Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.

Patching Array is a hard coding problem on arrays and greedy, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Arrays, Greedy
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a sorted array of positive integers nums and an integer n. You may patch the array by inserting any positive integer into it.

Return the minimum number of patches needed so that every integer in the range [1, n] can be written as the sum of some elements of the array (each element used at most once).

Example 1

Input: nums = [2,4], n = 10
Output: 2
Explanation: Adding 1 makes every value up to 7 reachable; adding 8 then covers 8 to 15.

Example 2

Input: nums = [1,2,2], n = 5
Output: 0
Explanation: 1, 2, 1+2, 2+2 and 1+2+2 already cover 1 to 5.

Example 3

Input: nums = [3,7], n = 50
Output: 4
Explanation: Patch 1, 2, 14 and 28.

Constraints

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 10^4
  • nums is sorted in ascending order
  • 1 <= n <= 2^31 - 1

Hints for Patching Array

  1. Hint 1

    Suppose every value in [1, reach] can already be formed. What happens when you add a number x <= reach + 1?

  2. Hint 2

    Then every value up to reach + x can be formed. If the next array element is larger than reach + 1, the value reach + 1 can never be formed without a patch.

  3. Hint 3

    Patch with exactly reach + 1 — it doubles the covered range, the most any single patch can do.

How to solve Patching Array

Track the prefix [1, reach] of values that can be formed. An element x <= reach + 1 extends it to reach + x; when the next element is too big, the gap reach + 1 must be patched, and patching exactly reach + 1 extends the range the furthest.

Approach

  1. Start with miss = 1 (the smallest value not yet formable), index i = 0 and patches = 0. Use 64-bit arithmetic: miss can exceed 2^31.
  2. While miss <= n: if i is in range and nums[i] <= miss, set miss += nums[i] and advance i.
  3. Otherwise patch with miss itself: miss += miss and count a patch.
  4. Return patches.

Why it works

If every value below miss is formable and we add x <= miss, every value below miss + x becomes formable (old sums, plus x added to them). If the next element exceeds miss, no subset of the remaining elements can form miss, so some patch p <= miss is required, and p = miss gives the largest new range [1, 2·miss). Any optimal solution can be exchanged for this one without needing more patches.

Complexity

  • Time — O(len(nums) + log n)
  • Space — O(1)

Pitfalls

  • miss can reach about 2^32 when n is near 2^31 - 1 — use a 64-bit counter.
  • Use the array elements whenever they fit; patching is only for real gaps.
  • Elements larger than n are simply never needed.

Reference solution

Python

from typing import List

def minPatches(nums: List[int], n: int) -> int:
    miss = 1
    i = 0
    patches = 0
    while miss <= n:
        if i < len(nums) and nums[i] <= miss:
            miss += nums[i]
            i += 1
        else:
            miss += miss
            patches += 1
    return patches

Java

public static int minPatches(int[] nums, int n) {
    long miss = 1;
    int i = 0, patches = 0;
    while (miss <= n) {
        if (i < nums.length && nums[i] <= miss) { miss += nums[i]; i++; }
        else { miss += miss; patches++; }
    }
    return patches;
}

C++

int minPatches(vector<int>& nums, int n) {
    long long miss = 1;
    int i = 0, patches = 0;
    while (miss <= n) {
        if (i < (int)nums.size() && nums[i] <= miss) { miss += nums[i]; i++; }
        else { miss += miss; patches++; }
    }
    return patches;
}

JavaScript

var minPatches = function(nums, n) {
    var miss = 1, i = 0, patches = 0;
    while (miss <= n) {
        if (i < nums.length && nums[i] <= miss) { miss += nums[i]; i++; }
        else { miss += miss; patches++; }
    }
    return patches;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms