Array With Elements Not Equal to Average of Neighbors
MedPrompt
You are given a 0-indexed array nums of distinct integers. You want to rearrange the elements in the array such that every element in the rearranged array is not equal to the average of its neighbors.
More formally, the rearranged array should have the property such that for every i in the range 1 <= i < nums.length - 1, (nums[i-1] + nums[i+1]) / 2 is not equal to nums[i].
Return any rearrangement of nums that meets the requirements.
Example 1:
Input: nums = [1,2,3,4,5]
Output: [1,2,4,5,3]
Explanation:
When i=1, nums[i] = 2, and the average of its neighbors is (1+4) / 2 = 2.5.
When i=2, nums[i] = 4, and the average of its neighbors is (2+5) / 2 = 3.5.
When i=3, nums[i] = 5, and the average of its neighbors is (4+3) / 2 = 3.5.Example 2:
Input: nums = [6,2,0,9,7]
Output: [9,7,6,2,0]
Explanation:
When i=1, nums[i] = 7, and the average of its neighbors is (9+6) / 2 = 7.5.
When i=2, nums[i] = 6, and the average of its neighbors is (7+2) / 2 = 4.5.
When i=3, nums[i] = 2, and the average of its neighbors is (6+0) / 2 = 3.
Note that the original array [6,2,0,9,7] also satisfies the conditions.
Constraints:
3 <= nums.length <= 1050 <= nums[i] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
The most optimal approach rearranges the array in-place to form a "wave" pattern in a single pass. This avoids the O(n log n) cost of sorting and requires no extra space.
Algorithm
- Iterate through the
numsarray fromi = 1ton-1. - For each
i, check if it and its predecessornums[i-1]follow the desired wave pattern. - If
iis odd, we wantnums[i-1] <= nums[i]. Ifnums[i-1] > nums[i], swap them. - If
iis even, we wantnums[i-1] >= nums[i]. Ifnums[i-1] < nums[i], swap them. - After the loop, the array will be in a valid wave form.
- Return the modified
numsarray.
Walkthrough
The key insight is that we only need to ensure a local property, and we can do so greedily. We can enforce a wave-like structure (a <= b >= c <= d >= ...) directly on the input array without a full sort. Since all elements are distinct, the relations will be strict < and >.
We iterate through the array from the second element (i = 1). At each position i, we enforce the correct relationship with the previous element i-1.
- If
iis odd, we want a 'peak', sonums[i]should be greater than or equal tonums[i-1]. If not, we swap them. - If
iis even, we want a 'valley', sonums[i]should be less than or equal tonums[i-1]. If not, we swap them.
This single pass is sufficient to transform the array into a valid wave. Each swap corrects the local order without disrupting the previously established wave property. Since the final array is a wave, every element is a local extremum, which satisfies the problem's condition.
class Solution { public int[] rearrangeArray(int[] nums) { for (int i = 1; i < nums.length; i++) { // If i is odd, we want nums[i] > nums[i-1] if (i % 2 == 1) { if (nums[i] < nums[i-1]) { swap(nums, i, i - 1); } } // If i is even, we want nums[i] < nums[i-1] else { if (nums[i] > nums[i-1]) { swap(nums, i, i - 1); } } } return nums; } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }}Complexity
Time
O(n), as it involves a single pass through the array with constant time operations at each step.
Space
O(1), as the rearrangement is done in-place with no auxiliary data structures.
Trade-offs
Pros
Optimal O(n) time complexity.
Optimal O(1) space complexity as it operates in-place.
Very simple and concise to implement.
Cons
The proof of correctness is slightly more subtle than the sorting approach, as one must verify that a local swap does not invalidate previously established parts of the wave.
This approach explores every possible arrangement of the numbers in the input array. It generates all permutations and, for each one, checks if it satisfies the given condition that no element is the average of its neighbors. Since the problem guarantees a solution exists, this method will eventually find one.
Algorithm
- Define a recursive function, say
findPermutation(index, currentNums), to generate all permutations. - The base case for the recursion is when
indexreaches the array length. At this point,currentNumsis a full permutation. - For each complete permutation, check if it is a valid arrangement using a helper function.
- The helper function
isValid(arr)iterates fromi = 1ton-2and returnsfalseif it finds anyiwhere2 * arr[i] == arr[i-1] + arr[i+1]. - If a valid permutation is found, return it.
- In the recursive step, iterate from
indexto the end of the array. For each element, swap it with the element atindex, recurse withfindPermutation(index + 1, currentNums), and then backtrack by swapping back.
Walkthrough
The core idea is to exhaustively try every single possible ordering of the nums array. We can write a recursive function that generates all permutations. For each generated permutation, we iterate from the second element to the second-to-last element (i from 1 to n-2) and check if the condition nums[i] * 2 == nums[i-1] + nums[i+1] is ever true. If we find a permutation where the condition is never true for any i, we have found a valid solution and can return it. While correct, this method is computationally prohibitive.
class Solution { public int[] rearrangeArray(int[] nums) { List<Integer> currentPermutation = new ArrayList<>(); for (int num : nums) { currentPermutation.add(num); } List<List<Integer>> allPermutations = new ArrayList<>(); generatePermutations(0, currentPermutation, allPermutations); for (List<Integer> p : allPermutations) { if (isValid(p)) { int[] result = new int[nums.length]; for (int i = 0; i < nums.length; i++) { result[i] = p.get(i); } return result; } } return new int[]{}; // Should not be reached } private void generatePermutations(int index, List<Integer> nums, List<List<Integer>> allPermutations) { if (index == nums.size()) { allPermutations.add(new ArrayList<>(nums)); return; } for (int i = index; i < nums.size(); i++) { Collections.swap(nums, index, i); generatePermutations(index + 1, nums, allPermutations); Collections.swap(nums, index, i); // backtrack } } private boolean isValid(List<Integer> nums) { for (int i = 1; i < nums.size() - 1; i++) { if (2 * nums.get(i) == nums.get(i - 1) + nums.get(i + 1)) { return false; } } return true; }}Complexity
Time
O(n! * n). There are `n!` permutations to generate, and checking each one for validity takes O(n) time.
Space
O(n! * n) in the worst case to store all permutations, or O(n) for the recursion stack if we check permutations as they are generated.
Trade-offs
Pros
Guaranteed to find a solution.
Conceptually simple to understand.
Cons
Extremely inefficient due to its factorial time complexity.
Only feasible for very small input sizes (e.g., n < 12).
Will result in a 'Time Limit Exceeded' error for the given constraints.
A much more efficient approach is to first sort the array and then construct a new array by arranging the elements in a specific "zigzag" or "wave" pattern. This pattern ensures that no element is the average of its neighbors.
Algorithm
- Sort the input array
numsin non-decreasing order. - Create a new result array
resof the same sizen. - Iterate through the sorted
numsarray with a single pointerk=0. - First, fill all the even indices (
0, 2, 4, ...) ofreswith elements fromnumsstarting fromnums[0]. - Then, fill all the odd indices (
1, 3, 5, ...) ofreswith the remaining elements fromnums. - Return the
resarray.
Walkthrough
The condition nums[i] == (nums[i-1] + nums[i+1]) / 2 can only be true if nums[i] lies strictly between nums[i-1] and nums[i+1]. We can prevent this by constructing an array where every element is a local extremum (either a peak or a valley). This can be achieved by sorting the array and then interleaving the smaller and larger halves.
- Sort the input array
nums. - Create a new
resultarray. - Place the smaller half of the sorted numbers at the even indices of the
resultarray and the larger half at the odd indices.
This creates a pattern like small, large, small, large, .... In such a pattern, any element nums[i] is either smaller than both its neighbors (a valley) or larger than both its neighbors (a peak). Therefore, it can never be their average.
import java.util.Arrays; class Solution { public int[] rearrangeArray(int[] nums) { Arrays.sort(nums); int n = nums.length; int[] res = new int[n]; int left = 0; int right = n - 1; for (int i = 0; i < n; i++) { if (i % 2 == 0) { res[i] = nums[left++]; } else { res[i] = nums[right--]; } } return res; }}Complexity
Time
O(n log n), dominated by the sorting step. The construction of the result array takes O(n) time.
Space
O(n) to store the result array. The space complexity of sorting can also be O(log n) or O(n) depending on the implementation used.
Trade-offs
Pros
Significantly faster than brute force, with a polynomial time complexity.
Guaranteed to produce a correct result.
The logic is relatively straightforward to prove.
Cons
Not the most optimal time complexity due to the sorting step.
Requires extra space for the result array, making it not an in-place solution.
Solutions
Solution
class Solution {public int[] rearrangeArray(int[] nums) { Arrays.sort(nums); int n = nums.length; int m = (n + 1) >> 1; int[] ans = new int[n]; for (int i = 0, j = 0; i < n; i += 2, j++) { ans[i] = nums[j]; if (j + m < n) { ans[i + 1] = nums[j + m]; } } return ans; }}class Solution {public: vector<int> rearrangeArray(vector<int> &nums) { sort(nums.begin(), nums.end()); vector<int> ans; int n = nums.size(); int m = (n + 1) >> 1; for (int i = 0; i < m; ++i) { ans.push_back(nums[i]); if (i + m < n) ans.push_back(nums[i + m]); } return ans; }};class Solution: def rearrangeArray(self, nums: List[int]) -> List[int]: nums . sort() n = len(nums) m = (n + 1) >> 1 ans = [] for i in range(m): ans . append(nums[i]) if i + m < n: ans . append(nums[i + m]) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.