Problem Description

You are given a 0-indexed array nums containing distinct integers. Your task is to rearrange the elements in the array so that no element equals the average of its two neighbors.

Specifically, after rearranging the array, for every index i where 1 <= i < nums.length - 1, the element at position i should not equal (nums[i-1] + nums[i+1]) / 2.

For example, if you have three consecutive elements [a, b, c], then b should not equal (a + c) / 2.

The solution works by first sorting the array, then splitting it into two halves. Elements from the first half are placed at even indices (0, 2, 4, ...) and elements from the second half are placed at odd indices (1, 3, 5, ...) of the result array. This interleaving pattern ensures that each element is surrounded by elements that are either both smaller or both larger than itself, preventing any element from being the average of its neighbors.

The key insight is that when you alternate between smaller and larger values, the middle element can never be the average of its neighbors since the neighbors are from different "groups" of the sorted array.

Intuition

The key observation is that for an element to equal the average of its neighbors, it must be exactly in the middle of those two values. For example, if we have three numbers [2, 5, 8], then 5 equals (2 + 8) / 2. This happens when the three numbers form an arithmetic progression.

Since all elements in the array are distinct, we can leverage sorting to control the relative positions of elements. After sorting, we get elements in increasing order: [a₁, a₂, a₃, ..., aₙ].

Now, if we simply use the sorted array as-is, many elements would be the average of their neighbors (like a₂ = (a₁ + a₃) / 2 if they form an arithmetic sequence). We need to break this pattern.

The clever insight is to split the sorted array into two groups: smaller elements and larger elements. If we interleave these two groups, we create a "zigzag" pattern where each element is surrounded by elements from a different group.

For instance, if the sorted array is [1, 2, 3, 4, 5, 6], we split it into [1, 2, 3] (smaller half) and [4, 5, 6] (larger half). By interleaving them as [1, 4, 2, 5, 3, 6], each element from the smaller half is surrounded by elements from the larger half and vice versa.

This works because:

• An element from the smaller half (like 2) is surrounded by elements from the larger half (like 4 and 5). Since both neighbors are larger than 2, their average (4 + 5) / 2 = 4.5 must be greater than 2.
• Similarly, an element from the larger half is surrounded by smaller elements, so the average of its neighbors will be less than itself.

This guarantees that no element can equal the average of its neighbors.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows a straightforward interleaving strategy after sorting:

1. Sort the array: First, we sort the input array nums in ascending order. This gives us elements arranged from smallest to largest.

2. Calculate the midpoint: We find the midpoint m = (n + 1) // 2, where n is the length of the array. This divides the sorted array into two parts:

   • First half: indices [0, m-1] containing smaller elements
   • Second half: indices [m, n-1] containing larger elements

3. Interleave the two halves: We iterate through the first half and alternately place elements from both halves into the result array:

   • For each index i from 0 to m-1:
     • First, append nums[i] (element from the first half)
     • Then, if i + m < n (to handle odd-length arrays), append nums[i + m] (corresponding element from the second half)

The pattern created looks like: [nums[0], nums[m], nums[1], nums[m+1], nums[2], nums[m+2], ...]

For example, with nums = [1, 2, 3, 4, 5, 6]:

• After sorting: [1, 2, 3, 4, 5, 6]
• m = (6 + 1) // 2 = 3
• First half: [1, 2, 3], Second half: [4, 5, 6]
• Result: [1, 4, 2, 5, 3, 6]

The condition if i + m < n handles odd-length arrays where the first half has one more element than the second half. In such cases, the last element from the first half won't have a corresponding pair from the second half.

This approach has a time complexity of O(n log n) due to sorting, and space complexity of O(n) for the answer array.

Example Walkthrough

Let's walk through the solution with a concrete example: nums = [6, 2, 0, 9, 7]

Step 1: Sort the array

• Original: [6, 2, 0, 9, 7]
• After sorting: [0, 2, 6, 7, 9]

Step 2: Calculate the midpoint

• n = 5 (length of array)
• m = (5 + 1) // 2 = 3
• This splits our sorted array into:
  • First half (smaller elements): [0, 2, 6] (indices 0-2)
  • Second half (larger elements): [7, 9] (indices 3-4)

Step 3: Interleave the two halves

We iterate through the first half and alternately place elements:

• i = 0:

  • Append nums[0] = 0 to result → [0]
  • Check if 0 + 3 < 5 (True), append nums[3] = 7 → [0, 7]

• i = 1:

  • Append nums[1] = 2 to result → [0, 7, 2]
  • Check if 1 + 3 < 5 (True), append nums[4] = 9 → [0, 7, 2, 9]

• i = 2:

  • Append nums[2] = 6 to result → [0, 7, 2, 9, 6]
  • Check if 2 + 3 < 5 (False), skip second element

Final Result: [0, 7, 2, 9, 6]

Verification: Let's verify that no element equals the average of its neighbors:

• Index 1: 7 ≠ (0 + 2) / 2 = 1 ✓
• Index 2: 2 ≠ (7 + 9) / 2 = 8 ✓
• Index 3: 9 ≠ (2 + 6) / 2 = 4 ✓

The solution works because each element from the smaller half (0, 2, 6) is surrounded by elements from the larger half (7, 9), creating a zigzag pattern where no element can be the average of its neighbors.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The dominant operation in this code is nums.sort(), which uses Python's Timsort algorithm with a time complexity of O(n × log n), where n is the length of the array. The subsequent loop iterates through m = (n + 1) // 2 elements, performing constant-time operations (appending to list and accessing array elements), contributing O(n) time. Since O(n × log n) + O(n) = O(n × log n), the overall time complexity is O(n × log n).

Space Complexity: O(n)

The space complexity consists of:

• The ans list which stores all n elements from the input array, requiring O(n) space
• The sorting operation in Python creates a copy of the array internally, using O(n) additional space
• Variables n, m, and i use O(1) space

Therefore, the total space complexity is O(n), where n is the length of the array nums.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Midpoint Calculation for Even vs Odd Length Arrays

A common mistake is using mid = n // 2 instead of mid = (n + 1) // 2. This can lead to incorrect splitting of the array, especially for odd-length arrays.

Why it's a problem:

• For odd-length arrays like [1, 2, 3, 4, 5], using n // 2 gives mid = 2, which would split as [1, 2] and [3, 4, 5] - unequal halves that break the interleaving pattern.
• The correct formula (n + 1) // 2 gives mid = 3, splitting as [1, 2, 3] and [4, 5], ensuring the first half has at most one more element than the second half.

Solution: Always use mid = (n + 1) // 2 to ensure proper splitting where the first half gets the extra element for odd-length arrays.

2. Forgetting to Check Bounds When Accessing Second Half

Another pitfall is omitting the bounds check if i + mid < n: when accessing elements from the second half.

Why it's a problem:

• For odd-length arrays, the last iteration would try to access nums[i + mid] where i + mid >= n, causing an IndexError.
• Example: Array [1, 2, 3, 4, 5] with mid = 3. When i = 2, trying to access nums[2 + 3] = nums[5] would be out of bounds.

Solution: Always include the bounds check before accessing the second half:

if i + mid < n:
    result.append(nums[i + mid])

3. Assuming the Input Array is Already Sorted

The problem states the array contains "distinct integers" but doesn't guarantee they're sorted. Forgetting to sort can produce incorrect results.

Why it's a problem:

• The interleaving strategy only works when we have a clear separation between smaller and larger elements.
• Without sorting, randomly distributed values won't maintain the property that neighbors are from different "groups."

Solution: Always sort the array first with nums.sort() before applying the interleaving logic.

4. Modifying the Original Array Without Considering Side Effects

Using nums.sort() modifies the original array in-place, which might not be desired if the original order needs to be preserved elsewhere.

Solution: If preserving the original array is important, create a copy first:

sorted_nums = sorted(nums)  # Creates a new sorted list
# Then use sorted_nums instead of nums