Array with elements not equal to average of neighbors

Array Greedy Sorting

50.6% acceptance

Feb 25, 2026

660

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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn rearrange_array(nums: Vec<i32>) -> Vec<i32> {
    let mut nums = nums;
    nums.sort();
    let n = nums.len();
    let mut result = vec![0; n];
    // Interleave: place smaller half at even indices, larger half at odd indices
    let mut idx = 0;
    for i in (0..n).step_by(2) {
      result[i] = nums[idx];
      idx += 1;
    }
    for i in (1..n).step_by(2) {
      result[i] = nums[idx];
      idx += 1;
    }
    result
  }
}