Array With Elements Not Equal to Average of Neighbors

Array With Elements Not Equal to Average of Neighbors - 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [4,1,3,2]

› Output: [1,4,2,3]

💡 Note: Rearranged so that (1+2)/2 = 1.5 ≠ 4, and (4+3)/2 = 3.5 ≠ 2. No element equals the average of its neighbors.

Example 2 — Three Elements

$ Input: nums = [1,2,3]

› Output: [1,3,2]

💡 Note: Original [1,2,3] fails because (1+3)/2 = 2. Rearranged [1,3,2] works because (1+2)/2 = 1.5 ≠ 3.

Example 3 — Larger Array

$ Input: nums = [1,2,3,4,5]

› Output: [1,3,2,5,4]

💡 Note: Creates zigzag pattern where no middle element equals average of neighbors: 1<3>2<5>4

Constraints

3 ≤ nums.length ≤ 10⁵
-10⁵ ≤ nums[i] ≤ 10⁵
All the elements of nums are unique

Visualization

Tap to expand

Understanding the Visualization

Input

Array with elements that may equal neighbor averages

Process

Rearrange into zigzag pattern (peaks and valleys)

Output

No element equals average of its neighbors

Key Takeaway

🎯 Key Insight: A zigzag pattern naturally prevents average conflicts between neighbors

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is creating a wiggle pattern where elements alternate between peaks and valleys. The optimal greedy approach runs in O(n) time by ensuring each position follows the alternating pattern rule. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Zigzag Pattern	O(n log n)	O(1)	Sort array then create alternating peaks and valleys
Brute Force Permutations	O(n! × n)	O(n)	Generate all permutations and check each one
Greedy Wiggle Sort	O(n)	O(1)	Directly arrange elements in alternating pattern without sorting

Sort and Zigzag Pattern — Algorithm Steps

Sort the array in ascending order
Create zigzag pattern: place elements alternating small-large-small
Return the rearranged array

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Array

Order elements from smallest to largest

Create Zigzag

Swap every other pair to make peaks and valleys

Result

No element equals average of neighbors

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int* solution(int* nums, int n) {
    qsort(nums, n, sizeof(int), compare);
    
    // Create zigzag pattern by swapping every other element
    for (int i = 1; i < n; i += 2) {
        if (i + 1 < n) {
            int temp = nums[i];
            nums[i] = nums[i + 1];
            nums[i + 1] = temp;
        }
    }
    
    return nums;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[100];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && (token[0] >= '0' && token[0] <= '9' || token[0] == '-')) {
            nums[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    solution(nums, n);
    
    printf("[");
    for (int i = 0; i < n; i++) {
        printf("%d", nums[i]);
        if (i < n - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), rearrangement takes O(n)

⚡ Linearithmic

Space Complexity

O(1)

Only uses constant extra space for swapping elements

✓ Linear Space

12.3K Views

Medium Frequency

~15 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort and Zigzag Pattern — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler