Array With Elements Not Equal to Average of Neighbors

MEDIUM

Description

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 <= 10⁵
0 <= nums[i] <= 10⁵

Approaches

Checkout 3 different approaches to solve Array With Elements Not Equal to Average of Neighbors. Click on different approaches to view the approach and algorithm in detail.

Greedy In-place Wave Sort

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.

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 Analysis

Time Complexity: O(n), as it involves a single pass through the array with constant time operations at each step.Space Complexity: O(1), as the rearrangement is done in-place with no auxiliary data structures.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Array With Elements Not Equal to Average of Neighbors. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Array With Elements Not Equal to Average of Neighbors

Algorithms:

Sorting

Patterns:

Greedy

Data Structures:

Array