Abstract / Summary

You can take at most k steps to collect fruits from trees in a line to maximize the total fruits gathered.

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 61% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Prefix Sum
• Sliding Window

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 maxTotalFruits method computes the maximum number of berries that can be collected when starting from a given position on a one-dimensional line, moving at most k steps in total. The input fruits is a list of [position, count] pairs sorted by position. The algorithm builds a cumulative array that enables constant-time range queries and then evaluates every feasible left-then-right and right-then-left walk pattern to find the optimal total.

Preprocessing and Prefix Accumulation

The first phase determines the size of the coordinate axis that must be represented. By taking the larger of the last fruit position and the start position and adding one, the code guarantees that every relevant index fits inside the total array.

size  = max(fruits[-1][0], startPos) + 1
total = [0] * size

Each fruit count is placed directly at its coordinate, turning the sparse input into a dense representation.

for x, berries in fruits:
    total[x] = berries

Two passes convert this raw array into a prefix-sum style structure. The left-to-right scan accumulates values from the start position outward, while the right-to-left scan does the same in the opposite direction. After these scans, total[i] holds the sum of berries from the start position up to i (inclusive) when moving left, and similarly when moving right.

have = 0
for x in reversed(range(startPos + 1)):
    have += total[x]
    total[x] = have

have = 0
for x in range(startPos, size):
    have += total[x]
    total[x] = have

Main Evaluation Loop - Walking Left First

The algorithm iterates over every possible leftmost position reachable within the step budget. For each candidate left, it first checks whether the distance from the start exceeds k; if so, the loop terminates early because farther positions are unreachable. The current best result is updated with the total berries collected by moving straight left to left.

result = total[startPos]
for left in reversed(range(startPos)):
    distance = startPos - left
    if distance > k:
        break
    result = max(result, total[left])

If there are remaining steps after reaching left, the code computes the farthest right position that can be visited after a mandatory return to the start (the “walkback” cost). The walkback cost is twice the left distance because the path must retrace steps. When the walkback itself consumes the entire budget, no rightward extension is possible. Otherwise, the rightmost reachable index is calculated, clamped to the array bounds, and the combined berries from both sides are considered. The subtraction of total[startPos] removes the double-counted berries at the start position.

    walkback = 2 * distance
    if walkback >= k:
        continue
    right = startPos + (k - walkback)
    right = min(right, size - 1)
    result = max(result, total[left] + total[right] - total[startPos])

Main Evaluation Loop - Walking Right First

The symmetric loop explores scenarios where the walk begins to the right. It mirrors the left-first logic: iterate over reachable right positions, update the result with the straight-right total, compute the walkback cost, and, if steps remain, extend leftward. The clamping operations ensure that the computed left index never falls below zero.

for right in range(startPos + 1, size):
    distance = right - startPos
    if distance > k:
        break
    result = max(result, total[right])
    walkback = 2 * distance
    if walkback >= k:
        continue
    left = startPos - (k - walkback)
    left = max(left, 0)
    result = max(result, total[left] + total[right] - total[startPos])

Finally, the method returns the best total found across all examined walk patterns.

return result

Edge Cases Handled

When k is zero, the early distance checks prevent any iteration beyond the start position, and the initial result (which equals the berries at startPos) is returned. If the start position lies at the extreme left or right edge of the coordinate range, the clamping with min and max guarantees that the algorithm never indexes outside the total array. The construction of size using the maximum of the last fruit coordinate and startPos ensures that even if the start lies beyond the last fruit, the array is still large enough to accommodate the start index. Sparse fruit distributions are safely handled because the initial filling step writes zeros for positions without fruit, and the prefix scans correctly propagate cumulative sums across empty slots.

Performance Optimizations

The solution avoids repeated summation over ranges by converting the fruit counts into a cumulative array in two linear passes. This enables each range query (total[left], total[right], and the combined expression) to be answered in constant time. Early termination of both main loops when the distance exceeds k prevents unnecessary iterations beyond the reachable horizon. The use of min and max to bound the computed right and left indices eliminates the need for additional boundary checks inside the inner calculations. By reusing the same total array for both left-to-right and right-to-left prefix sums, the code minimizes memory allocations and keeps the runtime footprint low.

Imagine there is a very long garden path with fruit trees planted at different spots. You are standing at a specific point on this path and you have a limited amount of energy to walk around. Because walking back and forth uses up energy, the goal is to figure out the best way to move so that you can gather as many fruits as possible before you get too tired.

First, the code creates a long list that represents the whole path, adding up all the fruits so that it is easy to see how many are growing in any section. It cleans up the information by counting all the fruits from the starting point out to the left and all the fruits from the starting point out to the right.

After that, the code tests two different plans. One plan is to walk to the left first and then potentially turn around to visit some trees on the right side. The other plan is to walk to the right first and then potentially turn around to visit the trees on the left side. For every possible distance you might walk in one direction, the code calculates exactly how much energy would be left over to venture in the other direction. It keeps track of the highest number of fruits collected during all these different scenarios, comparing each attempt to find the biggest feast possible. It is like trying every possible path to make sure you do not miss out on even one delicious snack.

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