⚡Flashcard Drill➔
NeetCode #205LC-1968MediumTwo Pointers
← Back to All Problems

#205 · #1968 · Array With Elements Not Equal to Average of Neighbors(构造元素不等于两相邻元素平均值的数组)

📌 Problem Statement & Constraints

Given an array nums, rearrange it so that no element equals the average of its neighbours. Return any valid arrangement. Constraints: 3 <= nums.length <= 10^5, 0 <= nums[i] <= 10^5.

💡 Core Algorithmic Approaches

  1. Sort the array and interleave the smaller half with the larger half: place the small values at the even indices and the large values at the odd indices.
  2. Then for every middle position, the value is a large one bounded below by the adjacent small values, and the strict inequality holds.
  3. Specifically, with res[2k] <= res[2k+1] >= res[2k+2], the equality case (an element being the exact average of its neighbours) cannot occur because the sorted halves are separated.
  4. This is a constructive proof, which is why the problem accepts any valid arrangement.

💻 Benchmark Python3 Implementation

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        nums.sort()
        n = len(nums)
        res = [0] * n
        mid = (n + 1) // 2             # size of the smaller half
        j = 0
        for i in range(0, n, 2):       # small values at even indices
            res[i] = nums[j]
            j += 1
        for i in range(1, n, 2):       # large values at odd indices
            res[i] = nums[j]
            j += 1
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): the sort dominates.
💾 Space Complexity
O(n) for the result.

⚠️ Interview Pitfalls & Follow-ups

  • Splitting the array evenly when n is odd: the smaller half has (n + 1) // 2 elements, and the interleaving depends on this split.
  • Placing large values at even indices: then the peak condition would be violated; small values must go at the even positions.
  • Trying to check all triples after a random shuffle: no guarantee of success, and the constructive approach is deterministic.
  • Forgetting that the arrangement only needs to be valid, not optimal: any valid permutation is accepted.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Two Pointers Problems