1968. Array With Elements Not Equal to Average of Neighbors LeetCode Solution

In this guide, you will get 1968. Array With Elements Not Equal to Average of Neighbors LeetCode Solution with the best time and space complexity. The solution to Array With Elements Not Equal to Average of Neighbors problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Array With Elements Not Equal to Average of Neighbors solution in C++
4. Array With Elements Not Equal to Average of Neighbors solution in Java
5. Array With Elements Not Equal to Average of Neighbors solution in Python
6. Additional Resources

Problem Statement of Array With Elements Not Equal to Average of Neighbors

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

Complexity Analysis

• Time Complexity: O(\texttt{sort})
• Space Complexity: O(\texttt{sort})

1968. Array With Elements Not Equal to Average of Neighbors LeetCode Solution in C++

class Solution {
 public:
  vector<int> rearrangeArray(vector<int>& nums) {
    ranges::sort(nums);
    for (int i = 1; i < nums.size(); i += 2)
      swap(nums[i], nums[i - 1]);
    return nums;
  }
};
/* code provided by PROGIEZ */

1968. Array With Elements Not Equal to Average of Neighbors LeetCode Solution in Java

class Solution {
  public int[] rearrangeArray(int[] nums) {
    Arrays.sort(nums);
    for (int i = 1; i < nums.length; i += 2) {
      final int temp = nums[i];
      nums[i] = nums[i - 1];
      nums[i - 1] = temp;
    }
    return nums;
  }
}
// code provided by PROGIEZ

1968. Array With Elements Not Equal to Average of Neighbors LeetCode Solution in Python

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
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.