Abstract / Summary

Replace elements whose value equals the average of their adjacent elements in an array.

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

Typical patterns to solve this problem:

• Array
• Greedy
• Sorting

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 method that receives a list of integers and produces a rearranged sequence where each interior element is either a local maximum or a local minimum relative to its immediate neighbors. The method first sorts the input, then iterates through the sorted values while alternating between yielding the current element and a previously stored element. A final check ensures that any leftover element from an odd-length input is also emitted. Because the function uses yield, it returns a generator rather than a concrete list, allowing the caller to consume the rearranged values lazily.

Key Steps

The first operation sorts the input in non-decreasing order, guaranteeing that the smallest values appear first and the largest values appear last.

nums.sort()

A variable named prev is initialized to zero before the loop begins. This variable temporarily holds the most recent element that has not yet been emitted.

prev = 0

The core of the algorithm is a for loop that enumerates the sorted list. The loop index i is examined with a bitwise AND to determine whether the position is odd. When the index is odd, the current number n is yielded first, followed by the previously stored value prev. When the index is even, the current number is stored in prev for later emission.

for i, n in enumerate(nums):
    if i & 1:
        yield n
        yield prev
    else:
        prev = n

After the loop completes, a conditional checks whether the original list length is odd. If it is, the final stored value prev-which has not yet been yielded-gets emitted.

if len(nums) & 1:
    yield prev

Edge Cases

When the input list is empty, the initial sort produces an empty list, the loop body never executes, and the final conditional evaluates to false, resulting in a generator that yields no values. This behavior gracefully handles the empty-input scenario without raising errors.

If the list contains a single element, the sorting step leaves the list unchanged. The loop runs once with i equal to zero, causing the element to be stored in prev. Because the length is odd, the final conditional triggers and yields that single element, satisfying the requirement that a one-element array trivially meets the local-extrema condition.

For lists with an even number of elements, the loop processes pairs of indices. Each odd index causes two values to be yielded-first the larger of the pair (due to the sorted order) and then the smaller-ensuring the alternating high-low pattern throughout the sequence. No leftover value remains, so the final conditional does not execute.

When the list length is odd and greater than one, the loop processes all but the last element in pairs, leaving the final element stored in prev. The concluding conditional then yields this element, preserving the alternating pattern up to the end of the sequence.

Performance Optimizations

The algorithm leverages the built-in list sort method, which operates in place and avoids the overhead of creating a secondary sorted copy. By using a generator (yield) rather than constructing a new list, the implementation minimizes memory consumption, especially for large inputs, because values are produced on demand.

The test for odd positions uses a bitwise AND (i & 1) instead of a modulo operation. Bitwise checks are marginally faster because they avoid division, which can be beneficial inside a tight loop.

Storing the pending element in a single scalar variable (prev) eliminates the need for additional data structures to track state between iterations. This compact state management contributes to both speed and low memory usage.

Imagine a line of bouncy balls of all different sizes. Some are big and some are small. To arrange them perfectly, the goal is to make sure every ball is either taller than its neighbors or shorter than its neighbors. It creates a wavy pattern like a roller coaster.

First, the numbers are lined up from smallest to biggest, just like putting blocks in order by height. To make the wavy pattern, the computer picks two balls at a time. It takes the smallest ball and the next biggest ball. It places the smaller one down first, and then the bigger one right next to it. By jumping back and forth between the tiny ones and the giant ones, the line starts to zig and zag. The computer keeps doing this, pairing up the balls and swapping their spots until every single one has a neighbor that is either shorter or taller. When the line is finished, the bouncy balls look like a bumpy hills and valleys path that goes up and down all the way to the end. If an extra ball is left over at the very end because of an odd number, it just gets added to the back of the line to finish the pattern.

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

Time: loglinear
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	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	fsq	C++
	JoshCrozier			JS
	lkwq007		Python
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
fsq	C++
JoshCrozier	JavaScript
lkwq007	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