Abstract / Summary

Find an element in a list that is greater than its neighbors.

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

Typical patterns to solve this problem:

• Array
• Binary Search

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 defines a class Solution with a method findPeakElement that searches for a peak element in a list of integers. A peak is an element that is strictly greater than its immediate neighbors. The algorithm adopts a randomized strategy: it repeatedly picks a random index until it discovers a position that satisfies the peak condition, then returns that index.

Input Validation

The method begins by determining the length of the input list and handling the trivial case where the list contains zero or one element. In such a scenario the only possible peak is at index 0, which is returned immediately.

size = len(nums)
if size <= 1:
    return 0

Random Selection Loop

A while True loop drives the core of the algorithm. Inside the loop a random position pos is chosen uniformly from the range [0, size-1]. This loop continues indefinitely until a peak is found, guaranteeing eventual termination because a peak always exists in any non-empty array.

while True:
    pos = randint(0, size - 1)

Neighbor Evaluation

For each randomly selected position the algorithm retrieves the values of the left and right neighbors. Sentinel values are used for positions that lie outside the bounds of the array: -2**32 is assigned to both left and right initially, and then overwritten when a neighbor exists. This approach simplifies the comparison logic by ensuring that out-of-range neighbors are always smaller than any realistic array element.

left = right = -2**32
if pos > 0:
    left = nums[pos - 1]
if pos < size - 1:
    right = nums[pos + 1]

Peak Detection and Return

After obtaining the neighbor values, the algorithm checks whether the current element is greater than both neighbors. If the condition holds, the index pos is returned as the location of a peak.

if left < nums[pos] and nums[pos] > right:
    return pos

The loop’s structure ensures that the method exits as soon as a valid peak is identified, avoiding unnecessary further iterations.

Edge Cases Handled

The code explicitly addresses the situation where the random index points to the first or last element of the list. By initializing left and right with a very small sentinel value and only overwriting them when a neighbor exists, the algorithm correctly treats the missing neighbor as smaller than the candidate element. This design allows the first and last positions to be considered valid peaks when they satisfy the strict greater-than condition relative to their single neighbor.

Additionally, the early return for arrays of length zero or one guarantees correct behavior for minimal inputs without entering the random selection loop.

Performance Optimizations Observed

The implementation makes use of local variable assignments (size, left, right, pos) to reduce attribute lookups and improve execution speed within the loop. By employing a sentinel value that is a constant expression (-2**32), the code avoids conditional branches for out-of-range checks during the comparison step. The use of randint from the standard library provides an efficient source of random indices, and the immediate return upon finding a peak eliminates any further unnecessary computation. These choices collectively contribute to a lean execution path for each iteration of the search.

Imagine there is a long row of LEGO towers of different heights all lined up on the floor. The goal is to find one specific tower that is taller than both the tower to its left and the tower to its right.

Since finding this tall tower can take a while if we look at every single one, the code decides to play a game of hide and seek. It closes its eyes and picks a random spot in the line of towers to check.

Once it picks a random spot, it looks at the tower standing there. Then it quickly looks at the neighbor to the left and the neighbor to the right to see how they compare. It asks if the chosen tower is strictly taller than both neighbors. If the chosen tower is indeed the big one that stands taller than the others nearby, the search is finished. If it is not, the code simply closes its eyes and picks a new random spot to try again. It keeps jumping around to different random spots until it finally stumbles upon a peak.

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++	Python	Java						TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java					Go	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei						Rust
	begeekmyfriend					C
	BigEggStudy				C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	Dijkstra-Edu			Java
	everthis							JS
	FelixFan1122				C#
	fengvyi	C++
	gaosq0604		Python
	Garvit244		Python
	gouthampradhan			Java
	halfrost								Go
	haoel	C++
	JoshCrozier							JS
	keineahnung2345	C++
	Krazune	C++
	lennylxx					C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	qiyuangong		Python
	ruoru						Rust
	sonugiri1043	C++
	suxrobGM				C#
	varunu28			Java
	vli02					C
	vthwang			Java
	wisdompeak	C++
	XiaotaoGuo	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
everthis	JavaScript
FelixFan1122	C#
fengvyi	C++
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
qiyuangong	Python
ruoru	Rust
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
XiaotaoGuo	C++
YuriSpiridonov	Python
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