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 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 <= 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;
    }
}

############

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;
    }
}

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

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


  • func rearrangeArray(nums []int) []int {
	sort.Ints(nums)
	n := len(nums)
	m := (n + 1) >> 1
	var ans []int
	for i := 0; i < m; i++ {
		ans = append(ans, nums[i])
		if i+m < n {
			ans = append(ans, nums[i+m])
		}
	}
	return ans
}

All Problems

All Solutions