Python 1306.py
class Solution:
def canReach(self, arr: List[int], start: int) -> bool:
need = set([ i for i,a in enumerate(arr) if a == 0 ])
have = set()
todo = set([ start ])
while todo:
next = set()
for t in todo:
if t in have:
continue
have.add(t)
if t in need:
return True
if t - arr[t] >= 0:
next.add(t - arr[t])
if t + arr[t] < len(arr):
next.add(t + arr[t])
todo = next
return False
Difficulty
and has an acceptance rate of about 70% (500k+ submissions).
Typical patterns to solve this problem:
- Array
- Breadth First Search
- Depth First Search
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 zero-valued element in an integer array can be reached from a given starting index by repeatedly jumping left or right by the value stored at the current position. It treats the array as a graph where each index is a node and possible jumps are edges. The algorithm performs a breadth-first search (BFS) over this implicit graph, stopping as soon as a node containing zero is discovered.
Core Data Structures
The solution relies on three sets:
need = set([ i for i,a in enumerate(arr) if a == 0 ])
have = set()
todo = set([ start ])
need holds all indices whose value is zero, allowing constant-time checks for a successful termination. have records indices that have already been processed, preventing infinite loops when the jump pattern creates cycles. todo represents the frontier of the BFS, i.e., the set of indices to be explored in the current iteration.
Main Loop
The heart of the algorithm is a while loop that continues until there are no more indices to explore:
while todo:
next = set()
for t in todo:
if t in have:
continue
have.add(t)
if t in need:
return True
if t - arr[t] >= 0:
next.add(t - arr[t])
if t + arr[t] < len(arr):
next.add(t + arr[t])
todo = next
Inside the loop, a new set next is prepared to collect the indices reachable from the current frontier. For each index t in todo, the algorithm first skips it if it has already been visited, ensuring that each node is processed at most once. The index is then added to have.
A membership test against need determines whether the current index contains zero; if so, the function returns True immediately, confirming reachability.
The two conditional blocks compute the left and right jump targets. The left jump t - arr[t] is added only when it stays within the array bounds (>= 0). The right jump t + arr[t] is added only when it remains less than the array length. These checks guarantee that the algorithm never attempts to access an out-of-range element.
After processing all indices in the current frontier, todo is replaced by next, advancing the BFS to the next layer of reachable positions.
Edge Cases Handled
The code gracefully handles several edge conditions:
- Multiple zeroes: By collecting all zero-valued indices in
need, the algorithm can succeed as soon as any of them is reached, regardless of how many exist. - Self-loops: When
arr[t]is zero, the left and right jump calculations both yieldt. Thehaveset prevents re-processing the same index, avoiding an infinite loop. - Repeated values: If different paths lead to the same index, the
haveset ensures that the index is explored only once, eliminating redundant work. - Boundary jumps: The explicit bounds checks (
>= 0and< len(arr)) prevent attempts to jump outside the array, which would raise an exception. - Start at a zero: If the starting index itself is a zero, the membership test against
needsucceeds on the first iteration, returningTruewithout further exploration.
Performance Optimizations
The implementation incorporates several techniques that improve runtime efficiency:
- Set-based frontier: Using a set for
todoandnextenables O(1) average-case insertion and membership checks, making each BFS layer expansion fast. - Early termination: The moment a zero index is encountered, the function returns immediately, avoiding unnecessary exploration of the remaining graph.
- Visited tracking: The
haveset eliminates revisiting nodes, which is crucial for preventing exponential blow-up in cases where the jump pattern creates many cycles. - Pre-computed zero indices: By building
needonce at the start, the algorithm avoids scanning the array repeatedly during the search, reducing overhead for each membership test.
Overall, the code presents a concise BFS solution that leverages set operations to achieve efficient exploration of the reachable indices while correctly handling boundary conditions and cycles.
ELI5 - Simplified Explanation
Imagine a long train track made of squares, and each square has a special number written on it. This number acts like a magic command that tells a little robot which way to hop next. Some squares help the robot jump to the left, while others help it jump to the right. The robot starts at a specific square and wants to find a lucky square that has a zero written on it.
To keep track of the journey, the robot uses a notebook to write down every square it has already visited so it does not get stuck going in circles. First, the robot looks at the starting square. If that square already has a zero, the mission is complete right away. If not, it looks at the number on the square to figure out how far to jump. It checks if jumping that far keeps it on the track. If the jump is allowed, the robot adds the new destination to its list of places to explore next.
The robot keeps jumping from square to square, always looking for a zero. It adds every new square it finds to a list of places to check. If the robot ever lands on a square with a zero, it celebrates because the goal is reached. If the robot tries every possible jump but never happens to land on a zero, it concludes that there is no way to reach the goal from the starting spot.
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++ | Java | ||||||
| leetcode.ca | C++ | Python | Java | Go | TS | |||
| MemoryLimitExceeded | C++ | Python | ||||||
| Progiez | C++ | Python | Java | |||||
| github | BigEggStudy | C# | ||||||
| black-shadows | C++ | |||||||
| charles-wangkai | Java | |||||||
| everthis | JS | |||||||
| fpdjsns | C++ | |||||||
| fsq | C++ | |||||||
| halfrost | Go | |||||||
| JoshCrozier | JS | |||||||
| keineahnung2345 | C++ | |||||||
| lkwq007 | Python | |||||||
| MacJim | C++ | |||||||
| shreymehul | C# | |||||||
| suxrobGM | C# | |||||||
| trung-hn | Python | |||||||
| varunu28 | Java | |||||||
| wisdompeak | C++ | |||||||
| withaarzoo | C++ | |||||||
| YuriSpiridonov | Python | |||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||
| WalkCCC | C++, Java | |||||||
| leetcode.ca | C++, Go, Java, Python, TypeScript | |||||||
| MemoryLimitExceeded | Python, C++ | |||||||
| Progiez | C++, Java, Python | |||||||
| BigEggStudy | C# | |||||||
| black-shadows | C++, C++ | |||||||
| charles-wangkai | Java | |||||||
| everthis | JavaScript | |||||||
| fpdjsns | C++ | |||||||
| fsq | C++ | |||||||
| halfrost | Go | |||||||
| JoshCrozier | JavaScript | |||||||
| keineahnung2345 | C++ | |||||||
| lkwq007 | Python | |||||||
| MacJim | C++ | |||||||
| shreymehul | C# | |||||||
| suxrobGM | C# | |||||||
| trung-hn | Python | |||||||
| varunu28 | Java | |||||||
| wisdompeak | C++ | |||||||
| withaarzoo | C++ | |||||||
| YuriSpiridonov | Python |
Videos
Similar Problems
- problem 55: Jump Game
Solved On The Same Day
- problem 997: Find the Town Judge
- problem 695: Max Area of Island
- problem 797: All Paths From Source to Target
- problem 802: Find Eventual Safe States
- problem 863: All Nodes Distance K in Binary Tree
- problem 934: Shortest Bridge
- problem 1020: Number of Enclaves
- problem 1091: Shortest Path in Binary Matrix
- problem 1129: Shortest Path with Alternating Colors
- problem 1376: Time Needed to Inform All Employees
- problem 1557: Minimum Number of Vertices to Reach All Nodes
- problem 2038: Remove Colored Pieces if Both Neighbors are the Same Color
- problem 212: Word Search II
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