We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Patching Array

Number: 330

Difficulty: Hard

Paid? No

Companies: Uber, Google, Meta, Amazon, Flipkart

Problem Description

Given a sorted integer array and an integer n, we need to find the minimum number of additional numbers (patches) required so that every number in the range [1, n] can be constructed as the sum of some elements from the updated array.

Key Insights

  • Use a greedy approach to extend the achievable sum range.
  • Maintain a variable (maxReach) to represent the current maximum value that can be formed from sums of the array.
  • If the current array element is within maxReach+1, it extends the reach. Otherwise, patch with maxReach+1 to jump the reachable range.
  • Repeat the process until the reachable sum exceeds n.

Space and Time Complexity

Time Complexity: O(m + P) where m is the length of the array and P is the number of patches added (in worst case, O(log n)). Space Complexity: O(1) – only constant extra space is used.

Solution

The solution uses a greedy algorithm that iteratively increases the reachable sum (maxReach). Start with maxReach = 0 and an index for the given array. At each step, if the next array element is within reach (<= maxReach + 1), use it to extend the range. Otherwise, add a patch (maxReach+1) to push the boundary further. This process continues until maxReach is at least n. The trick is to always patch with the smallest number that extends our reachable sum optimally, which is maxReach+1.

Code Solutions

def minPatches(nums, n):
    # Initialize variables: patches count, current reach, and index pointer
    patches = 0
    max_reach = 0
    i = 0
    # Loop until we cover all numbers up to n
    while max_reach < n:
        # If there are remaining elements and the current element is <= max_reach+1, use it.
        if i < len(nums) and nums[i] <= max_reach + 1:
            # Extend reach by current number
            max_reach += nums[i]
            # Move to next element in nums
            i += 1
        else:
            # Patch: add max_reach+1 to extend the range
            max_reach += (max_reach + 1)
            patches += 1
    return patches

# Example usage:
print(minPatches([1, 3], 6))  # Output: 1
← Back to All Questions