1968

1968. Array With Elements Not Equal to Average of Neighbors (Medium)

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.

 

Constraints:

• 3 <= nums.length <= 105
• 0 <= nums[i] <= 105

Similar Questions:

• Wiggle Sort (Medium)
• Wiggle Sort II (Medium)

Solution 1.

Intuition: If a < b and a < c, this sequence b, a, c must be valid. Similarly, if a > b and a > c, b, a, c is also valid.

Algorithm:

• Sort the array A.
• Fill the even positions with the small half numbers.
• Fill the odd positions with the great half numbers.

For example, A = [1, 2, 3, 4, 5]:

• Filling the even positions: ans = [1, ?, 2, ?, 3]
• Filling the odd positions: ans = [1, 4, 2, 5, 3].

The space complexity is O(N) because if we can't alter the original array, we have to copy the original array, sort it, then copy values into the answer array.

// OJ: https://leetcode.com/problems/array-with-elements-not-equal-to-average-of-neighbors/
// Author: github.com/lzl124631x
// 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;
    }
};

Solution 2.

• Sort the array.
• Swap every two pairs of numbers.

Example: A = [1,2,3,4,5]. We swap 1, 2, and 3, 4. A becomes [2,1,4,3,5].

The space complexity is O(1) because we can copy the original array into the answer array, sort the answer array, and swap values in place in the answer array. We don't count the size of the answer array into space complexity because they are needed anyway.

// OJ: https://leetcode.com/problems/array-with-elements-not-equal-to-average-of-neighbors/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    vector<int> rearrangeArray(vector<int>& A) {
        sort(begin(A), end(A));
        for (int i = 0; i + 1 < A.size(); i += 2) {
            swap(A[i], A[i + 1]);
        }
        return A;
    }
};

NOTE

The key is to find ways to turn the input array into a wiggle array. That is, A[0] < A[1] > A[2] < A[3] ....