Array With Elements Not Equal to Average of Neighbors - Solution & Explanation

Problem Overview: Given an integer array, rearrange the elements so that for every valid index i, the value nums[i] is not equal to the average of its neighbors (nums[i-1] + nums[i+1]) / 2. You can return any valid permutation of the array.

Approach 1: Sort and Interleave Strategy (O(n log n) time, O(n) space)

This approach relies on sorting followed by a simple rearrangement. First, sort the array in ascending order. Then build a new array by interleaving smaller and larger halves so adjacent numbers differ significantly. A common pattern is to place smaller elements at even indices and larger elements at odd indices. Because neighbors now come from different halves of the sorted list, the middle value rarely equals the average of its neighbors.

The key insight: when the array is sorted, the average of two distant values rarely equals a third element positioned between them. By separating low and high values during placement, you avoid symmetric patterns that create averages. Implementation simply iterates through the sorted array and fills positions alternately. Sorting dominates the runtime, giving O(n log n) time and O(n) extra space for the result array. This method is easy to implement and works reliably for all valid inputs.

Approach 2: Greedy Zig-Zag Strategy (O(n log n) time, O(1) extra space)

This method also begins with sorting but performs in-place rearrangement using a greedy zig-zag pattern. After sorting, iterate through the array and swap adjacent pairs starting from index 1: swap nums[i] and nums[i+1] for every odd index. This produces a pattern like a0 < a2 > a1 < a4 > a3. Because each middle element becomes either strictly larger or strictly smaller than its neighbors, it cannot equal their average.

The insight comes from greedy local adjustments. By ensuring alternating peaks and valleys, you prevent any element from sitting exactly between its neighbors. The algorithm performs a single pass of swaps after sorting, so the complexity remains O(n log n) time due to sorting and O(1) additional space since the rearrangement happens in-place. The approach works well when minimizing memory usage.

Both solutions rely on the structure created by array ordering after sorting. Once elements are spaced apart in value, the arithmetic average condition becomes very unlikely.

Recommended for interviews: The Sort and Interleave strategy is typically the clearest explanation during interviews. It demonstrates understanding of ordering and value distribution. The Greedy Zig-Zag swap method shows stronger in-place optimization skills and is often preferred when discussing space complexity trade-offs.