Problem Description
Given a 0-indexed array of distinct integers, rearrange its elements so that for every index i with 1 ≤ i < n - 1, the element nums[i] is not equal to the average of its neighbors (i.e. (nums[i-1] + nums[i+1]) / 2). Return any valid rearrangement.
Key Insights
- The problem is equivalent to avoiding configurations where three consecutive elements form an arithmetic progression.
- Sorting the array and then swapping adjacent elements (or interweaving two halves) will help ensure that no element becomes the exact average of its two neighbors.
- This is similar in spirit to the "wiggle sort" where the relative order of elements prevents arithmetic progression scenarios.
- A simple greedy approach that leverages sorting ensures that the large gap between numbers is distributed appropriately.
Space and Time Complexity
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) in the worst-case scenario if a new array is used, or O(1) if the rearrangement is done in-place.
Solution
The solution first sorts the given array. After sorting, a simple technique is to swap every pair of adjacent elements (starting from index 1). This creates a "wave" pattern in the array. In such a rearrangement, the middle element in any three consecutive elements is prevented from being the exact average of its two neighbors because the differences are not uniform. This approach is both easy to implement and efficient.