Jobs

Interviews

Discussions

Patching Array

Hard

Patching Array

Hard

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the upper bounds for the values in the `nums` array and the value of `n`?
If the input array is empty, what should I return?
Is the input array strictly sorted in ascending order, or can it contain equal consecutive numbers?
If `n` is less than or equal to the largest number in the array, do I still need to ensure all numbers from 1 to `n` are expressible as a sum?
Can the input array `nums` contain the number 0?

Brute Force Solution

Approach

The brute force method for patching an array involves meticulously testing every possible combination of additional numbers. We check if each combination allows us to form all numbers within the required range. It is like trying every single possible set of extra ingredients to ensure you can create any dish on the menu.

Here's how the algorithm would work step-by-step:

Begin with no extra numbers added to the original list.
Check if every number from 1 up to the target number can be formed by adding numbers from the list (including the original numbers).
If not, then add one extra number to the list, trying every number from 1 to the target number as the added number.
For each of these new lists, again check if every number from 1 to the target number can be formed.
If not, add two extra numbers to the list, trying all possible pairs of numbers from 1 to the target number.
Repeat the process of checking and adding numbers until you find a list where every number from 1 up to the target number can be formed.
The number of extra numbers added represents the minimum number needed to patch the array.

Code Implementation

def patching_array_brute_force(numbers, target_number):

    number_of_patches = 0
    while True:
        can_form_all_numbers = True
        for current_number in range(1, target_number + 1):
            if not can_form_number(numbers, current_number):
                can_form_all_numbers = False
                break

        if can_form_all_numbers:
            return number_of_patches

        # We need to add a number to the array and increment the number of patches
        number_of_patches += 1
        found_patch = False
        for potential_patch in range(1, target_number + 1):
            new_numbers = numbers + [potential_patch]
            can_form_all_numbers_with_patch = True
            for current_number in range(1, target_number + 1):
                if not can_form_number(new_numbers, current_number):
                    can_form_all_numbers_with_patch = False
                    break

            if can_form_all_numbers_with_patch:
                return number_of_patches

        #If no single patch worked, add the smallest missing number.
        smallest_missing = 1
        while can_form_number(numbers, smallest_missing):
            smallest_missing += 1
        numbers.append(smallest_missing)

def can_form_number(numbers, target_number):
    if target_number == 0:
        return True

    if not numbers:
        return False

    # Check if the target number is directly in the list
    if target_number in numbers:
        return True

    # Check all possible sums to see if it matches target_number
    for i in range(1 << len(numbers)):
        current_sum = 0
        for j in range(len(numbers)):
            if (i >> j) & 1:
                current_sum += numbers[j]

        if current_sum == target_number:
            return True

    return False

Big(O) Analysis

Time Complexity

O(target^(k+1)) – The brute force approach iteratively adds numbers to the array until all numbers from 1 to the target can be formed. In the worst case, we might need to add k numbers, where k is the minimum number of patches. For each k, we iterate through all possible combinations of k numbers within the range of 1 to target. The number of combinations to check for each k increases exponentially with the target value. Therefore, the time complexity can be approximated as O(target^(k+1)).

Space Complexity

O(N^K) – The brute force approach described potentially generates numerous temporary lists to test different combinations of added numbers. In the worst case, if we need to add K numbers (where K could be up to target - len(nums)), and each number can be any value from 1 to the target, we might explore combinations like (1,1), (1,2), ..., (target, target). For each combination, a new list of size N+K (where N is the size of original array and K is the number of added numbers) is potentially created to check if the sum is acheivable. Because the number of combinations grows exponentially with K, the space complexity is O(N^K), where N here represent the target value, and K represents the number of patched values.

Optimal Solution

Approach

We want to find the fewest numbers to add to a given list so we can form every sum from 1 up to a target number. The trick is to keep track of the largest sum we can currently form and cleverly add new numbers to extend this range as much as possible with each addition. By strategically patching the gaps, we ensure we can reach the target sum with the fewest patches.

Here's how the algorithm would work step-by-step:

Keep track of the largest sum we can make using the numbers we already have.
If the next number in the given list is smaller than or equal to the largest sum plus one, we can add it to our sum, extending our range.
If the next number in the given list is larger than the largest sum plus one, it leaves a gap that we must 'patch' by adding the number 'largest sum plus one' to the list.
Every time we add a patch, we increase our 'largest sum' by that amount.
Keep adding the numbers from the list or patching until we reach our target sum.
The total number of patches added is the answer.

Code Implementation

def patching_array(numbers, target_sum):
    patches_added = 0
    reachable_sum = 0
    array_index = 0

    while reachable_sum < target_sum:
        # If current num <= reachable, extend range
        if array_index < len(numbers) and numbers[array_index] <= reachable_sum + 1:
            reachable_sum += numbers[array_index]
            array_index += 1
        else:
            # Need to add a patch to extend range
            reachable_sum += reachable_sum + 1
            patches_added += 1

    return patches_added

Big(O) Analysis

Time Complexity

O(n) – The primary driver of the time complexity is iterating through the input array nums, which has a length we can denote as n. The while loop continues as long as the current largest sum (reach) is less than the target n. Inside this while loop, we either advance through the nums array, or we increment the patches. Both of these actions increment their respective counters (i or patches). Since we're advancing at most n times across nums and incrementing reach towards n via the patching process, the overall number of iterations is bounded by operations proportional to the target value of n and the number of elements in nums. Therefore the time complexity approximates to O(n).

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. It keeps track of the largest sum formed so far and the number of patches added using scalar variables. The plain English explanation doesn't suggest creating any temporary lists, hash maps, or other data structures that would scale with the size of the input array or the target. Thus, the auxiliary space is independent of the input size and remains constant.

Edge Cases

Case	How to Handle
Null or empty input array	If the input array is null or empty, patching is needed from 1 to n, so return the number of patches required to reach n.
n is zero	If n is zero, no patches are required, so return 0.
Array already covers the range 1 to n	If the sum of elements can already form any number from 1 to n, return 0 patches.
Large n and small values in nums	This requires many patches and should still be handled efficiently by the algorithm, without causing integer overflow, by using a long for the covered range.
Input array contains very large numbers (close to max int)	Ensure that additions of nums[i] to the covered range do not cause integer overflow by using a long for the covered range.
nums is sorted in reverse order	The provided solution iterates through the array and automatically adjusts for this, so no additional handling is needed.
nums contains a 0	Since the problem states nums contains positive integers, a zero would violate problem constraints and error checking might be needed or the zero ignored.
nums contains duplicate numbers	Duplicates in the array are fine, as they may contribute to forming sums within the target range, and the algorithm correctly adds them to the running sum.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the upper bounds for the values in the `nums` array and the value of `n`?
If the input array is empty, what should I return?
Is the input array strictly sorted in ascending order, or can it contain equal consecutive numbers?
If `n` is less than or equal to the largest number in the array, do I still need to ensure all numbers from 1 to `n` are expressible as a sum?
Can the input array `nums` contain the number 0?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Begin with no extra numbers added to the original list.
Check if every number from 1 up to the target number can be formed by adding numbers from the list (including the original numbers).
If not, then add one extra number to the list, trying every number from 1 to the target number as the added number.
For each of these new lists, again check if every number from 1 to the target number can be formed.
If not, add two extra numbers to the list, trying all possible pairs of numbers from 1 to the target number.
Repeat the process of checking and adding numbers until you find a list where every number from 1 up to the target number can be formed.
The number of extra numbers added represents the minimum number needed to patch the array.

Code Implementation

def patching_array_brute_force(numbers, target_number):

    number_of_patches = 0
    while True:
        can_form_all_numbers = True
        for current_number in range(1, target_number + 1):
            if not can_form_number(numbers, current_number):
                can_form_all_numbers = False
                break

        if can_form_all_numbers:
            return number_of_patches

        # We need to add a number to the array and increment the number of patches
        number_of_patches += 1
        found_patch = False
        for potential_patch in range(1, target_number + 1):
            new_numbers = numbers + [potential_patch]
            can_form_all_numbers_with_patch = True
            for current_number in range(1, target_number + 1):
                if not can_form_number(new_numbers, current_number):
                    can_form_all_numbers_with_patch = False
                    break

            if can_form_all_numbers_with_patch:
                return number_of_patches

        #If no single patch worked, add the smallest missing number.
        smallest_missing = 1
        while can_form_number(numbers, smallest_missing):
            smallest_missing += 1
        numbers.append(smallest_missing)

def can_form_number(numbers, target_number):
    if target_number == 0:
        return True

    if not numbers:
        return False

    # Check if the target number is directly in the list
    if target_number in numbers:
        return True

    # Check all possible sums to see if it matches target_number
    for i in range(1 << len(numbers)):
        current_sum = 0
        for j in range(len(numbers)):
            if (i >> j) & 1:
                current_sum += numbers[j]

        if current_sum == target_number:
            return True

    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Keep track of the largest sum we can make using the numbers we already have.
If the next number in the given list is smaller than or equal to the largest sum plus one, we can add it to our sum, extending our range.
If the next number in the given list is larger than the largest sum plus one, it leaves a gap that we must 'patch' by adding the number 'largest sum plus one' to the list.
Every time we add a patch, we increase our 'largest sum' by that amount.
Keep adding the numbers from the list or patching until we reach our target sum.
The total number of patches added is the answer.

Code Implementation

def patching_array(numbers, target_sum):
    patches_added = 0
    reachable_sum = 0
    array_index = 0

    while reachable_sum < target_sum:
        # If current num <= reachable, extend range
        if array_index < len(numbers) and numbers[array_index] <= reachable_sum + 1:
            reachable_sum += numbers[array_index]
            array_index += 1
        else:
            # Need to add a patch to extend range
            reachable_sum += reachable_sum + 1
            patches_added += 1

    return patches_added

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	If the input array is null or empty, patching is needed from 1 to n, so return the number of patches required to reach n.
n is zero	If n is zero, no patches are required, so return 0.
Array already covers the range 1 to n	If the sum of elements can already form any number from 1 to n, return 0 patches.
Large n and small values in nums	This requires many patches and should still be handled efficiently by the algorithm, without causing integer overflow, by using a long for the covered range.
Input array contains very large numbers (close to max int)	Ensure that additions of nums[i] to the covered range do not cause integer overflow by using a long for the covered range.
nums is sorted in reverse order	The provided solution iterates through the array and automatically adjusts for this, so no additional handling is needed.
nums contains a 0	Since the problem states nums contains positive integers, a zero would violate problem constraints and error checking might be needed or the zero ignored.
nums contains duplicate numbers	Duplicates in the array are fine, as they may contribute to forming sums within the target range, and the algorithm correctly adds them to the running sum.