Abstract / Summary

You can reach all indices if you can always jump to the highest reachable index at each step.

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 47% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming
• Heap (Priority Queue)
• Monotonic Queue
• Queue

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 problem of finding the maximum achievable score when moving from the first element to the last element of an integer array nums, with the constraint that each jump may span at most k positions. The algorithm maintains a dynamic programming array score where score[i] represents the best possible total when landing on index i. To keep the selection of the optimal previous position efficient, a monotonic deque-like structure called candidates stores indices in decreasing order of their associated scores.

Core Algorithm

The initialization creates the score array filled with zeros and sets the starting score to the value of the first element. The candidates list begins with index 0, indicating that the first position is the only reachable source at the start.

score = [0] * len(nums)
score[0] = nums[0]
candidates = [0]

The main loop iterates over each index i from 1 to the end of the array. For each position, three logical phases are performed:

1. Discarding Out-of-Range Sources The algorithm computes a threshold i - k. Any index in candidates that lies left of this threshold can no longer serve as a valid predecessor because a jump from it would exceed the allowed distance. The check examines the front of the list, which always holds the best candidate, and removes it if it is outdated.

   threshold = i - k
   if candidates[0] < threshold:
       candidates.pop(0)

2. Computing the Current Score The best reachable predecessor is always at the front of candidates. Adding the current array value yields the tentative score for index i.

   current = score[candidates[0]] + nums[i]

3. Maintaining Monotonic Order After the new score is known, the algorithm removes any indices at the back of candidates whose scores are strictly less than the newly computed current. This step preserves the invariant that scores in candidates decrease from front to back, guaranteeing that the front always points to the optimal predecessor for future positions.

   while candidates and score[candidates[-1]] < current:
       candidates.pop()

   Finally, the new score is stored, and the current index is appended as a potential source for later jumps.

   score[i] = current
   candidates.append(i)

When the loop finishes, score[-1] holds the maximum total achievable upon reaching the last element, which the function returns.

Edge Cases Handled

The algorithm gracefully handles the situation where k is larger than the length of the array. In such cases, the threshold i - k becomes negative for early indices, and the condition candidates[0] < threshold never triggers, allowing any earlier index to remain a valid source. This ensures that the first element can directly influence all subsequent positions when the jump limit is effectively unbounded.

When k equals 1, the loop reduces to a simple linear accumulation because each index can only be reached from its immediate predecessor. The deque logic still functions correctly: the outdated check removes the previous index, and the monotonic maintenance step never discards any element because each new score is exactly the sum of the previous score and the current value.

If the input array contains negative numbers, the algorithm still produces the correct maximum because it always selects the predecessor with the highest cumulative score, regardless of sign. The monotonic removal condition (score[candidates[-1]] < current) ensures that a negative contribution does not linger in the candidate list if a later, higher score becomes available.

Performance Optimizations

The primary optimization stems from the use of the candidates list as a monotonic queue. By keeping scores in decreasing order, the algorithm avoids scanning all possible predecessors within the window of size k. Each index is inserted into candidates exactly once and removed at most once, resulting in a total number of list operations linear in the length of nums. This eliminates the need for nested loops that would otherwise examine each of the up to k previous positions for every index.

The removal of outdated sources is performed only on the front of the list, which is an O(1) operation thanks to the direct index access. The while-loop that discards inferior scores works from the back, also achieving constant-time removals per element because each element can be popped only once throughout the entire execution.

By storing intermediate results in the score array, the algorithm avoids recomputing partial sums, ensuring that each value is accessed a constant number of times. The combination of these techniques yields a solution that scales efficiently with both the length of the input array and the jump limit k.

Imagine a long path made of colorful square tiles, and each tile has a special secret number written on it. Starting at the very first tile, the goal is to hop all the way to the final tile on the other side. Every time a tile is stepped on, that tile's secret number gets added to a growing pile of points.

To make the journey as successful as possible, there is a rule about how far you can jump. You are only allowed to leap forward a certain distance. This code acts like a very smart planning assistant that looks ahead at all the possible spots to land. It keeps track of the best way to get to any tile by remembering which previous tiles gave the biggest pile of points.

As the planner moves through the path, it looks at the available spots within jumping distance. It picks the one that already has the best score and adds the current tile's number to it. If some older spots become too far away to reach, they are simply pushed aside because they are no longer useful.

Sometimes, the planner realizes that a spot it just reached provides a much better total than any of the older options it was holding onto. When that happens, it forgets the old, smaller options and keeps the new, better one in mind for the future. By following this careful process of building on the best previous results and letting go of the ones that are not as helpful, the plan eventually figures out the highest possible score to reach the very last tile.

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

not analyzed yet

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