Python 1024.py
class Solution:
def videoStitching(self, clips: List[List[int]], time: int) -> int:
impossible = 9999
clips.sort()
@cache
def deeper(pos):
if pos >= time: # done
return 0
best = impossible
for start, end in clips:
if start > pos: # gap
break
if end > pos: # stitch
best = min(best, 1 + deeper(end))
return best
return -1 if deeper(0) == impossible else deeper(0)
Difficulty
and has an acceptance rate of about 52% (100k+ submissions).
Typical patterns to solve this problem:
- Array
- Dynamic Programming
- Greedy
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 solves the classic interval-cover problem: given a collection of video clips, each defined by a start and end time, determine the minimum number of clips required to cover a target interval [0, time]. The algorithm relies on sorting the input, a depth-first search with memoization, and early termination when a gap is detected.
Key Steps
Sorting the clips
clips.sort()
Sorting arranges the intervals in non-decreasing order of their start times (and, implicitly, end times for equal starts). This ordering enables the subsequent loop to stop as soon as a clip starts after the current position, guaranteeing that no later clip can fill the current gap.
Recursive search with caching
@cache
def deeper(pos):
if pos >= time: # done
return 0
best = impossible
for start, end in clips:
if start > pos: # gap
break
if end > pos: # stitch
best = min(best, 1 + deeper(end))
return best
The inner function deeper receives the current coverage position pos. The base case returns 0 when the target time has been reached or exceeded, indicating that no further clips are needed.
A sentinel value impossible (set to a large constant) represents an unattainable solution. The loop iterates over the sorted clips. When a clip’s start exceeds pos, the loop breaks because the sorted order guarantees that all subsequent clips also start later, leaving an unavoidable gap. If a clip extends beyond pos, the algorithm recursively explores the state after using that clip, adding one to the count. The minimum of all feasible continuations is stored in best.
Final result handling
return -1 if deeper(0) == impossible else deeper(0)
The initial call starts from position 0. If the recursive search returns the sentinel value, the function reports -1 to indicate that covering the interval is impossible; otherwise, it returns the computed minimum number of clips.
Edge Cases Handled
When the target time is 0, the base case pos >= time is satisfied immediately, and the function returns 0, correctly indicating that no clips are needed.
If the input list clips is empty, the loop body never executes, best remains the sentinel, and the final return yields -1, reflecting the impossibility of coverage.
Clips that start before the current position but end at or before pos are ignored because the condition end > pos filters them out, preventing unnecessary recursive calls.
When multiple clips share the same start time, the sorted order preserves their relative end times, and the loop still evaluates each candidate, ensuring that the optimal longer extension is considered.
Gaps in coverage are detected by the if start > pos: break statement; as soon as a clip begins after the current position, the algorithm knows that no earlier clip can fill the gap, and it stops exploring that branch.
Performance Optimizations
The initial sorting step reduces the search space by allowing an early break on gaps, eliminating the need to scan the entire list for each recursive call.
Memoization via @cache stores the result of deeper(pos) for every distinct position encountered. This prevents repeated exploration of identical sub-problems, turning an exponential search into a tractable one.
Using a single large sentinel value (impossible = 9999) avoids the overhead of constructing special objects or raising exceptions for impossible paths, enabling fast integer comparisons.
The condition if end > pos ensures that only clips that actually extend coverage are considered, pruning branches that would not make progress.
Overall, the combination of sorted input, early termination on gaps, and cached recursion yields an efficient solution that scales well with the number of clips.
ELI5 - Simplified Explanation
Imagine you have a long, long movie tape that is exactly as long as the time number. You want to cover the whole tape using smaller pieces of tape from the list of clips. Think of this like building a bridge across a river using floating logs.
First, the computer puts all the little tape pieces in order from the smallest number to the biggest number so they are easy to look through. Then, a helper function starts at the very beginning of the tape. It looks at all the pieces that can reach the current spot. When it finds a piece that can start where the current tape ends, it picks that piece up and adds it to the collection.
The computer keeps doing this over and over, trying to find the fewest pieces possible to reach the end of the long tape. If it finds a gap where no piece can reach, it knows that path will not work. If it reaches the end of the tape, it remembers how many pieces it used. It keeps trying different combinations until it finds the smallest number of pieces that can finish the job from start to finish. If the computer tries every way possible and still cannot cover the whole tape, it finishes by saying it is not possible to do.
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 | ||||
| LeetcodeHelp | C++ | Python | Java | |||||
| Progiez | C++ | Python | Java | |||||
| github | BigEggStudy | C# | ||||||
| black-shadows | C++ | |||||||
| charles-wangkai | Java | |||||||
| everthis | JS | |||||||
| fsq | C++ | |||||||
| haoel | C++ | |||||||
| JoshCrozier | JS | |||||||
| lkwq007 | Python | |||||||
| suxrobGM | C# | |||||||
| trung-hn | Python | |||||||
| wisdompeak | C++ | |||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||
| WalkCCC | C++, Python, Java | |||||||
| leetcode.ca | C++, Go, Java, Python | |||||||
| LeetcodeHelp | C++, Java, Python | |||||||
| Progiez | C++, Java, Python | |||||||
| BigEggStudy | C# | |||||||
| black-shadows | C++, C++ | |||||||
| charles-wangkai | Java | |||||||
| everthis | JavaScript | |||||||
| fsq | C++ | |||||||
| haoel | C++ | |||||||
| JoshCrozier | JavaScript | |||||||
| lkwq007 | Python | |||||||
| suxrobGM | C# | |||||||
| trung-hn | Python | |||||||
| wisdompeak | C++ |
Videos
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