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.