Array With Elements Not Equal to Average of Neighbors - Solution & Explanation
Problem Statement
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] <= 105
Approach Overview
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.
Approach 1: Sort and Interleave Strategy
Sort the array and then divide it into two halves. Interleave elements from both halves to form the rearrangement. This strategy works because the interleaving breaks the sequence that might result in the middle element being the average of its neighbors.
To be specific, split the sorted array into two: one for the even indexed positions and the other for odd indexed positions. By placing the smaller half in even positions and the larger half in odd positions, we ensure no element is the average of its neighbors.
The code first sorts the input array. It then defines a variable half to find the midpoint. By iterating through the first half of the array, the code appends an element from the first half followed by an element from the second half, creating an interleaved sequence. The strategy ensures that no element is equal to the average of its neighbors.
Code
Python
JavaScript
Complexity
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing the result.
Approach 2: Greedy Zig-Zag Strategy
Another approach is based on sorting the array and then arranging it in a zig-zag pattern. The goal is to position larger numbers adjacent to smaller numbers strategically. By doing this, the middle number in any triplet is unlikely to be the average of its neighbors since the fluctuation between numbers disrupts that average.
The C++ code sorts the input array and uses a two-pointer technique to arrange elements in an alternating higher-lower manner. This method distributes elements in a way that prevents any middle element from being the average of its neighbors.
Complexity
Time Complexity: O(n log n) because of sorting.
Space Complexity: O(n) for output storage.
Approach 3: Sorting
Since the elements in the array are distinct, we can first sort the array, then divide the array into two parts. Place the first half of the elements in the even positions of the answer array, and the second half of the elements in the odd positions of the answer array. In this way, for each element, its two adjacent elements will not be equal to its average value.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sort and Interleave Strategy | Time Complexity: |
| Greedy Zig-Zag Strategy | Time Complexity: |
| Sorting | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort and Interleave Strategy | O(n log n) | O(n) | Best for clarity and easy implementation when building a new array is acceptable |
| Greedy Zig-Zag Strategy | O(n log n) | O(1) | Preferred when minimizing extra memory and performing in-place rearrangement |
Video Solution
Array With Elements Not Equal to Average of Neighbors - Leetcode 1968 - Python • NeetCode • 15,527 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Array With Elements Not Equal to Average of Neighbors easy or hard?
Array With Elements Not Equal to Average of Neighbors Python/Java solution
How to solve Array With Elements Not Equal to Average of Neighbors in O(n)?
What is the best approach for Array With Elements Not Equal to Average of Neighbors?
Is Array With Elements Not Equal to Average of Neighbors asked at Google/Amazon/Meta?
What data structure is used in Array With Elements Not Equal to Average of Neighbors?
What is the time complexity of Array With Elements Not Equal to Average of Neighbors?
Ready to solve this problem?
Practice Array With Elements Not Equal to Average of Neighbors with our built-in code editor and test cases.
Practice on FleetCode