1968. Array With Elements Not Equal to Average of Neighbors
Problem Description
You are provided with an array nums
which consists of unique integers. The goal is to rearrange the elements in the array in such a way that no element is equal to the average of its immediate neighbors. To clarify, for every index i
of the rearranged array (1 <= i < nums.length - 1
), the value at nums[i]
should not be equal to (nums[i-1] + nums[i+1]) / 2
. The task is to return any version of the nums
array that satisfies this condition.
Intuition
The key observation to arrive at the solution is that if we arrange the numbers in a sorted manner and then alternate between the smaller and larger halves of the sorted array, we can ensure that no element will be the average of its neighbors. This is because the numbers are distinct and sorted, so a number from the smaller half will always be less than the average of its neighbors, and a number from the larger half will always be greater than the average of its neighbors.
Therefore, first, we sort nums
. Then, we divide the sorted array into two halves - the first half containing the smaller elements and the second half containing the larger elements. We then interleave these two halves such that we first take an element from the first half, followed by an element from the second half, and so on until we run out of elements.
Here's how the thought process breaks down:
- Sort the array to easily identify the smaller and larger halves.
- Identify the middle index to divide the sorted array into two halves.
- Create an empty array
ans
to store the final rearranged sequence. - Iterate through each of the elements in the first half and alternate by adding an element from the second half.
- Return the rearranged array which should now meet the requirements of the problem.
Solution Approach
The solution is pretty straightforward once we understand the intuition behind the problem. The approach makes use of the sorting algorithm, which is a very common and powerful technique in many different problems to create order from disorder.
Here's a step-by-step explanation of the implementation with reference to the provided solution code:
-
We start by sorting the array
nums
. Sorting is done in-place and can use the TimSort algorithm (Python's default sorting algorithm), which has a time complexity of O(n log n), where n is the number of elements in the array.1nums.sort()
-
Calculate the middle index
m
of the array. It represents the starting index of the second half of the sorted array. If the array is of odd length, the middle index will include one more element in the first half.1m = (n + 1) >> 1
The
>>
operator is a right bitwise shift, which is equivalent to dividing by two, but since we are dealing with arrays that are zero-indexed,(n + 1)
ensures that the first half includes the middle element whenn
is odd. For evenn
, this does not change the result. -
An empty list
ans
is initialized to store the final rearranged sequence ofnums
.1ans = []
-
Use a for-loop to iterate over the indices of the first half of
nums
, which runs from0
tom - 1
inclusive. For eachi
, addnums[i]
toans
. Then, check if the corresponding index in the second halfi + m
is within bounds (i + m < n
), and if so, addnums[i + m]
toans
. This ensures that elements are alternated from both halves.1for i in range(m): 2 ans.append(nums[i]) 3 if i + m < n: 4 ans.append(nums[i + m])
-
The completed
ans
list is now a rearranged version ofnums
that satisfies the problem conditions and is returned as the result.1return ans
By implementing this solution, we ensure that elements from the lower half and the upper half of the sorted array alternate in the final arrangement, which prevents any element from being the average of its neighbors due to the distinct and sorted nature of nums
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach described above using an array nums
. Suppose our input array is:
1nums = [1, 3, 2, 5, 4, 6]
Following the steps in the approach:
-
We start by sorting the array
nums
, which gives us:1nums.sort() => [1, 2, 3, 4, 5, 6]
-
Calculate the middle index
m
. There are 6 elements (n = 6
), so the middle index will be:1m = (6 + 1) >> 1 => 3
This means that the first half is
[1, 2, 3]
and the second half is[4, 5, 6]
. -
An empty list
ans
is initialized to store the final rearranged sequence ofnums
.1ans = []
-
Use a for-loop to iterate over the indices of the first half of
nums
. We take an element from the first half, then an element from the second half, and repeat:1for i in range(3): # range(m) 2 ans.append(nums[i]) # Add from the first half 3 if i + 3 < 6: # Check if the second half index is within bounds 4 ans.append(nums[i + 3]) # Add from the second half
When we iterate through, the
ans
array gets filled as follows:i = 0
: Appendnums[0]
which is1
and thennums[0 + 3]
which is4
, soans = [1, 4]
.i = 1
: Appendnums[1]
which is2
and thennums[1 + 3]
which is5
, soans = [1, 4, 2, 5]
.i = 2
: Appendnums[2]
which is3
and thennums[2 + 3]
which is6
, soans = [1, 4, 2, 5, 3, 6]
.
-
The reordered list
ans
is now[1, 4, 2, 5, 3, 6]
and satisfies the problem condition where no element is equal to the average of its immediate neighbors, and this is returned as the result.
The final output for the initial nums
array is:
1return ans => [1, 4, 2, 5, 3, 6]
The process effectively rearranges the original array preventing any value from being the average of its neighbors by interleaving the first and second halves of the sorted list.
Solution Implementation
1class Solution:
2 def rearrangeArray(self, nums: List[int]) -> List[int]:
3 # Sort the list of numbers in ascending order
4 nums.sort()
5 # Get the length of the nums list
6 n = len(nums)
7 # Find the middle index, rounded up to account for odd lengths
8 # Equivalent to ceil function: m = ceil(n / 2)
9 m = (n + 1) // 2
10 # Initialize an empty list to store the answer
11 ans = []
12 # Iterate over the first half of the sorted list
13 for i in range(m):
14 # Add the current element from the first half to the answer list
15 ans.append(nums[i])
16 # Check if there is a corresponding element in the second half
17 if i + m < n:
18 # Add the corresponding element from the second half to the answer list
19 ans.append(nums[i + m])
20 # Return the rearranged list
21 return ans
22
23# Demonstrating the use of Solution class:
24# Assuming 'List' has already been imported from 'typing' module otherwise, add the following line:
25# from typing import List
26
27# Initialize the class instance
28solution_instance = Solution()
29
30# Example input list of numbers
31input_nums = [6,2,0,9,7]
32
33# Get the rearranged list from the rearrangeArray method
34rearranged_nums = solution_instance.rearrangeArray(input_nums)
35
36# Print the rearranged list
37print(rearranged_nums)
38
1class Solution {
2 public int[] rearrangeArray(int[] nums) {
3 // Sort the array to arrange elements in ascending order
4 Arrays.sort(nums);
5
6 // Find the length of the array
7 int length = nums.length;
8
9 // Compute the mid-index accounting for both even and odd length arrays
10 int midIndex = (length + 1) >> 1;
11
12 // Initialize a new array to store the rearranged elements
13 int[] rearranged = new int[length];
14
15 // Loop to interleave elements from the two halves of the sorted array
16 for (int i = 0, j = 0; i < length; i += 2, j++) {
17 // Place the j-th element from the first half into the i-th position of the rearranged array
18 rearranged[i] = nums[j];
19
20 // Check if there's an element to pair from the second half and place it next to the element from the first half
21 if (j + midIndex < length) {
22 rearranged[i + 1] = nums[j + midIndex];
23 }
24 }
25
26 // Return the rearranged array
27 return rearranged;
28 }
29}
30
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 // Method to rearrange the elements of the array such that each positive integer
7 // is followed by a negative integer and vice-versa.
8 vector<int> rearrangeArray(vector<int>& nums) {
9 // First, sort the elements of the nums array in non-decreasing order.
10 sort(nums.begin(), nums.end());
11
12 // Declare a vector to store the rearranged elements.
13 vector<int> rearranged;
14
15 // Calculate the middle index based on the size of nums to divide
16 // the array into two halves.
17 int mid = (nums.size() + 1) >> 1; // Equivalent to (n+1)/2
18
19 // Loop through the first half of the sorted array.
20 for (int i = 0; i < mid; ++i) {
21 // Add the current element from the first half to the rearranged vector.
22 rearranged.push_back(nums[i]);
23
24 // If the symmetric position in the second half exists, add it to the rearranged vector.
25 if (i + mid < nums.size()) rearranged.push_back(nums[i + mid]);
26 }
27
28 // Return the vector with rearranged elements.
29 return rearranged;
30 }
31};
32
1function rearrangeArray(nums: number[]): number[] {
2 // Sort the elements of the nums array in non-decreasing order.
3 nums.sort((a, b) => a - b);
4
5 // Declare an array to store the rearranged elements.
6 const rearranged: number[] = [];
7
8 // Calculate the middle index based on the size of nums to divide
9 // the array into two halves. Equivalent to (n+1)/2
10 const mid = Math.floor((nums.length + 1) / 2);
11
12 // Loop through the first half of the sorted array.
13 for (let i = 0; i < mid; ++i) {
14 // Add the current element from the first half to the rearranged array.
15 rearranged.push(nums[i]);
16
17 // Check if the symmetric position in the second half exists,
18 // if so, add it to the rearranged array.
19 const secondHalfIndex = i + mid;
20 if (secondHalfIndex < nums.length) {
21 rearranged.push(nums[secondHalfIndex]);
22 }
23 }
24
25 // Return the array with rearranged elements.
26 return rearranged;
27}
28
Time and Space Complexity
Time Complexity
The time complexity of the code consists of the sort operation and the loop that rearranges the elements.
- Sorting the
nums
array takesO(n log n)
time, wheren
is the number of elements innums
. - The for loop runs for
m = (n + 1) >> 1
iterations, which is essentiallyn/2
iterations for largen
. Each iteration executes constant time operations, making this partO(n/2)
which simplifies toO(n)
.
Hence, the overall time complexity is dominated by the sort operation: O(n log n)
.
Space Complexity
The space complexity is determined by the additional space used besides the input nums
array.
- The
ans
list, which containsn
elements, requiresO(n)
space. - There are also constant-size extra variables like
n
,m
, andi
which useO(1)
space.
Thus, the total space complexity is O(n)
for the ans
list.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we