Last Updated: 17 Jun, 2022
Rearrange Array
Easy
Asked in companies
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.
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
Approaches
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):
- Sort the 'NUMS' array in non-decreasing order
- Initialize two pointers, 'LEFT' = 0 and 'RIGHT' = first odd position from the back.
- Loop while 'LEFT' < 'RIGHT':
- Swap the value 'LEFT' with the value of 'RIGHT'.
- Increment 'LEFT' by 2.
- Decrement 'RIGHT' by 2.
We can iterate over the array, and for each index, we can check if it satisfies the condition or not. If it does not meet the condition, we can swap the value at the current index with the value at the previous index. There can be two cases based on the index:
Case 1: When ‘I’ is even, if ‘NUMS[ i ]’ is smaller than ‘NUMS[ i - 1]’, Swap them. This works because, If ‘I’ is even then ‘I’ -1 is odd thus ‘NUMS[ i - 1 ]’ is smaller than its previous element (if any). We can write the order as ‘NUMS[ i ]’ < ‘NUMS[ i -1 ] <= ‘NUMS[ i - 2 ] (‘i’ >= 2). Here even if we swap NUMS[ i ] with NUMS[ i - 1] previous arrangement will not be disturbed and we can also satisfy the condition.
Case 2: When ‘I’ is odd, if ‘NUMS[ i ]’ is greater than ‘NUMS[ i - 1]’, Swap them. This works because, If ‘I’ is odd then ‘I’ -1 is even thus ‘NUMS[ i - 1 ]’ is greater than its previous element (if any). We can write the order as ‘NUMS[ i ]’ > ‘NUMS[ i -1 ] >= ‘NUMS[ i - 2 ] (‘i’ >= 2). Here even if we swap NUMS[ i ] with NUMS[ i - 1] previous arrangement will not be disturbed and we can also satisfy the condition.
The steps are as follows:-
Function rearrangeArray(vector<int>& nums):
- Iterate over all the elements of 'NUMS' starting from 2nd element, for 'I' = 1...'N'.
- If 'I' is even and 'NUMS[ i ]' is less than 'NUMS[ i - 1 ]' then swap the value of 'NUMS[ i ]' with 'NUMS[ i - 1 ]'.
- Else If 'I' is odd and 'NUMS[ i ]' is greater than 'NUMS[ i - 1]’ then swap the value of 'NUMS[ i ]' with 'NUMS[ i - 1 ]'.