Problem Description

Given an integer array nums, rearrange the elements of nums so that no element is equal to the average of its immediate neighbors. In other words, for every index i (where 1 ≤ i < nums.length - 1), you must ensure:
nums[i] ≠ (nums[i-1] + nums[i+1]) / 2

• Return any valid rearrangement of the array that satisfies this rule.
• Each element of nums must be used exactly once (no reusing or omitting elements).
• If there are multiple valid answers, return any one of them.

Thought Process

The brute-force approach would be to check all possible permutations of nums and see if any arrangement satisfies the condition. However, this quickly becomes infeasible as the number of permutations grows factorially with the array size.

Instead, let's think about why an element might be equal to the average of its neighbors. This happens when the element is "between" two values in a sorted sense. For example, if the neighbors are the smallest and largest, the middle value would be their average. So, to avoid this, we can try to arrange the numbers so that large and small values alternate, preventing any value from being the average of its neighbors.

This leads us to consider sorting the array and then interleaving the smallest and largest halves, so that adjacent numbers are as different as possible.

Solution Approach

To construct a valid arrangement efficiently, follow these steps:

1. Sort the input array nums in ascending order.
2. Split the sorted array into two halves:
   • The first half contains the smaller elements.
   • The second half contains the larger elements.
3. Interleave the two halves: place one element from the smaller half, then one from the larger half, and repeat.
4. If the array length is odd, one half will have one more element; start with that half.
5. This arrangement ensures no element is the average of its neighbors, because adjacent elements will differ significantly in value.

This approach works because, by separating similar values, we avoid having three consecutive values that form an arithmetic progression (which would cause the middle one to be the average of its neighbors).

Example Walkthrough

Let's consider nums = [1, 2, 3, 4, 5, 6].

1. Sort nums (already sorted): [1, 2, 3, 4, 5, 6]
2. Split into halves:
   • First half: [1, 2, 3]
   • Second half: [4, 5, 6]
3. Interleave:
   • Take from first half: 1
   • Take from second half: 4
   • Take from first half: 2
   • Take from second half: 5
   • Take from first half: 3
   • Take from second half: 6

   Result: [1, 4, 2, 5, 3, 6]

4. Check for the condition:
   • For index 1: (1 + 2)/2 = 1.5 ≠ 4
   • For index 2: (4 + 5)/2 = 4.5 ≠ 2
   • For index 3: (2 + 3)/2 = 2.5 ≠ 5
   • For index 4: (5 + 6)/2 = 5.5 ≠ 3

   Condition satisfied for all indices.

Time and Space Complexity

• Brute-force approach:
  • Time complexity: O(n!) due to checking all permutations.
  • Space complexity: O(n) for storing permutations and checks.
• Optimized approach (interleaving sorted halves):
  • Time complexity: O(n log n) for sorting, O(n) for interleaving — overall O(n log n).
  • Space complexity: O(n) for the new arrangement.

Summary

By sorting the array and interleaving its smallest and largest halves, we ensure that no element is the average of its neighbors. This approach is both efficient and simple to implement, avoiding the need to check all permutations. The key insight is that separating similar values prevents the formation of arithmetic progressions, which would otherwise violate the problem's condition.

Code Implementation

class Solution:
    def rearrangeArray(self, nums):
        nums.sort()
        n = len(nums)
        res = []
        mid = (n + 1) // 2
        left = nums[:mid]
        right = nums[mid:]
        l, r = 0, 0
        for i in range(n):
            if i % 2 == 0:
                res.append(left[l])
                l += 1
            else:
                res.append(right[r])
                r += 1
        return res
      

class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> res(n);
        int mid = (n + 1) / 2;
        int l = 0, r = mid;
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0) {
                res[i] = nums[l++];
            } else {
                res[i] = nums[r++];
            }
        }
        return res;
    }
};
      

class Solution {
    public int[] rearrangeArray(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int[] res = new int[n];
        int mid = (n + 1) / 2;
        int l = 0, r = mid;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                res[i] = nums[l++];
            } else {
                res[i] = nums[r++];
            }
        }
        return res;
    }
}
      

var rearrangeArray = function(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const res = [];
    const mid = Math.floor((n + 1) / 2);
    let l = 0, r = mid;
    for (let i = 0; i < n; i++) {
        if (i % 2 === 0) {
            res.push(nums[l++]);
        } else {
            res.push(nums[r++]);
        }
    }
    return res;
};