Array With Elements Not Equal to Average of Neighbors

How it works

A valid arrangement alternates between increasing and decreasing. We can enforce this pattern in a single pass by tracking whether the next step should increase or decrease. Starting from the relationship between the first two elements, we alternate the expected direction. If the actual relationship violates the expected direction, we swap to fix it.

Steps

1. Determine the initial direction based on whether nums[0] < nums[1] (increasing) or not.
2. Iterate from index 1 to n-2.
3. If the direction is increasing and nums[i] < nums[i+1], or if decreasing and nums[i] > nums[i+1], swap nums[i] and nums[i+1].
4. Toggle the direction after each step.
5. Return the modified array.

Complexity

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

Things to watch for

Checking Only One Direction After Swapping

When fixing a violation by swapping, the swap might create a new violation at the previous position. A single forward pass may not catch all cases, which is why some solutions use both forward and backward passes.

Using Division for Average Check

Using division to check if an element equals the average of its neighbors can introduce floating-point precision issues. Instead, multiply both sides by 2 to avoid division entirely.

Forgetting to Handle Array Boundaries

The check only applies to elements with both neighbors (indices 1 through n-2). Applying the average check to the first or last element causes index out of bounds errors.

from typing import List

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

class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        bool increase = nums[0] < nums[1];
        for (int i = 1; i < nums.size() - 1; i++) {
            if ((increase && nums[i] < nums[i + 1]) ||
                (!increase && nums[i] > nums[i + 1])) {
                swap(nums[i], nums[i + 1]);
            }
            increase = !increase;
        }
        return nums;
    }
};