Ninja And Alternating Largest

Easy
0/40
Average time to solve is 15m
0 upvote
Asked in company
Acko

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.

Suppose the given array is [1, 2, 3, 4, 5] then the rearranged array can be [1, 3, 2, 5, 4].

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 1 if the array satisfies the conditions mentioned.
Note: 
If the array returned is the rearranged array following all the conditions, then it will print 1 else it will print 0.
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^4
0 <= array[i] <= 10^5     

Time limit: 1 sec
Sample Input 1:
2
7
1 2 3 4 5 6 7
4
8 2 4 6
Sample Output 1:
1 
1
Explanation for Sample Output 1:
In the first test case,  [1, 3, 2, 5, 4, 7, 6] is one possible answer. The reason is every second element of the array is greater than its left and right element. So on returning this 1 is the output.

In the second test case,  [2, 8, 4, 6] is one possible answer. The reason is every second element of the array is greater than its left and right element. So on returning this 1 is the output.
Sample Input 2:
2
6
9 7 1 2 9 6
3
3 2 1
Sample Output 2:
1
1
Hint

Can you sort the array?

Approaches (2)
Brute Force

We will sort the array. Then we take an auxiliary array and fill it with the elements of the sorted array starting from both the ends in an alternate order.

 

The steps are as follows:   

  • We sort the array.
  • We take two pointers ‘l’ to mark the first element of the array, ‘r’ to mark the last element of the array, and ‘k’ to mark the present element of an array.
  • We run a while loop as long as l < r.
    • We store in an auxiliary array A[k] the value of array[i] and increment both i and k.
    • We store in an auxiliary array A[k] the value of array[j] and increment k and decrement j simultaneously.
  • Finally, we return the array ‘A’ as the final answer.

   

Time Complexity

O(NLogN), where ‘N’ is the number of elements in the array.

 

As we are sorting the whole array, it takes N*LogN time. Hence, the overall complexity is O(NLogN).

Space Complexity

O(N), where ‘N’ is the number of elements in the array

 

As we require an auxiliary array, hence the overall complexity is O(N).

Code Solution
(100% EXP penalty)
Ninja And Alternating Largest
Full screen
Console