ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 17:I[4821,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 18:I[2647,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1a:I[7912,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 19:Tdea,

Problem

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.

Examples

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.

Solution

Method 1 - Using Wiggle Sort

We can use Wiggle Sort 1 and Wiggle Sort 2 - No Adjacent Duplicates algorithms smartly. If we make sure that nums[i-1] < nums[i] > nums[i+1], i.e. - a < b > c < d > e < f, we are good to go.

public int[] rearrangeArray(int[] nums) {
	Arrays.sort(nums);
	for (int i = 1; i < nums.length; i += 2) {
		int tmp = nums[i];
		nums[i] = nums[i - 1];
		nums[i - 1] = tmp;
	}
	return nums;
}

Time complexity - O(nlogn)

[{"language":"Method 2 - Using MinHeap","code":"public int[] rearrangeArray(int[] nums) {\n\tQueue<Integer> minHeap = new PriorityQueue<>();\n\tfor (int num:nums) {\n\t\tminHeap.add(num);\n\t}\n\tfor (int i = 1; i < nums.length; i=i+2) {\n\t   nums[i]  = minHeap.poll();\n\t}\n\tfor (int i = 0; i < nums.length; i=i+2) {\n\t\tnums[i]  = minHeap.poll();\n\t}\n\treturn nums;\n}","lang":"java"},{"language":"Method 3 - Sorting and Keeping Numbers Greater Than Median at Odd Indexs","code":"public static int[] rearrangeArrayWithSorting1(int[] nums) {\n\tint len = nums.length;\n\tArrays.sort(nums);\n\tint medianIndex = len - len / 2;\n\tfor (int i = 1; i < nums.length && medianIndex < nums.length; i += 2, medianIndex++) {\n\t\tswap(nums, i, medianIndex);\n\t}\n\treturn nums;\n}","lang":"java"},{"language":"Method 4 - Without Sorting","code":"public static int[] rearrangeArray(int[] nums) {\n   int n = nums.length;\n   for (int i = 1; i < n - 1; i++) {\n\t   if (2 * nums[i] == (nums[i - 1] + nums[i + 1])) {\n\t\t   swap(nums, i, i + 1);\n\t   }\n   }\n   for (int i = n - 2; i > 0; i--) {\

Related Tags