Problem 1306

Abstract / Summary

Given an array of integers, determine if you can reach any index with a value of at least the array's maximum value by jumping according to the values.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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
23 lines | 642 bytes | submitted October 2, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 70% (500k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Breadth First Search
  • Depth First Search
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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 yield t. The have set prevents re-processing the same index, avoiding an infinite loop.
  • Repeated values: If different paths lead to the same index, the have set ensures that the index is explored only once, eliminating redundant work.
  • Boundary jumps: The explicit bounds checks (>= 0 and < 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 need succeeds on the first iteration, returning True without further exploration.

Performance Optimizations

The implementation incorporates several techniques that improve runtime efficiency:

  • Set-based frontier: Using a set for todo and next enables 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 have set 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 need once 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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 6.89 | σ = 1.40

Complexity Analysis

Time: linear
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
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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
34 links | 23 authors | 7 languages

Videos

6 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

14 solutions   October 2, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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