<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]:
        # find a permutation of nums where nums[i] != (nums[i-1] + nums[i+1]) / 2

        # parity? e.g. eoeo nope, 2+4 avg is 3, odd
        #         eeoeeo... same problem
        #         etc. same problem

        # must be some kind of obvious pattern in O(n log(n)) or faster

        # suppose we sort
        # then we put the smallest number, then the largest number
        #
        #   min max 2ndLowest 2ndHighest ...
        #
        # then we'd have each k**th highest surrounded by two values lower than it
        # and each low value surrounded by 2 higher values
        # such that the average can't match
        # e.g. 1 2 3 4 5 6 7 8 9
        #
        # 1 9 2 8 3 7 4 6 5
        # last value has only one neighbor and is exempt

        # nums.sort()
        # l = 0
        # r = len(nums)-1
        # out = [0]*len(nums)
        # i = 0
        # while l < r:
        #     out[i] = nums[l]
        #     out[i+1] = nums[r]
        #     i += 2
        #     l += 1
        #     r -= 1

        ##### what if we swap?
        #
        # from looking at other solutions: something about an up-down pattern
        #
        # we can only have b = (a+c)/2 if a,b,c are sorted
        # therefore if we have a < b < c then we swap c, b to guarantee no violation
        #
        # if a < b < c then we swap b,c so we get an up-down pattern
        #   a c b
        #    U D
        #
        # now we have c b d
        #              D
        #
        # if b > d, then c > b > d may be a violation
        # so we'd swap b,d ; in here we know that
        #    the decrese from c to next element is all we need to fix earlier violations
        #    d < b

        ### Swap-based also:
        # if the pattern of changes is UDUDUD... or DUDUDU... then there's no
        # violation, each element is sandwiched between adjacent elements that are
        # either both lower or both higher
        #
        # suppose we've fixed ..... a b where a < b, state U because b is higher than prior
        #   then a < b < c; we have two U in a row. this might cause a violation
        #   so swap b and c:
        #       UU or DD means c is the "same direction" from a as b, even larger or smaller
        #       so swapping doesn't change the U or D: if a < b < c then a < c
        #       but swapping DOES change the subsequent sign of the change

        n = len(nums)
        inc = nums[1] > nums[0] # is i > prior element?
        for i in range(1, n-1):
            if inc == (nums[i+1] > nums[i]):
                # consecutive increases or decreases may cause violation
                #     if we swap i, i+1 then we change an increase to a decrease
                #     but the new i (current i+1) compares the same was as i does
                #     to i+1
                # and therefore we can swap to fix i-1..i+1 without changing
                # the sign pattern of prior differences and thus introducing
                # any violation to earlier elements
                nums[i], nums[i+1] = nums[i+1], nums[i]

            # whole point of our swap is to make sure we toggle the sign of the
            # last increase
            inc = not inc

        return nums
287