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 &lt;= i &lt; 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.

&nbsp;
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.


&nbsp;
Constraints:


	3 &lt;= nums.length &lt;= 105
	0 &lt;= nums[i] &lt;= 105


class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        for i in range(1, len(nums) -1):
            pre = nums[i-1]
            current = nums[i]
            next = nums[i+1]
            
            # If block will run when we meet 1 2 3 or 6 4 2
            if (pre < current < next) or (pre > current > next):
                # Swap next and current
                # For example: 
                # 1 2 3 -> 1 3 2
                # 6 4 2 -> 6 2 4
                nums[i+1], nums[i] = nums[i], nums[i+1]
                
        return nums
class Solution {
    public int[] rearrangeArray(int[] nums) {
       Arrays.sort(nums);
       // sort in wave format
        for(int i = 0;i<nums.length-1;i+=2){
            int temp = nums[i];
            nums[i] = nums[i+1];
            nums[i+1] = temp;
        }
        return nums;
    }
}
//Approach-1 (Using sorting O(nlogn))
/*
    If you make sure that
    nums[i-1] < nums[i] > nums[i+1]
    You are good to go.

    So, just sort the input and choose wisely to satisfy above condition.

    Example :
    [6,2,0,9,7]
    sort it : [0, 2, 6, 7, 9]

    result : [0, _, 2, _, 6] - 1st loop (fill alternaltely)
    result : [0, 7, 2, 9, 6] - 2nd loop (fill next larger numbers from nums to result in spaces left)

*/

class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        int n = nums.size();
        sort(begin(nums), end(nums));

        vector<int> result(n);
        int j = 0;
        int i = 0;
        for(; i < n && j < n; i++, j += 2) //alternately fill so that you leave one space in between for large number
            result[j] = nums[i];

        j = 1;
        for(; i < n && j < n; i++, j += 2) //filter the large number in spaces between that we left above
            result[j] = nums[i];

        return result;
    }
};
var rearrangeArray = function(nums) {
    let arr=[], res=[]
    for(let q of nums) arr[q]= 1

    let l=0, r=arr.length-1
    while(l<=r){
        while(!arr[l])l++
        while(!arr[r])r--
        if(l<=r)res.push(l++)
        if(l<=r)res.push(r--)
    }
    return res
};
Array With Elements Not Equal to Average of Neighbors