09 Feb 2025•TypeScript•Medium

Array With Elements Not Equal to Average of Neighbors

rearrange array so no element equals the average of its neighbors using sorted interleaving pattern.

the key insight is that we need to separate larger and smaller values so no element sits between its neighbors. i sort the array, split it at the midpoint, then interleave from both halves—larger values from the left half, smaller from the right.

by placing elements in this alternating pattern, we ensure that each element is either larger or smaller than both neighbors, never equal to their average.

approach

sort the input array
split at midpoint (mid = floor((n + 1) / 2))
interleave: even indices get from left half, odd from right
this guarantees no element equals neighbor average

complexity

O(n log n) time for sorting, O(n) space for the result array. the interleaving step is linear.

Solution files

TypeScript•array-with-elements-not-equal-to-average-of-neighbors/solution.ts

function rearrangeArray(nums: number[]): number[] {
  if (nums.length <= class="syntax-number">2) {
    return [...nums];
  }

  const sorted = [...nums].sort((a, b) => a - b);
  const mid = Math.floor((nums.length + class="syntax-number">1) / class="syntax-number">2);
  let left = mid - class="syntax-number">1;
  let right = nums.length - class="syntax-number">1;
  const result: number[] = [];

  for (let i = class="syntax-number">0; i < nums.length; ++i) {
    if (i % class="syntax-number">2 === class="syntax-number">0) {
      result.push(sorted[left]);
      left -= class="syntax-number">1;
    } else {
      result.push(sorted[right]);
      right -= class="syntax-number">1;
    }
  }

  return result;
}

export { rearrangeArray };