<p>You are given a <strong>0-indexed</strong> array <code>nums</code> of <strong>distinct</strong> integers. You want to rearrange the elements in the array such that every element in the rearranged array is <strong>not</strong> equal to the <strong>average</strong> of its neighbors.</p>

<p>More formally, the rearranged array should have the property such that for every <code>i</code> in the range <code>1 &lt;= i &lt; nums.length - 1</code>, <code>(nums[i-1] + nums[i+1]) / 2</code> is <strong>not</strong> equal to <code>nums[i]</code>.</p>

<p>Return <em><strong>any</strong> rearrangement of </em><code>nums</code><em> that meets the requirements</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4,5]
<strong>Output:</strong> [1,2,4,5,3]
<strong>Explanation:</strong>
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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [6,2,0,9,7]
<strong>Output:</strong> [9,7,6,2,0]
<strong>Explanation:</strong>
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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        nums.sort()
        l=1
        n=len(nums)
        r=n-1
        if(n<3):
            return nums
        #You want to create a zig zag pattern, so just interchange elements pairwise 
        #[a,b1,b2,c1,c2]->[a,b2,b1,c2,c1]--> b2>b1,a;  b1<c2,b2; c2>c1,b1
        #Hence we're done
        while(l+1<n):
            nums[l],nums[l+1]=nums[l+1],nums[l]
            l+=2
        return nums
'''
Basically idea is to rearrage an array in alternate increasing decreasing sequence IDIDIDI... or DIDIDIDI...
At its core, this approach is based on the fact that the average of two numbers can never be lower than the smallest of the two elements, nor higher than the largest of the two elements. This means that if an element's neighbors are both smaller than itself, then the average of those two neighbors will be smaller than the element in question. The same is true for larger elements as well, though with the average being larger than the element in question. So what we can do is go through the array and, in a sense, rearrange it into a series of peaks and valleys, that way ensuring that we meet the no average criteria.
'''
class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        l=1
        n=len(nums)
        while(l+1<n):
            if (nums[l-1]<nums[l]<nums[l+1] or nums[l-1]>nums[l]>nums[l+1]): #we know nums are distinct
                nums[l],nums[l+1]=nums[l+1],nums[l]
            l+=1
        return nums
            
573