Formatted question description: https://leetcode.ca/all/1968.html

# 1968. Array With Elements Not Equal to Average of Neighbors

## Level

Medium

## Description

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 <= 10^5`

`0 <= nums[i] <= 10^5`

## Solution

One simple way is to rearrange elements so that element element that is not the first element or the last element is either greater than both neighbors or less than both neighbors. Sort array `nums`

. Let `left = 0`

and `right = nums.length - 1`

. Create an array `rearrange`

of the same length as `nums`

. For any `i`

, if `i`

is even, then let `rearrange[i] = nums[left]`

and increase `left`

by 1. If `i`

is odd, then let `rearrange[i] = nums[right]`

and decrease `right`

by 1. Finally, return `rearrange`

.

```
class Solution {
public int[] rearrangeArray(int[] nums) {
Arrays.sort(nums);
int length = nums.length;
int[] rearrange = new int[length];
int left = 0, right = length - 1;
for (int i = 0; i < length; i++) {
if (i % 2 == 0) {
rearrange[i] = nums[left];
left++;
} else {
rearrange[i] = nums[right];
right--;
}
}
return rearrange;
}
}
```