1968. Array With Elements Not Equal to Average Neighbors

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.

More formally, the rearranged array should have the property such that for every i in the range 1 <= i < nums.length - 1, (nums[i-1] + nums[i+1]) / 2 is not equal to nums[i].

Return any rearrangement of nums that meets the requirements.

Example 1:

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.
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.

Example 2:

Input: nums = [6,2,0,9,7]
Output: [9,7,6,2,0]
Explanation:
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.

Constraints:

3 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵

Approach overview

Problem Overview: Given an integer array, rearrange the elements so that for every valid index i, the value nums[i] is not equal to the average of its neighbors (nums[i-1] + nums[i+1]) / 2. You can return any valid permutation of the array.

Approach 1: Sort and Interleave Strategy (O(n log n) time, O(n) space)

This approach relies on sorting followed by a simple rearrangement. First, sort the array in ascending order. Then build a new array by interleaving smaller and larger halves so adjacent numbers differ significantly. A common pattern is to place smaller elements at even indices and larger elements at odd indices. Because neighbors now come from different halves of the sorted list, the middle value rarely equals the average of its neighbors.

The key insight: when the array is sorted, the average of two distant values rarely equals a third element positioned between them. By separating low and high values during placement, you avoid symmetric patterns that create averages. Implementation simply iterates through the sorted array and fills positions alternately. Sorting dominates the runtime, giving O(n log n) time and O(n) extra space for the result array. This method is easy to implement and works reliably for all valid inputs.

Approach 2: Greedy Zig-Zag Strategy (O(n log n) time, O(1) extra space)

This method also begins with sorting but performs in-place rearrangement using a greedy zig-zag pattern. After sorting, iterate through the array and swap adjacent pairs starting from index 1: swap nums[i] and nums[i+1] for every odd index. This produces a pattern like a0 < a2 > a1 < a4 > a3. Because each middle element becomes either strictly larger or strictly smaller than its neighbors, it cannot equal their average.

The insight comes from greedy local adjustments. By ensuring alternating peaks and valleys, you prevent any element from sitting exactly between its neighbors. The algorithm performs a single pass of swaps after sorting, so the complexity remains O(n log n) time due to sorting and O(1) additional space since the rearrangement happens in-place. The approach works well when minimizing memory usage.

Both solutions rely on the structure created by array ordering after sorting. Once elements are spaced apart in value, the arithmetic average condition becomes very unlikely.

Recommended for interviews: The Sort and Interleave strategy is typically the clearest explanation during interviews. It demonstrates understanding of ordering and value distribution. The Greedy Zig-Zag swap method shows stronger in-place optimization skills and is often preferred when discussing space complexity trade-offs.

Approach 1: Sort and Interleave Strategy

Sort the array and then divide it into two halves. Interleave elements from both halves to form the rearrangement. This strategy works because the interleaving breaks the sequence that might result in the middle element being the average of its neighbors.

To be specific, split the sorted array into two: one for the even indexed positions and the other for odd indexed positions. By placing the smaller half in even positions and the larger half in odd positions, we ensure no element is the average of its neighbors.

Python

def rearrange_array(nums):
    nums.sort()
    half = len(nums) // 2
    result = []
    for i in range(half):
        result.append(nums[i])
        if i + half < len(nums):
            result.append(nums[i + half])
    return result

print(rearrange_array([1,2,3,4,5]))  # Output: [1,3,2,5,4]

JavaScript

function rearrangeArray(nums) {
    nums.sort((a, b) => a - b);
    let half = Math.floor(nums.length / 2);
    let result = [];
    for (let i = 0; i < half; i++) {
        result.push(nums[i]);
        if (i + half < nums.length) {
            result.push(nums[i + half]);
        }
    }
    return result;
}

console.log(rearrangeArray([1,2,3,4,5])); // Output: [1,3,2,5,4]

The code first sorts the input array. It then defines a variable half to find the midpoint. By iterating through the first half of the array, the code appends an element from the first half followed by an element from the second half, creating an interleaved sequence. The strategy ensures that no element is equal to the average of its neighbors.

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing the result.

Try this approach in the editor

Approach 2: Greedy Zig-Zag Strategy

Another approach is based on sorting the array and then arranging it in a zig-zag pattern. The goal is to position larger numbers adjacent to smaller numbers strategically. By doing this, the middle number in any triplet is unlikely to be the average of its neighbors since the fluctuation between numbers disrupts that average.

Java

import java.util.Arrays;

public class Solution {
    public static int[] rearrangeArray(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int[] result = new int[n];
        int left = 0, right = n - 1, index = 0;
        while (left <= right) {
            if (right != left) result[index++] = nums[right--];
            result[index++] = nums[left++];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5};
        int[] result = rearrangeArray(nums);
        System.out.println(Arrays.toString(result));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> rearrangeArray(std::vector<int>& nums) {
    std::sort(nums.begin(), nums.end());
    std::vector<int> res;
    int n = nums.size();
    int left = 0, right = n - 1;
    while (left <= right) {
        if (right != left) res.push_back(nums[right--]);
        res.push_back(nums[left++]);
    }
    return res;
}

int main() {
    std::vector<int> nums = {1,2,3,4,5};
    auto result = rearrangeArray(nums);
    for (int n : result) std::cout << n << " ";
    return 0;
}

This Java implementation sorts the input array and uses two pointers to place elements alternately from the end and beginning, neutralizing any potential average formation among consecutive elements.

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for arranging the output array.

Try this approach in the editor

Approach 3: Sorting

Since the elements in the array are distinct, we can first sort the array, then divide the array into two parts. Place the first half of the elements in the even positions of the answer array, and the second half of the elements in the odd positions of the answer array. In this way, for each element, its two adjacent elements will not be equal to its average value.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums.

TypeScript

function rearrangeArray(nums: number[]): number[] {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const m = (n + 1) >> 1;
    const ans: number[] = [];
    for (let i = 0; i < m; i++) {
        ans.push(nums[i]);
        if (i + m < n) {
            ans.push(nums[i + m]);
        }
    }
    return ans;
}

func rearrangeArray(nums []int) (ans []int) {
	sort.Ints(nums)
	n := len(nums)
	m := (n + 1) >> 1
	for i := 0; i < m; i++ {
		ans = append(ans, nums[i])
		if i+m < n {
			ans = append(ans, nums[i+m])
		}
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Sort and Interleave Strategy	Time Complexity: `O(n log n)` due to sorting. Space Complexity: `O(n)` for storing the result.
Greedy Zig-Zag Strategy	Time Complexity: `O(n log n)` due to sorting. Space Complexity: `O(n)` for arranging the output array.
Sorting	–

Complexity analysis

Approach	Time	Space	When to Use
Sort and Interleave Strategy	O(n log n)	O(n)	Best for clarity and easy implementation when building a new array is acceptable
Greedy Zig-Zag Strategy	O(n log n)	O(1)	Preferred when minimizing extra memory and performing in-place rearrangement

Frequently asked questions

Is Array With Elements Not Equal to Average of Neighbors easy or hard?

The problem is rated Medium because the constraint is subtle. A naive rearrangement can accidentally produce an element equal to the average of its neighbors. Recognizing that sorting followed by controlled placement or zig-zag swaps prevents this condition requires a greedy insight.

Array With Elements Not Equal to Average of Neighbors Python/Java solution

Python and Java implementations typically follow the same logic: sort the array and rearrange it using either interleaving or zig-zag swaps. Python solutions often construct a new list for clarity, while Java implementations frequently perform in-place swaps to reduce memory usage. Both approaches run in O(n log n) time.

How to solve Array With Elements Not Equal to Average of Neighbors in O(n)?

Pure O(n) time is possible only if the input array is already sorted or nearly sorted. In that case, perform a single pass and swap adjacent elements at odd indices to create a zig-zag pattern. For arbitrary unsorted arrays, sorting is typically required, which raises the complexity to O(n log n).

What is the best approach for Array With Elements Not Equal to Average of Neighbors?

The most common approach is the sort and interleave strategy. Sort the array and place smaller values at even indices and larger values at odd indices so neighbors come from different value ranges. This prevents any element from becoming the exact average of its neighbors. The algorithm runs in O(n log n) time due to sorting and uses O(n) extra space.

Is Array With Elements Not Equal to Average of Neighbors asked at Google/Amazon/Meta?

Problems involving array rearrangement and greedy ordering frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary in wording, the underlying concept of preventing arithmetic relationships between neighbors is a common greedy interview pattern.

What data structure is used in Array With Elements Not Equal to Average of Neighbors?

The solution primarily uses arrays along with sorting algorithms. After sorting, a greedy rearrangement or swapping technique is applied to control the relationship between neighboring elements. No advanced data structures are required beyond the array itself.

What is the time complexity of Array With Elements Not Equal to Average of Neighbors?

Most optimal solutions run in O(n log n) time because the array is sorted first. After sorting, rearranging elements using interleaving or zig-zag swaps requires only a single linear pass. Space complexity ranges from O(1) for in-place swaps to O(n) when constructing a new reordered array.

Array With Elements Not Equal to Average of Neighbors solution and explanation

The problem

Approach overview

Approach 1: Sort and Interleave Strategy

Approach 2: Greedy Zig-Zag Strategy

Approach 3: Sorting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Array With Elements Not Equal to Average of Neighbors solution and explanation

The problem

Approach overview

Approach 1: Sort and Interleave Strategy

Approach 2: Greedy Zig-Zag Strategy

Approach 3: Sorting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems