# Array With Elements Not Equal to Average of Neighbors
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/array-with-elements-not-equal-to-average-of-neighbors)
Canonical: https://scaleengineer.com/dsa/problems/array-with-elements-not-equal-to-average-of-neighbors
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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.
Note that the original array [6,2,0,9,7] also satisfies the conditions.

**Constraints:**

* `3 <= nums.length <= 105`
* `0 <= nums[i] <= 105`

# Approaches
## Brute Force with Permutations
This approach explores every possible arrangement of the numbers in the input array. It generates all permutations and, for each one, checks if it satisfies the given condition that no element is the average of its neighbors. Since the problem guarantees a solution exists, this method will eventually find one.
**Time:** O(n! * n). There are `n!` permutations to generate, and checking each one for validity takes O(n) time. · **Space:** O(n! * n) in the worst case to store all permutations, or O(n) for the recursion stack if we check permutations as they are generated.
**Pros:** Guaranteed to find a solution.; Conceptually simple to understand.
**Cons:** Extremely inefficient due to its factorial time complexity.; Only feasible for very small input sizes (e.g., n < 12).; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
The core idea is to exhaustively try every single possible ordering of the `nums` array. We can write a recursive function that generates all permutations. For each generated permutation, we iterate from the second element to the second-to-last element (`i` from 1 to `n-2`) and check if the condition `nums[i] * 2 == nums[i-1] + nums[i+1]` is ever true. If we find a permutation where the condition is never true for any `i`, we have found a valid solution and can return it. While correct, this method is computationally prohibitive.

```java
class Solution {
    public int[] rearrangeArray(int[] nums) {
        List<Integer> currentPermutation = new ArrayList<>();
        for (int num : nums) {
            currentPermutation.add(num);
        }
        List<List<Integer>> allPermutations = new ArrayList<>();
        generatePermutations(0, currentPermutation, allPermutations);

        for (List<Integer> p : allPermutations) {
            if (isValid(p)) {
                int[] result = new int[nums.length];
                for (int i = 0; i < nums.length; i++) {
                    result[i] = p.get(i);
                }
                return result;
            }
        }
        return new int[]{}; // Should not be reached
    }

    private void generatePermutations(int index, List<Integer> nums, List<List<Integer>> allPermutations) {
        if (index == nums.size()) {
            allPermutations.add(new ArrayList<>(nums));
            return;
        }
        for (int i = index; i < nums.size(); i++) {
            Collections.swap(nums, index, i);
            generatePermutations(index + 1, nums, allPermutations);
            Collections.swap(nums, index, i); // backtrack
        }
    }

    private boolean isValid(List<Integer> nums) {
        for (int i = 1; i < nums.size() - 1; i++) {
            if (2 * nums.get(i) == nums.get(i - 1) + nums.get(i + 1)) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Define a recursive function, say `findPermutation(index, currentNums)`, to generate all permutations.
- The base case for the recursion is when `index` reaches the array length. At this point, `currentNums` is a full permutation.
- For each complete permutation, check if it is a valid arrangement using a helper function.
- The helper function `isValid(arr)` iterates from `i = 1` to `n-2` and returns `false` if it finds any `i` where `2 * arr[i] == arr[i-1] + arr[i+1]`.
- If a valid permutation is found, return it.
- In the recursive step, iterate from `index` to the end of the array. For each element, swap it with the element at `index`, recurse with `findPermutation(index + 1, currentNums)`, and then backtrack by swapping back.

## Sorting and Interleaving
A much more efficient approach is to first sort the array and then construct a new array by arranging the elements in a specific "zigzag" or "wave" pattern. This pattern ensures that no element is the average of its neighbors.
**Time:** O(n log n), dominated by the sorting step. The construction of the result array takes O(n) time. · **Space:** O(n) to store the result array. The space complexity of sorting can also be O(log n) or O(n) depending on the implementation used.
**Pros:** Significantly faster than brute force, with a polynomial time complexity.; Guaranteed to produce a correct result.; The logic is relatively straightforward to prove.
**Cons:** Not the most optimal time complexity due to the sorting step.; Requires extra space for the result array, making it not an in-place solution.
### Explanation
The condition `nums[i] == (nums[i-1] + nums[i+1]) / 2` can only be true if `nums[i]` lies strictly between `nums[i-1]` and `nums[i+1]`. We can prevent this by constructing an array where every element is a local extremum (either a peak or a valley). This can be achieved by sorting the array and then interleaving the smaller and larger halves.

1.  Sort the input array `nums`.
2.  Create a new `result` array.
3.  Place the smaller half of the sorted numbers at the even indices of the `result` array and the larger half at the odd indices.

This creates a pattern like `small, large, small, large, ...`. In such a pattern, any element `nums[i]` is either smaller than both its neighbors (a valley) or larger than both its neighbors (a peak). Therefore, it can never be their average.

```java
import java.util.Arrays;

class Solution {
    public int[] rearrangeArray(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int[] res = new int[n];
        int left = 0;
        int right = n - 1;

        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                res[i] = nums[left++];
            } else {
                res[i] = nums[right--];
            }
        }
        return res;
    }
}
```
### Algorithm
- Sort the input array `nums` in non-decreasing order.
- Create a new result array `res` of the same size `n`.
- Iterate through the sorted `nums` array with a single pointer `k=0`.
- First, fill all the even indices (`0, 2, 4, ...`) of `res` with elements from `nums` starting from `nums[0]`.
- Then, fill all the odd indices (`1, 3, 5, ...`) of `res` with the remaining elements from `nums`.
- Return the `res` array.

## Greedy In-place Wave Sort
The most optimal approach rearranges the array in-place to form a "wave" pattern in a single pass. This avoids the `O(n log n)` cost of sorting and requires no extra space.
**Time:** O(n), as it involves a single pass through the array with constant time operations at each step. · **Space:** O(1), as the rearrangement is done in-place with no auxiliary data structures.
**Pros:** Optimal O(n) time complexity.; Optimal O(1) space complexity as it operates in-place.; Very simple and concise to implement.
**Cons:** The proof of correctness is slightly more subtle than the sorting approach, as one must verify that a local swap does not invalidate previously established parts of the wave.
### Explanation
The key insight is that we only need to ensure a local property, and we can do so greedily. We can enforce a wave-like structure (`a <= b >= c <= d >= ...`) directly on the input array without a full sort. Since all elements are distinct, the relations will be strict `<` and `>`.

We iterate through the array from the second element (`i = 1`). At each position `i`, we enforce the correct relationship with the previous element `i-1`.
- If `i` is odd, we want a 'peak', so `nums[i]` should be greater than or equal to `nums[i-1]`. If not, we swap them.
- If `i` is even, we want a 'valley', so `nums[i]` should be less than or equal to `nums[i-1]`. If not, we swap them.

This single pass is sufficient to transform the array into a valid wave. Each swap corrects the local order without disrupting the previously established wave property. Since the final array is a wave, every element is a local extremum, which satisfies the problem's condition.

```java
class Solution {
    public int[] rearrangeArray(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            // If i is odd, we want nums[i] > nums[i-1]
            if (i % 2 == 1) {
                if (nums[i] < nums[i-1]) {
                    swap(nums, i, i - 1);
                }
            } 
            // If i is even, we want nums[i] < nums[i-1]
            else {
                if (nums[i] > nums[i-1]) {
                    swap(nums, i, i - 1);
                }
            }
        }
        return nums;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
```
### Algorithm
- Iterate through the `nums` array from `i = 1` to `n-1`.
- For each `i`, check if it and its predecessor `nums[i-1]` follow the desired wave pattern.
- If `i` is odd, we want `nums[i-1] <= nums[i]`. If `nums[i-1] > nums[i]`, swap them.
- If `i` is even, we want `nums[i-1] >= nums[i]`. If `nums[i-1] < nums[i]`, swap them.
- After the loop, the array will be in a valid wave form.
- Return the modified `nums` array.

# Solutions
### Java

```java
class Solution {
public
  int[] rearrangeArray(int[] nums) {
    Arrays.sort(nums);
    int n = nums.length;
    int m = (n + 1) >> 1;
    int[] ans = new int[n];
    for (int i = 0, j = 0; i < n; i += 2, j++) {
      ans[i] = nums[j];
      if (j + m < n) {
        ans[i + 1] = nums[j + m];
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> rearrangeArray(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    vector<int> ans;
    int n = nums.size();
    int m = (n + 1) >> 1;
    for (int i = 0; i < m; ++i) {
      ans.push_back(nums[i]);
      if (i + m < n)
        ans.push_back(nums[i + m]);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]: nums . sort() n = len(nums) m = (n + 1) >> 1 ans = [] for i in range(m): ans . append(nums[i]) if i + m < n: ans . append(nums[i + m]) return ans

```