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.
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.
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
Contents
- Solution 1 - Sort and rearrange elements
The main intution behind this solution is, say if we were given the input array as [1, 2, 3, 4, 5, 6], here element 2 is
in between (1, 3) and their average is 2, so how can we re arrange these such that current element value will not be the average of its neighbors ?
one simple solution we can do is, if we can rearrange elements such that current element's neighbors are either smaller than current element or greater than current element,
then we can solve this problem.
Consider, above example nums = [1, 2, 3, 4, 5, 6], first we will fill smaller elements first but leave one space after each element, so the resultant array looks like
[1, _, 2, _, 3, _], then we will remaining numbers in the spots either from left or right, so the final resultant array looks like [1, 6, 2, 5, 3, 4],
notice that neighbors of each element are either smaller or greater than current element, and element's value is not equal to neighbors average.
Before we apply the solution, we are going to sort the array first, so that they are either in increasing or decreasing order and we will rearrange number as shown above.
import java.util.Arrays;
public class ArrayWithElementsNotEqualToAverageOfNeighbors {
static int[] rearrangeArray(int[] nums) {
Arrays.sort(nums);
int l=0;
int r = nums.length-1;
int[] res = new int[nums.length];
int index = 0;
while(l<=r) {
res[index++] = nums[l++];
if(l<=r){ // to handle odd length arrays
res[index++] = nums[r--];
}
}
return res;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(rearrangeArray(new int[]{1, 2, 3, 4, 5})));
System.out.println(Arrays.toString(rearrangeArray(new int[]{1, 2, 3, 4, 5, 6})));
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n log n) time where n is the length of nums array, since we are sorting the input array.
Space complexity: O(n) for the result array.
Above implementations source code can be found at
GitHub link for Java code