Array With Elements Not Equal to Average of Neighbors
LeetCode 1968. Array With Elements Not Equal to Average of Neighbors gives you a 0-indexed array nums of distinct integers. Your task is to rearrange the elements so that for every index i where 1 <= i <= n - 2, nums[i] does not equal the average of nums[i - 1] and nums[i + 1].
In other words, no interior element should sit exactly halfway between its two neighbors.
The problem
Given nums = [1, 2, 3, 4, 5], the original order violates the constraint because nums[1] = 2 equals (1 + 3) / 2, nums[2] = 3 equals (2 + 4) / 2, and nums[3] = 4 equals (3 + 5) / 2. You need to rearrange the array so none of these equalities hold.
The problem guarantees that a valid rearrangement always exists.
The approach: sort and interleave
The idea is simple. Sort the array, split it into two halves, and interleave them. Place elements from the smaller half and larger half in alternating positions.
Why does this work? After sorting, every element in the first half is strictly less than every element in the second half (the values are distinct). When you interleave, each element from the smaller half is surrounded by elements from the larger half, and vice versa. An element cannot be the average of two neighbors that are both strictly larger than it, or both strictly smaller than it. The average of two values that are both bigger than x must also be bigger than x. The average of two values that are both smaller than x must also be smaller than x. Either way, x cannot equal that average.
Here is the concrete process for nums = [1, 2, 3, 4, 5]:
- Sort:
[1, 2, 3, 4, 5] - Split: small =
[1, 2, 3], large =[4, 5] - Interleave: take one from small, one from large, repeat. Result:
[1, 4, 2, 5, 3]
def rearrangeArray(nums: list[int]) -> list[int]:
nums.sort()
n = len(nums)
mid = (n + 1) // 2
small = nums[:mid]
large = nums[mid:]
result = []
for i in range(mid):
result.append(small[i])
if i < len(large):
result.append(large[i])
return result
Visual walkthrough
Let's trace through nums = [1, 2, 3, 4, 5] step by step.
Sort the array
nums = [1,2,3,4,5] is already sorted. Sorting guarantees a clear boundary between small and large values.
Split into two halves
With n=5, mid = n//2 = 2 (index 2 is the last element of the first half, giving us ceil(n/2) = 3 elements). Small = [1,2,3], large = [4,5].
Green = smaller half, amber = larger half.
Interleave: alternate small and large
Take one from small, one from large, repeating until both are exhausted. Result: [1, 4, 2, 5, 3].
Each small value is flanked by larger values. No element can be the average of its neighbors.
Verify the constraint
For each interior element, check that it does not equal the average of its two neighbors:
Adjacent elements always come from different halves. Because every value in the smaller half is strictly less than every value in the larger half, no element can ever equal the average of two values that are both larger or both smaller than itself.
After interleaving, the result is [1, 4, 2, 5, 3]. Every interior element has neighbors from the opposite half, making it impossible for the average constraint to be violated.
Complexity
| Aspect | Complexity |
|---|---|
| Time | O(n log n) |
| Space | O(n) |
Time is dominated by the sort. The interleaving step is a single O(n) pass. Together, O(n log n).
Space is O(n) because the solution builds a new result array. You could also do the interleave in-place with a deque-style approach, but the O(n) version is cleaner and the space is no worse than the sort itself in Python.
The building blocks
This problem is built from two reusable bricks that appear across many sorting and greedy problems.
Sorting as preprocessing
Sorting transforms an unstructured problem into one with clear guarantees. Once sorted, you know exactly where the boundary between "small" and "large" values is. You do not need to reason about arbitrary orderings. Many greedy problems use sorting as the first step to unlock a simple linear-time strategy: merge intervals, meeting rooms, and this interleaving problem all follow this pattern.
Two-pointer interleaving
The interleaving step is a variant of the merge step from merge sort. You maintain two read pointers (one in each half) and one write pointer into the result. The twist is that instead of comparing and picking the smaller element, you alternate unconditionally. This same brick shows up in Wiggle Sort II, where you interleave the halves into even and odd positions.
Edge cases
Two elements. With n = 2, there are no interior elements. Any arrangement is valid. The algorithm returns the sorted pair, which works trivially.
Three elements. With distinct values like [1, 2, 3], the sorted order violates the constraint because 2 = (1 + 3) / 2. After interleaving, you get [1, 3, 2]. Check: 3 does not equal (1 + 2) / 2 = 1.5. Valid.
Already valid. The algorithm does not check whether the input already satisfies the constraint. It always sorts and interleaves. This is fine because the result is guaranteed to be valid, and checking first would not save time (you would still need O(n) to verify).
From understanding to recall
The core insight here is that interleaving two sorted halves prevents any element from being the average of its neighbors. That is the one thing to internalize.
When you practice this problem with spaced repetition, focus on the split point. With n elements, the smaller half gets ceil(n/2) elements and the larger half gets floor(n/2). The interleaving loop takes one from each half in turn, starting with the smaller half. If you can write that loop from memory, the rest is just calling sort() beforehand.
The mnemonic: sort, split, alternate. Three words, three lines of logic. Everything else is bookkeeping.
Related posts
- Wiggle Sort II - The same sort-split-interleave pattern, but with strict inequality requirements that force you to fill from the ends of each half
- Sort Colors - Another array rearrangement problem using partitioning, this time with three categories instead of two halves
- Sort an Array - If you want to understand the sorting step itself, this post covers merge sort and quicksort from scratch