Abstract / Summary

Find the fewest jumps to reach the end of an array where each value shows the farthest you can jump from that spot.

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 43% (5+ million submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming
• Greedy

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 classic “minimum jumps to reach the end of an array” problem using a dynamic programming approach. It builds an auxiliary array that records the smallest number of jumps required to reach each position. The algorithm iterates through the input, propagating reachable states forward, and finally returns the value stored for the last index. The code handles the trivial case of a single-element array explicitly, returning zero jumps.

Key Steps

The method begins by checking whether the input vector contains only one element. In that situation the function returns 0 immediately, because no movement is needed.

if (nums.size() == 1)
    return 0;

Next, an auxiliary vector named steps is created. Its length is one greater than the input size, and each entry is initialized to a large sentinel value (999999). The first element is set to 0, indicating that the start position requires zero jumps.

vector<int> steps(nums.size() + 1, 999999);
steps[0] = 0;

The outer loop walks through each index i of the input array. If the current position has not been reached (its entry in steps still holds the sentinel), the loop skips further processing for that index.

for (auto i = 0; i < nums.size(); i++)
{
    if (steps[i] == 999999)
        continue;
    // inner loop follows
}

Inside the outer loop, an inner loop enumerates every possible jump length j from 1 up to the maximum distance allowed by nums[i]. For each candidate destination i + j, the code first checks whether the destination lies beyond the bounds of the steps vector; if so, the inner loop terminates early.

for (auto j = 1; j <= nums[i]; j++)
{
    if (i + j >= steps.size())
        break;
    // update step count follows
}

When a reachable destination is within bounds, the algorithm compares the existing recorded jump count for that destination with the count that would result from taking the current jump (steps[i] + 1). If the new count is smaller, the entry is updated.

if (steps[i + j] > steps[i] + 1)
    steps[i + j] = steps[i] + 1;

After all positions have been processed, the function returns the value stored for the last index of the original array, which represents the minimal number of jumps required to reach the end.

return steps[nums.size() - 1];

Edge Cases

The explicit early return for a single-element input covers the edge case where the start is also the destination, ensuring the function does not perform unnecessary work. The sentinel value (999999) acts as a guard against unreachable positions; the outer loop’s continue statement skips any index that remains unreachable after previous iterations. The inner loop’s boundary check (i + j >= steps.size()) prevents out-of-range accesses when a jump would overshoot the end of the auxiliary array, effectively handling cases where the maximum jump length exceeds the remaining distance to the array’s end.

Performance Optimizations

The algorithm avoids redundant updates by only processing indices that have already been reached (steps[i] != 999999). This selective propagation reduces the number of inner-loop executions compared to a naïve approach that would iterate over every possible jump from every index regardless of reachability. The early break in the inner loop (if (i + j >= steps.size()) break;) stops further iteration as soon as the jump would exceed the array bounds, preventing unnecessary comparisons and assignments. By using a single auxiliary vector and updating it in place, the implementation minimizes memory allocations and leverages contiguous storage for fast access patterns. The use of simple integer comparisons and assignments keeps the inner operations lightweight, contributing to overall efficiency.

Imagine you have a long row of numbered stepping stones leading to a treasure chest. You are standing on the first stone and you want to reach the last one by taking as few jumps as possible. Each stone has a magic number written on it that tells you how far you are allowed to leap forward.

To figure this out, this code keeps a little notebook where it writes down the smallest number of jumps needed to land on every stone. At the very beginning, it assumes every stone is super far away, almost impossible to reach. It starts the count at zero for the first stone because that is where you begin.

Then, it looks at each stone one by one. If it knows it can actually reach the current stone, it looks at the magic number written there. That number shows the range of how many spots you can hop ahead. It checks all those spots and writes in the notebook how many jumps it took to get there. If it finds a way to reach a stone in fewer jumps than it had written down before, it updates the notebook with the better, smaller number.

Finally, after looking at all the stones and all the possible hops, the notebook will have the smallest number of jumps needed to reach that final stone with the treasure.

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

Time: polynomial
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	C#	Rust		Go		C	PHP	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei					Rust
	begeekmyfriend									C
	BigEggStudy				C#
	black-shadows		Python
	bujosa		Python
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	everthis						JS
	FelixFan1122				C#
	fengvyi	C++
	fpdjsns	C++
	gaosq0604		Python
	Garvit244		Python
	gouthampradhan			Java
	halfrost							Go
	JoshCrozier						JS
	keineahnung2345	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	qiyuangong		Python
	ruoru					Rust
	Shamik07								Dart
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	trung-hn		Python
	varunu28			Java
	vthwang			Java
	wisdompeak	C++
	XiaotaoGuo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, C#, Go, Java, PHP, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	Python, Python
bujosa	Python
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
luangong	C++
MacJim	C++
qiyuangong	Python
ruoru	Rust
Shamik07	Dart
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
wisdompeak	C++
XiaotaoGuo	C++
zfang399	C++

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