Scale Engineer

Array With Elements Not Equal to Average of Neighbors

Med
#1794Time: O(n), as it involves a single pass through the array with constant time operations at each step.Space: O(1), as the rearrangement is done in-place with no auxiliary data structures.
Patterns
Greedy
Algorithms
Sorting
Data structures
Array

Prompt

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.
Note that the original array [6,2,0,9,7] also satisfies the conditions.

 

Constraints:

  • 3 <= nums.length <= 105
  • 0 <= nums[i] <= 105

Approaches

3 approaches with complexity analysis and trade-offs.

The most optimal approach rearranges the array in-place to form a "wave" pattern in a single pass. This avoids the O(n log n) cost of sorting and requires no extra space.

Algorithm

  • Iterate through the nums array from i = 1 to n-1.
  • For each i, check if it and its predecessor nums[i-1] follow the desired wave pattern.
  • If i is odd, we want nums[i-1] <= nums[i]. If nums[i-1] > nums[i], swap them.
  • If i is even, we want nums[i-1] >= nums[i]. If nums[i-1] < nums[i], swap them.
  • After the loop, the array will be in a valid wave form.
  • Return the modified nums array.

Walkthrough

The key insight is that we only need to ensure a local property, and we can do so greedily. We can enforce a wave-like structure (a <= b >= c <= d >= ...) directly on the input array without a full sort. Since all elements are distinct, the relations will be strict < and >.

We iterate through the array from the second element (i = 1). At each position i, we enforce the correct relationship with the previous element i-1.

  • If i is odd, we want a 'peak', so nums[i] should be greater than or equal to nums[i-1]. If not, we swap them.
  • If i is even, we want a 'valley', so nums[i] should be less than or equal to nums[i-1]. If not, we swap them.

This single pass is sufficient to transform the array into a valid wave. Each swap corrects the local order without disrupting the previously established wave property. Since the final array is a wave, every element is a local extremum, which satisfies the problem's condition.

class Solution {    public int[] rearrangeArray(int[] nums) {        for (int i = 1; i < nums.length; i++) {            // If i is odd, we want nums[i] > nums[i-1]            if (i % 2 == 1) {                if (nums[i] < nums[i-1]) {                    swap(nums, i, i - 1);                }            }             // If i is even, we want nums[i] < nums[i-1]            else {                if (nums[i] > nums[i-1]) {                    swap(nums, i, i - 1);                }            }        }        return nums;    }     private void swap(int[] nums, int i, int j) {        int temp = nums[i];        nums[i] = nums[j];        nums[j] = temp;    }}

Complexity

Time

O(n), as it involves a single pass through the array with constant time operations at each step.

Space

O(1), as the rearrangement is done in-place with no auxiliary data structures.

Trade-offs

Pros

  • Optimal O(n) time complexity.

  • Optimal O(1) space complexity as it operates in-place.

  • Very simple and concise to implement.

Cons

  • The proof of correctness is slightly more subtle than the sorting approach, as one must verify that a local swap does not invalidate previously established parts of the wave.

Solutions

class Solution {public  int[] rearrangeArray(int[] nums) {    Arrays.sort(nums);    int n = nums.length;    int m = (n + 1) >> 1;    int[] ans = new int[n];    for (int i = 0, j = 0; i < n; i += 2, j++) {      ans[i] = nums[j];      if (j + m < n) {        ans[i + 1] = nums[j + m];      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem