1968. Array With Elements Not Equal to Average of Neighbors - Explanation

1. Greedy

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        nums.sort()
        res = []
        l, r = 0, len(nums) - 1
        while len(res) != len(nums):
            res.append(nums[l])
            l += 1
            if l <= r:
                res.append(nums[r])
                r -= 1
        return res

Time & Space Complexity

Time complexity: $O(n\log n)$
Space complexity: $O(n)$

2. Greedy (Space Optimized)

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

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

3. Greedy (Optimal) - I

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        n = len(nums)

        for i in range(1, n - 1):
            if 2 * nums[i] == (nums[i - 1] + nums[i + 1]):
                nums[i], nums[i + 1] = nums[i + 1], nums[i]

        for i in range(n - 2, 0, -1):
            if 2 * nums[i] == (nums[i - 1] + nums[i + 1]):
                nums[i], nums[i - 1] = nums[i - 1], nums[i]

        return nums

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

4. Greedy Optimal - II

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        increase = nums[0] < nums[1]
        for i in range(1, len(nums) - 1):
            if ((increase and nums[i] < nums[i + 1]) or
                (not increase and nums[i] > nums[i + 1])
            ):
                nums[i], nums[i + 1] = nums[i + 1], nums[i]
            increase = not increase
        return nums

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.