Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1968.html
1968. Array With Elements Not Equal to Average of Neighbors
Level
Medium
Description
You are given a 0indexed 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[i1] + 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.
Constraints:
3 <= nums.length <= 10^5
0 <= nums[i] <= 10^5
Solution
One simple way is to rearrange elements so that element element that is not the first element or the last element is either greater than both neighbors or less than both neighbors. Sort array nums
. Let left = 0
and right = nums.length  1
. Create an array rearrange
of the same length as nums
. For any i
, if i
is even, then let rearrange[i] = nums[left]
and increase left
by 1. If i
is odd, then let rearrange[i] = nums[right]
and decrease right
by 1. Finally, return rearrange
.

class Solution { public int[] rearrangeArray(int[] nums) { Arrays.sort(nums); int length = nums.length; int[] rearrange = new int[length]; int left = 0, right = length  1; for (int i = 0; i < length; i++) { if (i % 2 == 0) { rearrange[i] = nums[left]; left++; } else { rearrange[i] = nums[right]; right; } } return rearrange; } }

// OJ: https://leetcode.com/problems/arraywithelementsnotequaltoaverageofneighbors/ // Time: O(NlogN) // Space: O(N) class Solution { public: vector<int> rearrangeArray(vector<int>& A) { sort(begin(A), end(A)); int N = A.size(), i = 0; vector<int> ans(N); for (int j = 0; j < N; j += 2) ans[j] = A[i++]; for (int j = 1; j < N; j += 2) ans[j] = A[i++]; 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 ans ############ # 1968. Array With Elements Not Equal to Average of Neighbors # https://leetcode.com/problems/arraywithelementsnotequaltoaverageofneighbors/ class Solution: def rearrangeArray(self, nums: List[int]) > List[int]: nums.sort() for i in range(1, len(nums), 2): nums[i], nums[i  1] = nums[i  1], nums[i] return nums