LeetCode 330: Patching Array Solution in Python – A Step-by-Step Guide

What Is LeetCode 330: Patching Array?

In LeetCode 330: Patching Array, you’re given an integer array nums (sorted, non-negative) and an integer n. Your task is to find the minimum number of patches (additional numbers) needed so that all sums from 1 to n can be formed by selecting numbers from nums and the patches, with unlimited use of each number. For example, with nums = [1,3], n = 6, you need 1 patch (2) to cover all sums up to 6. This problem tests your ability to extend a set’s coverage greedily, connecting to concepts in LeetCode 322: Coin Change.

Problem Statement

• Input: A sorted integer array nums (non-negative) and an integer n.
• Output: An integer—the minimum number of patches needed.
• Rules:
• Use numbers from nums and patches unlimited times.
• Cover all sums from 1 to n inclusive.
• Patches can be any positive integer.

Constraints

• 0 <= nums.length <= 1000
• 1 <= nums[i] <= 10⁴
• 1 <= n <= 10⁹

Examples

• Input: nums = [1,3], n = 6
• Output: 1 (Patch with 2: [1,2,3] covers 1-6)
• Input: nums = [1,5,10], n = 20
• Output: 2 (Patch with 2, 4: [1,2,4,5,10] covers 1-20)
• Input: nums = [1,2,2], n = 5
• Output: 0 (Already covers 1-5)

Understanding the Problem: Patching for Coverage

To solve LeetCode 330: Patching Array in Python, we need to determine the fewest numbers to add to nums so all sums from 1 to n are possible. A naive approach—checking all sums with combinations—is exponential in time, impractical for n up to 10⁹. Instead, we’ll use:

• Best Solution (Greedy): O(m + log n) time, O(1) space—fast and elegant (m = len(nums)).
• Alternative Solution (Brute Force): O(n * m) time, O(n) space—clear but inefficient.

Let’s start with the greedy solution, explained in a beginner-friendly way.

Best Solution: Greedy Approach

Why This Is the Best Solution

The greedy approach is the top choice for LeetCode 330 because it’s efficient—O(m + log n) time, O(1) space—and uses a clever insight: always patch with the smallest missing number to maximize coverage with minimal additions. It tracks the range of sums achievable and extends it greedily. It’s like building a ladder one rung at a time—smart and quick!

How It Works

Think of this as a coverage expander:

• Step 1: Track Missing:
• miss = smallest sum not yet covered (starts at 1).
• Step 2: Extend Range:
• If next num ≤ miss, use it to extend coverage to miss + num - 1.
• If not, patch with miss, double coverage to 2 * miss - 1.
• Step 3: Repeat Until n:
• Stop when miss > n.
• Step 4: Why It Works:
• Adding miss ensures all sums up to 2 * miss - 1 are covered (with existing numbers).
• Greedy choice minimizes patches.

It’s like filling gaps with the perfect pieces!

Step-by-Step Example

Example: nums = [1,5,10], n = 20

• Init: miss = 1, patches = 0, i = 0
• Step 1: miss = 1, nums[0] = 1
• Use 1, miss = 1+1 = 2
• Step 2: miss = 2, nums[1] = 5
• Patch 2, miss = 2+2 = 4, patches = 1
• Step 3: miss = 4, nums[1] = 5
• Patch 4, miss = 4+4 = 8, patches = 2
• Step 4: miss = 8, nums[1] = 5
• Use 5, miss = 8+5 = 13
• Step 5: miss = 13, nums[2] = 10
• Use 10, miss = 13+10 = 23 (>20)
• Result: patches = 2

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        miss = 1  # Smallest sum not covered
        patches = 0  # Number of patches
        i = 0  # Index in nums

        # Extend coverage until miss > n
        while miss <= n:
            if i < len(nums) and nums[i] <= miss:
                miss += nums[i]  # Use nums[i] to extend range
                i += 1
            else:
                miss += miss  # Patch with miss, double range
                patches += 1

        return patches

• Lines 3-5: Initialize miss, patches, and index.
• Lines 8-13: Loop until coverage exceeds n:
• If nums[i] ≤ miss, use it to extend miss.
• Otherwise, patch with miss, double miss.
• Time Complexity: O(m + log n)—m iterations plus log n patches.
• Space Complexity: O(1)—just variables.

This is like a gap-filling genius—fast and lean!

Alternative Solution: Brute Force with Dynamic Programming

Why an Alternative Approach?

The brute-force DP approach—O(n * m) time, O(n) space—builds a boolean array to track achievable sums, adding patches when gaps appear. It’s clearer for understanding coverage but impractical for large n. It’s like testing every sum step-by-step—thorough but slow!

How It Works

Track sums with DP:

• Step 1: DP array for sums 0 to n.
• Step 2: Process nums, mark reachable sums.
• Step 3: Patch gaps, update DP.

Step-by-Step Example

Example: nums = [1,3], n = 6

• Init: dp = [True, False, False, False, False, False, False]
• Num 1: dp = [True, True, False, False, False, False, False]
• Num 3: dp = [True, True, False, True, True, False, False]
• Patch 2: dp = [True, True, True, True, True, True, True]
• Result: 1 patch

Code for Brute Force Approach

Copy codeclass Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        dp = [False] * (n + 1)
        dp[0] = True
        patches = 0

        for i in range(1, n + 1):
            if not dp[i]:
                # Check if any num can reach i
                can_reach = False
                for num in nums:
                    if i >= num and dp[i - num]:
                        dp[i] = True
                        can_reach = True
                        break
                if not can_reach:
                    patches += 1
                    for j in range(n, i - 1, -1):
                        if j - i >= 0 and dp[j - i]:
                            dp[j] = True
                    dp[i] = True

        return patches

• Time Complexity: O(n * m)—check each sum with nums.
• Space Complexity: O(n)—dp array.

It’s a sum-building plodder—basic but heavy!

Comparing the Two Solutions

• Greedy (Best):
• Pros: O(m + log n) time, O(1) space, scalable.
• Cons: Greedy logic less obvious.
• Brute Force (Alternative):
• Pros: O(n * m) time, O(n) space, intuitive coverage.
• Cons: Too slow for large n.

Greedy wins for efficiency.

Additional Examples and Edge Cases

• [], 3: 2 (Patch 1, 2).
• [1], 1: 0.
• [2], 3: 1 (Patch 1).

Both handle these, but greedy is faster.

Complexity Breakdown

• Greedy: Time O(m + log n), Space O(1).
• Brute Force: Time O(n * m), Space O(n).

Greedy is the clear choice.

Key Takeaways

• Greedy: Patch the miss—brilliant!
• Brute Force: Build all sums—clear!
• Python: Loops and logic shine—see [Python Basics](/python/basics).
• Coverage: Greed fills gaps.

Final Thoughts: Patch the Array

LeetCode 330: Patching Array in Python is a greedy optimization gem. The greedy solution offers speed and elegance, while brute force provides a tangible baseline. Want more array challenges? Try LeetCode 322: Coin Change or LeetCode 300: Longest Increasing Subsequence. Ready to patch? Head to Solve LeetCode 330 on LeetCode and cover those sums today!