Patching Array Solution

LeetCode 330: Patching Array

i recently solved the patching array problem on leetcode, and it's a great example of greedy algorithms and number theory. this hard problem tests your understanding of optimal strategies and efficient problem-solving techniques.

Problem Statement

given a sorted integer array nums and an integer n, add/patch elements to the array such that any number in the range [1, n] inclusive can be formed by the sum of some elements in the array.

return the minimum number of patches required.

example 1:

input: nums = [1,3], n = 6
output: 1

explanation:
combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
so we only need 1 patch.

example 2:

input: nums = [1,5,10], n = 20
output: 2

explanation: the two patches can be [2, 4].

example 3:

input: nums = [1,2,2], n = 5
output: 0

My Approach

when i first saw this problem, i immediately thought about using a greedy approach. the key insight is that we should always add the smallest missing number to maximize the range of achievable sums.

Initial Thoughts

i started by thinking about different approaches:

greedy approach - always add smallest missing number
dynamic programming - try all possible combinations
backtracking - explore all possible patches
mathematical analysis - understand the pattern

Solution Strategy

i decided to use a greedy algorithm approach with the following strategy:

range building - track the maximum achievable sum
greedy selection - add the smallest missing number when needed
array processing - process existing array elements
optimal strategy - always add the smallest missing number
range extension - extend achievable range with each addition

My Solution

class solution:
def minpatches(self, nums: list[int], n: int) -&gt; int:
patches = 0
reachable = 0  # maximum achievable sum
i = 0

while reachable &lt; n:
# if we can use the current number from array
if i &lt; len(nums) and nums[i] &lt;= reachable + 1:
reachable += nums[i]
i += 1
else:
# add the smallest missing number (reachable + 1)
reachable += reachable + 1
patches += 1

return patches

Code Breakdown

let me walk through how this solution works:

1. Initialization

patches = 0
reachable = 0  # maximum achievable sum
i = 0

we initialize our variables:

patches: count of numbers we need to add
reachable: maximum sum we can achieve with current elements
i: index in the original array

2. Main Loop

while reachable &lt; n:
# process array elements or add patches

the main loop continues until we can reach the target number n:

condition: reachable < n
goal: extend reachable range to cover n

3. Array Element Processing

if i &lt; len(nums) and nums[i] &lt;= reachable + 1:
reachable += nums[i]
i += 1

we process array elements when possible:

boundary check: i < len(nums)
usability check: nums[i] <= reachable + 1
range extension: add the element to reachable sum
index increment: move to next array element

4. Patch Addition

else:
# add the smallest missing number (reachable + 1)
reachable += reachable + 1
patches += 1

when we can't use array elements:

add smallest missing: reachable + 1
range extension: reachable += reachable + 1
patch count: increment patches counter

5. Greedy Strategy Explanation

# the key insight: always add the smallest missing number
reachable += reachable + 1

the greedy strategy:

smallest missing: reachable + 1 is the smallest number we can't form
optimal choice: adding this number maximizes the new range
range doubling: each addition roughly doubles the achievable range

Example Walkthrough

let's trace through the example: nums = [1,3], n = 6

initial state:
- reachable = 0, patches = 0, i = 0

step 1: reachable = 0, nums[0] = 1
- condition: 1 &lt;= 0 + 1 (true)
- use 1: reachable = 1, i = 1

step 2: reachable = 1, nums[1] = 3
- condition: 3 &lt;= 1 + 1 (false)
- add patch: reachable = 1 + 1 = 2, patches = 1

step 3: reachable = 2, nums[1] = 3
- condition: 3 &lt;= 2 + 1 (true)
- use 3: reachable = 2 + 3 = 5, i = 2

step 4: reachable = 5, i = 2 (end of array)
- condition: 5 &lt; 6 (true)
- add patch: reachable = 5 + 5 + 1 = 11, patches = 2

result: 1 patch (we can reach 6 without the second patch)

Time and Space Complexity

time complexity: O(m + log n) where m is array length
space complexity: O(1) - constant extra space

the algorithm is efficient because:

we process each array element at most once
the number of patches is logarithmic in n
we use constant extra space

Key Insights

greedy approach - always add smallest missing number
range tracking - maintain maximum achievable sum
optimal strategy - each patch maximizes range extension
efficient processing - linear time through array

Alternative Approaches

i also considered:

dynamic programming - try all possible combinations
exponential time complexity
too slow for large inputs
not suitable for leetcode
backtracking - explore all possible patches
exponential time complexity
impractical for large n
doesn't guarantee optimal solution
mathematical analysis - understand the pattern
more complex than greedy
same time complexity
harder to implement
binary search - find optimal patches
more complex than greedy
same time complexity
unnecessary complexity

Edge Cases to Consider

empty array - need patches for all numbers
single element - handle array with one element
large n - ensure efficient performance
duplicate elements - handle repeated values
small n - handle edge cases
array larger than n - handle unnecessary elements

Python 3-Specific Features

type hints - list[int] for better code clarity
class methods - object-oriented approach
list operations - len(), indexing for array access
comparison operators - <= for boundary checking
increment operators - += for efficient updates

Lessons Learned

this problem taught me:

greedy algorithms - optimal local choices
number theory - understanding achievable ranges
range building - incremental construction
optimal strategies - mathematical intuition

Real-World Applications

this problem has applications in:

coin change problems - making exact amounts
resource allocation - optimal distribution
game theory - optimal strategies
optimization - minimizing resources

Conclusion

the patching array problem is an excellent exercise in greedy algorithms and number theory. the key insight is using a greedy approach to always add the smallest missing number, which optimally extends the achievable range.

this is part of my leetcode problem-solving series. i'm documenting my solutions to help others learn and to track my own progress.