Abstract / Summary

Given an array, replace each element with the largest number to its right or zero if none exists.

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 72% (700k+ submissions).

Typical patterns to solve this problem:

• Array

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 “replace each element with the greatest element on its right” problem by traversing the input list from the end toward the beginning. It builds the output list in reverse order, records the maximum seen so far, and finally restores the original order before returning the result. The algorithm works in a single linear pass after an initial reversal of the input array.

Key Steps

The first important operation establishes a sentinel value that represents the greatest element to the right of the last position.

high = -1

Next, an empty container is prepared to accumulate the transformed values.

result = []

The input list is reversed in place, which enables forward iteration while effectively processing the original list from right to left.

arr.reverse()

The core loop iterates over the indices of the reversed list. For each element, the current sentinel value is appended to the result list, then the sentinel is updated to be the larger of its current value and the element just examined.

for i in range(len(arr)):
    result.append(high)
    high = max(high, arr[i])

After the loop finishes, the result list holds the desired values but in reverse order. Reversing it restores the correct left-to-right orientation.

result.reverse()

Finally, the method returns the populated list.

return result

Edge Cases Handled

When the input list is empty, the reversal operation leaves it unchanged, the loop body never executes, and the method returns an empty list, matching the expected behavior for a vacuous input.

If the input contains a single element, the reversal does not alter the list, the loop runs once, appends the sentinel value -1 to the result, and then the final reversal yields a list containing only -1. This correctly reflects that there is no element to the right of the sole entry.

The algorithm also correctly processes lists that are strictly decreasing, strictly increasing, or contain repeated values. Because the sentinel high is updated with the maximum of itself and the current element at each step, it always reflects the greatest value encountered so far in the reversed traversal, ensuring that each position receives the proper greatest-to-right value regardless of the ordering pattern.

Negative numbers are accommodated as long as the sentinel -1 is appropriate for the problem’s definition of “no greater element.” If all elements are less than -1, the sentinel will remain larger than any array entry, and the output will consist of -1 for every position, which aligns with the convention that -1 denotes the absence of a greater element.

Performance Optimizations

Reversing the input list in place avoids allocating an auxiliary copy of the data, thereby conserving memory. The subsequent forward iteration over the reversed list eliminates the need for index arithmetic that would be required when iterating backward, simplifying the loop logic and allowing the use of Python’s efficient range iterator.

Updating the sentinel with a single call to the built-in max function provides a constant-time comparison at each step, ensuring that the overall processing time scales linearly with the length of the input.

Collecting the output in a separate list rather than modifying the original array preserves the input for callers that may rely on its unchanged state, while still achieving linear time performance because each element is appended exactly once.

The final reversal of the result list is also performed in place, reusing the allocated storage without additional copying. This two-step reversal strategy-first on the input, then on the output-maintains a tight memory footprint while delivering the required ordering.

Imagine a long line of toy blocks, each having a different number written on it. The goal is to walk along these blocks, but instead of looking at the number on the block in your hand, you want to know which one is the biggest among all the blocks that come after it.

To solve this, the code starts by turning the whole line of blocks around so the very last one is now first. It keeps track of a special number, which starts at negative one because there is nothing after the last block.

As it looks at each block one by one, it first writes down that special number on a new piece of paper. Then, it compares the number on the current block with the special number it is holding. If the block has a bigger number, that becomes the new special number to remember for the next step.

Once it reaches the end of the line, the new list of numbers is turned back around to match the original order. Every spot now shows the largest number that was hiding to its right.

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++	Java		Python					TS
	WalkCCC	C++	Java		Python
	leetcode.ca	C++	Java		Python			Go		TS
	Progiez	C++	Java		Python
github	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai		Java
	Dijkstra-Edu		Java
	DimitrisJim								C
	everthis					JS
	fartem						Ruby
	fsq	C++
	halfrost							Go
	JoshCrozier					JS
	keineahnung2345	C++
	lkwq007				Python
	shreymehul			C#
	suxrobGM			C#
	varunu28		Java
	YuriSpiridonov				Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
Dijkstra-Edu	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
shreymehul	C#
suxrobGM	C#
varunu28	Java
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