Array With Elements Not Equal to Average of Neighbors — LeetCode 1968 Python Solution

The problem

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.

Example

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.

Python solution

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

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 1968. Array With Elements Not Equal to Average of Neighbors is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems