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
- 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.
- Then for every middle position, the value is a large one bounded below by the adjacent small values, and the strict inequality holds.
- 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. - 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
nis odd: the smaller half has(n + 1) // 2elements, 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.