You are given a 0-indexed array nums of distinct integers. You want to rearrange the elements in the array such that every element in the rearranged array is not equal to the average of its neighbors.
More formally, the rearranged array should have the property such that for every i in the range 1 <= i < nums.length - 1, (nums[i-1] + nums[i+1]) / 2 is not equal to nums[i].
Return any rearrangement of nums that meets the requirements.
Example 1:
Input: nums = [1,2,3,4,5] Output: [1,2,4,5,3] Explanation: When i=1, nums[i] = 2, and the average of its neighbors is (1+4) / 2 = 2.5. When i=2, nums[i] = 4, and the average of its neighbors is (2+5) / 2 = 3.5. When i=3, nums[i] = 5, and the average of its neighbors is (4+3) / 2 = 3.5.
Example 2:
Input: nums = [6,2,0,9,7] Output: [9,7,6,2,0] Explanation: When i=1, nums[i] = 7, and the average of its neighbors is (9+6) / 2 = 7.5. When i=2, nums[i] = 6, and the average of its neighbors is (7+2) / 2 = 4.5. When i=3, nums[i] = 2, and the average of its neighbors is (6+0) / 2 = 3.
Constraints:
3 <= nums.length <= 1050 <= nums[i] <= 105In #1968 Array With Elements Not Equal to Average of Neighbors, the goal is to rearrange an array so that for every valid index i, the element nums[i] is not equal to the average of its neighbors (nums[i-1] + nums[i+1]) / 2. A common observation is that this equality occurs when three elements form an arithmetic progression. Therefore, the strategy is to rearrange the numbers so such patterns are avoided.
A practical greedy approach is to first sort the array. After sorting, slightly disturb the order so consecutive elements do not form evenly spaced values. One simple technique is swapping adjacent elements in pairs or interleaving smaller and larger values. This breaks potential arithmetic triplets that could appear in a purely sorted sequence.
Sorting ensures predictable ordering, while controlled swaps guarantee that middle elements are not the average of their neighbors. The overall time complexity is dominated by sorting, and the rearrangement step runs in linear time.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting + Greedy Rearrangement | O(n log n) | O(1) to O(n) |
| Pairwise Swapping After Sorting | O(n log n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
A number can be the average of its neighbors if one neighbor is smaller than the number and the other is greater than the number.
We can put numbers smaller than the median on odd indices and the rest on even indices.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Sorting organizes values so that potential arithmetic patterns become predictable. By swapping or interleaving elements after sorting, you break evenly spaced triples that could satisfy the average condition. This simple disturbance prevents the middle element from equaling the average of its neighbors.
While the exact problem may not always appear, similar array rearrangement and greedy pattern-breaking questions are common in technical interviews. Companies often test a candidate’s ability to recognize patterns like arithmetic sequences and apply sorting-based strategies.
The problem mainly relies on arrays and sorting rather than advanced data structures. A standard array combined with a sorting algorithm is sufficient. After sorting, simple index manipulation or swapping ensures the required condition holds.
The optimal strategy is to sort the array and then rearrange elements using a greedy method such as swapping adjacent pairs. This disrupts potential arithmetic progressions where the middle element equals the average of its neighbors. The sorting step dominates the runtime at O(n log n).