Array With Elements Not Equal to Average of Neighbors

Related: Wiggle Sort

TARGET DECK: Leetcode FILE TAGS:

Intuition

• For every middle element x[i], to satisfy the property that (nums[i-1] + nums[i+1]) / 2 is not equal to nums[i]:
  • Notice that x[i] - x[i - 1] cannot equal x[i + 1] - x[i].
    • Since otherwise, nums[i-1] + nums[i+1] = nums[i] $\times$ 2.
  • Therefore, by using Wiggle Sort, we guarantee that every middle element (1 … n - 1) satisfies the property that nums[i] $\ge$ nums[i + 1], meaning that it is not possible for x[i] - x[i - 1] to equal x[i + 1] - x[i] since [i + 1] - x[i] is a negative number.

Cards

START Basic Front: Array With Elements Not Equal to Average of Neighbors - LeetCode Back: This problem reduces to Wiggle Sort. Tags:

END

Complexity

Runtime

$O(NlogN)$

Space

$O(1)$

Code

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

Notes

---

References

Array With Elements Not Equal to Average of Neighbors - LeetCode