Python 1764.py
class Solution:
def canChoose(self, groups: List[List[int]], nums: List[int]) -> bool:
# quick heuristic using prefix sum
prefix = [ 0 ]
for n in nums:
prefix.append(prefix[-1] + n)
sums = []
for g in groups:
sums.append(sum(g))
def deeper(gi, ni): # group index, nums index
if gi == len(groups):
return True
if ni >= len(nums):
return False
# check first character
if groups[gi][0] != nums[ni]:
return deeper(gi, ni + 1)
last = ni + len(groups[gi]) - 1
# check last character
if last >= len(nums):
return False
if groups[gi][-1] != nums[last]:
return deeper(gi, ni + 1)
# check sum
if sums[gi] != prefix[last + 1] - prefix[ni]:
return deeper(gi, ni + 1)
# now compare the arrays
if nums[ni : last + 1] == groups[gi]:
return deeper(gi + 1, last + 1)
else:
return deeper(gi, ni + 1)
return deeper(0, 0)
Difficulty
and has an acceptance rate of about 55% (30k+ submissions).
Typical patterns to solve this problem:
- Array
- Greedy
- String Matching
- Two Pointers
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation determines whether a sequence of integer groups can be found, in order, as non-overlapping contiguous sub-arrays within a larger integer array. The algorithm relies on a depth-first search that advances through the nums array while attempting to match each group from groups. Early rejection tests based on the first and last elements of a candidate segment, together with a prefix-sum comparison, reduce the amount of element-wise work required.
Key Steps
Building a Prefix Sum Array
A prefix sum array is constructed so that the sum of any sub-array can be obtained in constant time.
prefix = [0]
for n in nums:
prefix.append(prefix[-1] + n)
The extra leading zero aligns indices such that prefix[i] holds the sum of the first i elements of nums. This structure enables a rapid equality check between the sum of a group and the sum of a candidate segment.
Pre-computing Group Sums
The total of each group is calculated once before the recursive search begins.
sums = []
for g in groups:
sums.append(sum(g))
Storing these sums avoids repeated aggregation during recursion.
Recursive Matching Function
The core of the solution is the nested function deeper, which receives the current group index gi and the current position ni in nums.
def deeper(gi, ni):
if gi == len(groups):
return True
if ni >= len(nums):
return False
...
The base cases handle successful completion when all groups have been matched, and failure when the end of nums is reached before all groups are satisfied.
First-Element Quick Check
Before attempting a full segment comparison, the algorithm verifies that the first element of the current group matches the element at the current nums index.
if groups[gi][0] != nums[ni]:
return deeper(gi, ni + 1)
If the first element does not align, the search moves forward by one position in nums, preserving the current group index.
Last-Element and Boundary Validation
The index of the last element of the candidate segment is computed, and the algorithm ensures that this index does not exceed the bounds of nums.
last = ni + len(groups[gi]) - 1
if last >= len(nums):
return False
if groups[gi][-1] != nums[last]:
return deeper(gi, ni + 1)
A mismatch of the last element triggers a shift of the starting position, while an out-of-range condition terminates the current path.
Sum Comparison Using Prefix Sums
The sum of the candidate segment is obtained via the prefix array and compared to the pre-computed group sum.
if sums[gi] != prefix[last + 1] - prefix[ni]:
return deeper(gi, ni + 1)
If the sums differ, the algorithm discards the current alignment without performing a full element-wise comparison.
Full Segment Equality Check
Only after passing the first-element, last-element, and sum checks does the algorithm compare the entire slice.
if nums[ni : last + 1] == groups[gi]:
return deeper(gi + 1, last + 1)
else:
return deeper(gi, ni + 1)
A successful slice match advances both the group index and the position in nums; otherwise, the search continues from the next position while keeping the same group.
Initiating the Search
The outer method simply calls the recursive helper starting at the first group and the first element of nums.
return deeper(0, 0)
Edge Cases Handled
When groups is empty, the first base case (gi == len(groups)) immediately returns True, indicating that an empty sequence of groups trivially matches.
If nums is empty while groups still contains elements, the second base case (ni >= len(nums)) returns False, correctly reflecting the impossibility of matching any non-empty group.
Groups that are longer than the remaining portion of nums are caught by the boundary check if last >= len(nums): return False, preventing out-of-range indexing.
Mismatches at the very first element of a group cause an early recursive call that skips the current nums position, ensuring that the algorithm does not waste time on impossible alignments.
Similarly, a mismatch of the last element or a sum discrepancy leads to an immediate shift of the starting index, avoiding unnecessary full slice comparisons.
The recursion naturally handles overlapping candidate windows because each call either moves the start index forward or advances to the next group after a successful match, guaranteeing that matched groups remain non-overlapping.
Performance Optimizations
The prefix-sum array eliminates the need to recompute the sum of a candidate segment on each recursive step, turning what would be an O(k) operation (where k is the length of the group) into O(1).
Early pruning based on the first and last elements dramatically reduces the search space. By checking these two positions before any deeper work, the algorithm discards the majority of misaligned windows with minimal effort.
The sum comparison acts as a second layer of pruning. Even when the first and last elements match, a differing total sum indicates a mismatch without requiring a full element-wise scan.
Only when all cheap checks succeed does the algorithm perform the slice equality test, which is the most expensive operation. This staged approach ensures that the costly comparison is executed rarely.
The recursive structure avoids the overhead of explicit stack management or iterative loops that would need to maintain multiple indices simultaneously. Each recursive call carries only the necessary state (gi and ni), and the early returns keep the call depth bounded by the number of groups plus the number of positions examined in nums.
Collectively, these techniques produce a solution that scales well for typical input sizes, leveraging constant-time arithmetic and strategic early exits to keep the overall work proportional to the amount of genuine matching effort required.
ELI5 - Simplified Explanation
Imagine a long treasure chest filled with numbered blocks. The goal is to find several smaller groups of blocks hiding inside that big chest, one after another in order. Think of the code as a helpful robot that is searching through the chest.
At the start, the robot creates a quick way to add up the numbers so it does not have to count every single block every time it wants to check a section. This saves a lot of time.
Then, the robot uses a special trick to jump through the chest. It looks at the group of blocks it needs to find and guesses if they might be in a certain spot. To be fast, it checks if the first block matches and if the last block matches. It also checks if the total value of all the blocks in that spot adds up to the same number as the group it is looking for.
If those quick checks look good, it carefully compares every single block to make sure it is exactly the right one. If it finds the match, it marks that spot as finished and moves on to hunt for the next group of blocks starting from where the last one ended. If it does not find a match, it simply jumps to the next spot in the chest and tries again. The robot keeps doing this until it finds everything it needs or runs out of places to look inside the chest.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | ||||||||
|---|---|---|---|---|---|---|---|---|
| author | solutions | |||||||
| www | AlgoMonster | C++ | Python | Java | TS | |||
| WalkCCC | C++ | Python | Java | |||||
| leetcode.ca | C++ | Python | Java | Go | ||||
| Progiez | C++ | Python | Java | |||||
| github | black-shadows | C++ | ||||||
| charles-wangkai | Java | |||||||
| everthis | JS | |||||||
| fsq | C++ | |||||||
| haoel | C++ | |||||||
| JoshCrozier | JS | |||||||
| suxrobGM | C# | |||||||
| trung-hn | Python | |||||||
| wisdompeak | C++ | |||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||
| WalkCCC | C++, Python, Java | |||||||
| leetcode.ca | C++, Go, Java, Python | |||||||
| Progiez | C++, Java, Python | |||||||
| black-shadows | C++, C++ | |||||||
| charles-wangkai | Java | |||||||
| everthis | JavaScript | |||||||
| fsq | C++ | |||||||
| haoel | C++ | |||||||
| JoshCrozier | JavaScript | |||||||
| suxrobGM | C# | |||||||
| trung-hn | Python | |||||||
| wisdompeak | C++ |
Videos
Solved On The Same Day
- problem 3132: Find the Integer Added to Array II
- problem 3133: Minimum Array End
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality