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] <= 105Sort 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.
JavaScript
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing the result.
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.
Java
Time Complexity: O(n log n) because of sorting.
Space Complexity: O(n) for output storage.
| Approach | Complexity |
|---|---|
| Sort and Interleave Strategy | Time Complexity: |
| Greedy Zig-Zag Strategy | Time Complexity: |
Median of Two Sorted Arrays - Binary Search - Leetcode 4 • NeetCode • 551,893 views views
Watch 9 more video solutions →Practice Array With Elements Not Equal to Average of Neighbors with our built-in code editor and test cases.
Practice on FleetCode