Rearrange Array

Easy
0/40
Average time to solve is 15m
profile
Contributed by
0 upvote
Asked in companies
Thought WorksUnthinkable Solutions

Problem statement

You are given a 0-indexed array ‘NUMS’ consisting of ‘N’ integers. You need to rearrange the array ‘NUMS’ so that numbers at even positions are greater than or equal to those at odd positions.

E.g. ‘NUMS[ i ]’ >= ‘NUMS[ i - 1 ]’ if ‘i’ is even and ‘NUMS[ i ]’ <= ‘NUMS[ i - 1 ]’ if ‘i’ is odd.

If there are multiple ways to rearrange the array, you can choose any.

Example: 
Input: ‘N’ = 4,  ‘NUMS’ = [2, 3, 6, 5] 

Output: [3, 2, 6, 5]

At ‘i’ = 0, ‘NUMS[ i ]’ = 3
At ‘i’ = 1, ‘NUMS[ i ]’ = 2, it satisfies the condition ‘NUMS[ i ]’ <= ‘NUMS[ i - 1 ]’ if ‘i’ is odd.
At ‘i’ = 2, ‘NUMS[ i ]’ = 6, it satisfies the condition ‘NUMS[ i ]’ >= ‘NUMS[ i - 1 ]’ if ‘i’ is even.
At ‘i’ = 3, ‘NUMS[ i ]’ = 5, it satisfies the condition ‘NUMS[ i ]’ <= ‘NUMS[ i - 1 ]’ if ‘i’ is odd.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains an integer ‘N’ denoting the length of the array ‘NUMS’.

The second line of each test case contains ‘N’ integers.
Output format : 
For each test case, you don’t need to return anything. Just rearrange the given input array. 

You may use print statements to debug your code for custom input as the verdict/output will be shown as '1' for correct answer and '0' for incorrect answer.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^5
1 <= A[i] <= 10^9
Sum of ‘N’ <= 10^5
Time Limit: 1 sec
Sample Input 1 :
2
4
4 9 2 6
2
1 2
Sample Output 1 :
9 4 6 2
2 1
Explanation Of Sample Input 1 :
For the first case:
At ‘i’ = 0, ‘NUMS[ i ]’ = 9
At ‘i’ = 1, ‘NUMS[ i ]’ = 4, it satisfies the condition ‘NUMS[ i ]’ <= ‘NUMS[ i - 1 ]’ if ‘i’ is odd.
At ‘i’ = 2, ‘NUMS[ i ]’ = 6, it satisfies the condition ‘NUMS[ i ]’ >= ‘NUMS[ i - 1 ]’ if ‘i’ is even.
At ‘i’ = 3, ‘NUMS[ i ]’ = 2, it satisfies the condition ‘NUMS[ i ]’ <= ‘NUMS[ i - 1 ]’ if ‘i’ is odd.    

For the second case:
At ‘i’ = 0, ‘NUMS[ i ]’ = 2
At ‘i’ = 1, ‘NUMS[ i ]’ = 1, it satisfies the condition ‘NUMS[ i ]’ <= ‘NUMS[ i - 1 ]’ if ‘i’ is odd.
Sample Input 2 :
2
6
20 12 1 28 16 20 
5
2 14 29 21 11
Sample Output 2 :
20 1 28 12 20 16 
14 2 29 11 21
Hint

Can you think of a way to assign only smaller elements at the odd indices?

Approaches (2)
Sorting

In the naive approach, we can assign the smallest ceil( N/2 ) numbers at odd positions and the other  N/2 numbers at the even positions. In this way, numbers at even positions will always be larger than the numbers at odd positions. To implement this approach,  we can iterate over the even indices from left to right and odd indices from right to left and keep on swapping the values of odd positions and even positions.


 

The steps are as follows:-

Function  rearrangeArray(vector<int>& nums):

  1. Sort the 'NUMS' array in non-decreasing order
  2. Initialize two pointers, 'LEFT' = 0 and 'RIGHT' = first odd position from the back.
  3. Loop while 'LEFT' < 'RIGHT':
    • Swap the value 'LEFT' with the value of 'RIGHT'.
    • Increment 'LEFT' by 2.
    • Decrement 'RIGHT' by 2.
Time Complexity

O( N * log( N ) ), Where ‘N’ denotes the length of the array ‘NUMS’.

 

We are sorting the ‘NUMS’ array, which takes the time complexity O( N * log( N ) ). Then we are iterating over the original array ‘NUMS’ to modify it. It has the time complexity of O( N ).

Hence the time complexity is O( N * log( N ) ).

Space Complexity

O( 1 ).

 

We are not using any extra storage.

Hence space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Rearrange Array
Full screen
Console