Ninja And Alternating Largest

Easy

0/40

1 upvote

Asked in company

Problem statement

Ninja is given a few numbers, and he is being asked to rearrange the numbers so that every second element is greater than its left and right element.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains a single integer T, representing the number of test cases.

The first line of each test case contains ‘N’, denoting the number of elements in the array.

The second line of each test case contains the array elements.

Output Format :

 The first and only line of each test case in the output contains the rearranged array.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10    
1 <= N <= 10^5
0 <= array[i] <= 10^5     

Time limit: 1 second

Sample Input 1:

2
7
1 2 3 4 5 6 7
4
8 2 4 6

Sample Output 1:

1 3 2 5 4 7 6
2 8 4 6

Explanation for Sample Output 1:

 In the first test case, we traverse every second element of the array and check whether it is greater than its left and right element. If it is not, then we rearrange the array; else, we keep it as it is. So we first rearrange positions of 2 and 3 and follow similar steps to rearrange the array.

In the second test case, we traverse the array for every second element. As here 2 is less than its left element, so we do a rearrangement. Similarly, we rearrange the whole array.

Sample Input 2:

2
6
9 7 1 2 9 6
3
3 2 1

##### Sample Output 2: 7 9 1 9 2 6 2 3 1

Approaches (1)

Approach 1

Brute force

Time Complexity

Space Complexity

(100% EXP penalty)

Ninja And Alternating Largest

Console