Abstract / Summary

You can reach all indices by jumping forward or backward by at most a given value from any index.

Note

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

This problem is ranked as

and has an acceptance rate of about 46% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Breadth First Search
• Hash Table

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.

Overview

The provided implementation solves the “minimum jumps” problem on an integer array by treating each index as a node in an implicit graph. From any position you may move to the adjacent indices or to any other index that holds the same value. The algorithm performs a breadth-first search (BFS) from the start index until the last index is reached, counting the number of layers traversed as the answer.

Data Preparation

The first phase builds a mapping from each distinct array value to the set of indices that contain that value. This enables constant-time lookup of all “teleport” destinations for a given value.

same = defaultdict(set)
for i, a in enumerate(arr):
    same[a].add(i)

The use of defaultdict(set) guarantees that a new set is created automatically for unseen values, and the add operation populates the collection efficiently.

BFS Loop

The search maintains three core structures:

• todo - the current frontier of indices to explore.
• seen - a record of indices that have already been processed.
• steps - the number of BFS layers traversed so far.

The loop proceeds until the frontier becomes empty or the target index appears in the frontier.

todo  = set([0])
seen  = set([-1])          # sentinel to simplify boundary checks
last  = len(arr) - 1
steps = 0
while todo:
    if last in todo:
        return steps
    next = set()
    for t in todo:
        if t in seen:
            continue
        seen.add(t)

        if t + 1 not in seen:
            next.add(t + 1)
        if t - 1 not in seen:
            next.add(t - 1)

        next |= same[arr[t]]
        same[arr[t]].clear()   # prevents revisiting the same value later
    todo   = next
    steps += 1

Each iteration expands the frontier by:

1. Adding the right neighbor (t + 1) if it has not been visited.
2. Adding the left neighbor (t - 1) under the same condition.
3. Merging all indices that share the current value (same[arr[t]]) into the next frontier.
4. Clearing the set for the current value to avoid redundant work in future iterations.

The early return when last is found guarantees that the minimal number of jumps is returned as soon as the target is reachable.

Edge Cases Handled

The algorithm gracefully handles several special situations without additional conditional logic:

• Single-element array - The initial frontier contains index 0, which is also the last index, causing the immediate return of 0 steps.
• Negative indices - The sentinel -1 placed in seen ensures that attempts to access t - 1 when t is 0 are ignored, eliminating the need for explicit bounds checks.
• Repeated values - By clearing same[arr[t]] after processing a value, the algorithm prevents repeated expansion through the same group of equal elements, which could otherwise cause exponential blow-up.
• Array with all identical values - The first expansion from index 0 will add every other index to the frontier, and the subsequent clearing of the value’s set stops further unnecessary processing.
• Array where the start and end values are the same - The teleport step (next |= same[arr[t]]) will immediately include the last index in the next frontier, leading to a correct answer in one additional step.

Performance Optimizations

Several deliberate choices keep the execution efficient:

• Set-based frontier - Using a set for todo and next provides O(1) membership tests and eliminates duplicate entries automatically.
• Early termination - Checking if last in todo at the start of each BFS layer avoids unnecessary expansion once the goal is reachable.
• Clearing value groups - The line same[arr[t]].clear() removes all indices associated with a value after they have been explored once. This prevents the algorithm from revisiting the same group of equal numbers in later layers, reducing the total number of edge traversals dramatically when many duplicates exist.
• Sentinel in seen - Inserting -1 into seen removes the need for explicit range checks when moving left from the first index, simplifying the loop body and avoiding extra conditional branches.
• Avoiding redundant neighbor checks - The if t in seen: continue guard ensures that each index is processed at most once, even if it appears in the frontier multiple times due to different paths.

Together, these techniques ensure that the BFS explores each index and each distinct value group at most once, delivering a solution that scales well with input size and value distribution.

Imagine a long path of stepping stones, where each stone has a number painted on it. The goal is to reach the final stone at the end of the path using the smallest number of jumps possible.

The code starts by organizing all the stones so that if several stones have the same number, they are grouped together in a special notebook. This makes it easy to jump between stones that look identical.

A list is created to keep track of every stone that can be reached in the current turn. At the same time, another list remembers which stones have already been visited so no time is wasted hopping back to where the journey has already been.

When a jump happens, there are three types of moves to choose from. One move is to step forward to the very next stone, another is to step backward to the previous stone, and the most exciting move is to jump instantly to any other stone that has the same number painted on it. Once a group of matching stones has been used, those stones are crossed out in the notebook so they do not need to be checked again.

Each time a new jump starts, a counter goes up to track how many big hops were taken. The process keeps going, jumping from stone to stone, until the final stone is finally reached.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

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

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++	Python		Java
	leetcode.ca	C++	Python		Java		Go	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fpdjsns	C++
	fsq	C++
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	suxrobGM					C#
	trung-hn		Python
	varunu28				Java
	wisdompeak	C++
	withaarzoo	C++
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fpdjsns	C++
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++
withaarzoo	C++
YuriSpiridonov	Python

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