LeetCode 1968 - Array With Elements Not Equal to Average of Neighbors

The problem asks us to rearrange a distinct integer array so that no element is equal to the average of its neighbors. The input is a zero-indexed array nums of length at least 3, and all elements are guaranteed to be distinct.

leetcodemediumarraygreedysorting

LeetCode Problem 1968

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem asks us to rearrange a distinct integer array so that no element is equal to the average of its neighbors. The input is a zero-indexed array nums of length at least 3, and all elements are guaranteed to be distinct. The output should be any valid rearrangement of nums that satisfies the condition for all elements that have both left and right neighbors, i.e., for indices 1 to len(nums) - 2.

The constraints tell us that the array can be relatively large (up to 10^5 elements) and the element values are non-negative integers up to 10^5. Because of this size, any algorithm that involves trying all permutations would be far too slow.

Key edge cases include arrays that are already sorted in increasing or decreasing order, or arrays where adjacent differences are minimal. The problem guarantees distinct elements, so we do not have to handle duplicates, which simplifies our task.

The fundamental requirement is that for any element nums[i], it must not equal (nums[i-1] + nums[i+1]) / 2. Intuitively, this happens when an element is "between" its neighbors. Therefore, a clever reordering that avoids such situations will satisfy the problem.

Approaches

A brute-force approach would attempt all permutations of the array and check the condition for each. While this is guaranteed to eventually find a solution if one exists, it is computationally infeasible. For n elements, there are n! permutations, which is far beyond reasonable for n = 10^5.

The key insight for an optimal approach is based on sorting and interleaving extremes. If we sort the array and then rearrange elements by alternating the smaller half with the larger half, we ensure that no middle element is the average of its neighbors. Essentially, by spreading out the smaller and larger numbers, the "sandwiching" of a number by smaller and larger neighbors prevents it from being their average.

This technique is a kind of greedy approach based on ordering, which guarantees the required property.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n) Check all permutations of the array to satisfy the condition
Optimal O(n log n) O(n) Sort the array and interleave smaller and larger halves to avoid average conflicts

Algorithm Walkthrough

  1. Start by sorting the array in ascending order. Sorting provides a predictable structure of smallest to largest elements.
  2. Split the sorted array into two halves. For simplicity, consider left as the smaller half and right as the larger half.
  3. Create a new result array and alternate elements from left and right. Start by taking an element from left, then from right, and continue.
  4. If the array has odd length, the larger half will have one extra element. Place it at the end of the interleaving sequence.
  5. Return the interleaved array as the rearranged result.

Why it works: Sorting guarantees that each element is ordered. By interleaving small and large values, every element that has neighbors will have one smaller and one larger neighbor. Mathematically, a number cannot be exactly equal to the average of one smaller and one larger number unless it is a duplicate or symmetric in an exact arithmetic way, which is impossible here due to distinct elements. This ensures the invariant is satisfied for all middle elements.

Python Solution

from typing import List

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        nums.sort()
        n = len(nums)
        left = nums[:n//2]
        right = nums[n//2:]
        
        result = []
        i = 0
        j = 0
        while i < len(left) or j < len(right):
            if j < len(right):
                result.append(right[j])
                j += 1
            if i < len(left):
                result.append(left[i])
                i += 1
        return result

The solution first sorts the array to impose order. The left and right halves are then interleaved into the result. We take elements from the larger half first to ensure that the sequence does not accidentally place a smaller number between two larger numbers, which could form an average. This ensures the algorithm’s correctness.

Go Solution

import "sort"

func rearrangeArray(nums []int) []int {
    sort.Ints(nums)
    n := len(nums)
    left := nums[:n/2]
    right := nums[n/2:]
    
    result := make([]int, 0, n)
    i, j := 0, 0
    for i < len(left) || j < len(right) {
        if j < len(right) {
            result = append(result, right[j])
            j++
        }
        if i < len(left) {
            result = append(result, left[i])
            i++
        }
    }
    return result
}

In Go, we handle slices carefully. make([]int, 0, n) pre-allocates the result array to avoid repeated resizing. Sorting is done in-place using sort.Ints. The interleaving logic mirrors the Python approach.

Worked Examples

Example 1: nums = [1,2,3,4,5]

  1. Sort: [1,2,3,4,5]
  2. Split: left = [1,2], right = [3,4,5]
  3. Interleave: result = [3,1,4,2,5]
  4. Verify:
  • i=1: (3+4)/2 = 3.5 != 1
  • i=2: (1+2)/2 = 1.5 != 4
  • i=3: (4+5)/2 = 4.5 != 2

Example 2: nums = [6,2,0,9,7]

  1. Sort: [0,2,6,7,9]
  2. Split: left = [0,2], right = [6,7,9]
  3. Interleave: result = [6,0,7,2,9]
  4. Verify:
  • i=1: (6+7)/2 = 6.5 != 0
  • i=2: (0+2)/2 = 1 != 7
  • i=3: (7+9)/2 = 8 != 2

Both examples satisfy the condition.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates the complexity; interleaving is O(n)
Space O(n) We store left and right halves, and a result array of size n

Sorting the array is the primary cost, and creating the interleaved array requires linear space. This is optimal given the problem size.

Test Cases

# Provided examples
assert Solution().rearrangeArray([1,2,3,4,5]) != []  # generic check
assert Solution().rearrangeArray([6,2,0,9,7]) != []

# Minimum length array
assert Solution().rearrangeArray([1,2,3]) != []

# Already sorted array
assert Solution().rearrangeArray([10,20,30,40,50]) != []

# Reverse sorted array
assert Solution().rearrangeArray([50,40,30,20,10]) != []

# Large input
assert Solution().rearrangeArray(list(range(1, 10001))) != []
Test Why
[1,2,3,4,5] Simple ascending input
[6,2,0,9,7] Random distinct integers
[1,2,3] Minimum size edge case
[10,20,30,40,50] Already sorted array
[50,40,30,20,10] Reverse sorted array
1..10000 Large input to stress performance

Edge Cases

Minimum length array: Arrays of length 3 are the smallest possible. The interleaving logic still works, because the left half will have one element and the right half two, producing a valid sequence.

Sorted array with consecutive integers: Could accidentally produce an element equal to the average if naive swapping is done. Sorting and alternating halves prevent this by spacing extremes.

Odd-length arrays: The left half will have fewer elements than the right. Placing the extra element from the right at the beginning ensures that every middle element still has one smaller and one larger neighbor, preserving correctness.