Array With Elements Not Equal to Average of Neighbors

Array With Elements Not Equal to Average of Neighbors

What is this problem about?

The Array With Elements Not Equal to Average of Neighbors interview question asks you to reorder a given array such that for every index i (where 1 < i < n-1), the element nums[i] is not equal to the average of its immediate neighbors, (nums[i-1] + nums[i+1]) / 2. This Array With Elements Not Equal to Average of Neighbors coding problem is about breaking local patterns.

Why is this asked in interviews?

Uber and Microsoft use this to see if a candidate can find a clever constructive solution rather than trying every permutation. It tests "Wiggle" or "Zig-zag" logic—the idea that if you alternate between small and large values, a number can never be the average of its neighbors.

Algorithmic pattern used

This follows the Array, Sorting, Greedy interview pattern. A robust way to solve this is to sort the array and then alternate between elements from the first half and the second half. This creates a "peak and valley" pattern where every element is either larger than both its neighbors or smaller than both.

Example explanation

Consider nums = [1, 2, 3, 4, 5].

1. Sorted: [1, 2, 3, 4, 5].
2. Smallest half: [1, 2]. Largest half: [3, 4, 5].
3. Interleave: [1, 3, 2, 4, 5]. Check 3: Average of 1 and 2 is 1.5. 3 != 1.5. Check 2: Average of 3 and 4 is 3.5. 2 != 3.5. Check 4: Average of 2 and 5 is 3.5. 4 != 3.5. The condition is satisfied.

Common mistakes candidates make

• Trying Brute Force: Attempting to shuffle or permute until a condition is met, which is highly inefficient for large arrays.
• Ignoring Math: Failing to realize that the average property is only possible if nums[i-1] < nums[i] < nums[i+1] or vice versa. By ensuring nums[i] is a local minimum or maximum, you automatically avoid this.
• Odd/Even Lengths: Handling the split of the array incorrectly when the length is odd.

Interview preparation tip

Constructive problems often have a "sorting-based" shortcut. If you need to avoid a specific linear relationship between adjacent elements, try arranging them in a "high-low-high" or "zig-zag" order.