Ninja And Alternating Largest
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].

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

Question

Ninja And Alternating Largest

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].

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

Accepted Answer

The task is to rearrange the given array such that every second element is greater than its left and right element.

Read the number of test cases
For each test case, read the number of elements in the array and the array elements
Iterate through the array and swap elements at odd indices with their adjacent elements if necessary
Check if the rearranged array satisfies the conditions and print 1 if it does, else print 0

Accepted Answer

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.

Space Complexity: O(n)Explanation:

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).

Time Complexity: O(nlogn)Explanation:

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).

Python (3.5)

'''

    Time complexity: O(NLogN)

    Space complexity: O(N)



    Where 'N' is the number of elements of the array

'''



def alternateNumbers(arr):



    n = len(arr)

    # Sort the array

    arr.sort()



    # Pointers to mark the starting and ending poin of initial array and pointer for creating the new array

    k = 0

    l = 0

    r = n - 1

    a = []



    # Condoition to fill the array

    while l < r:

        a.append(l)

        l += 1

        a.append(r)

        r -= 1



    # Returning the rearranged array

    return a

C++ (g++ 5.4)

/*

    Time complexity: O(NLogN)

    Space complexity: O(N)



    Where 'N' is the number of elements of the array

*/

#include 



vector  alternateNumbers(vector  &arr) {



  int n = arr.size();

  // Sort the array

  sort(arr.begin(), arr.end());



  // Pointers to mark the starting and ending poin of initial array and pointer for creating the new array

  int k = 0, l = 0, r = n - 1;

  vector  a(n);



  // Condoition to fill the array

  while (l < r) {

    a[k++] = arr[l++];

    a[k++] = arr[r--];

  }



  // Returning the rearranged array

  return a;

}

Java (SE 1.8)

/*

    Time complexity: O(NLogN)

    Space complexity: O(N)



    Where 'N' is the number of elements of the array

*/



import java.util.ArrayList;

import java.util.Collections;



public class Solution {



	public static ArrayList alternateNumbers(ArrayList arr) {



		int n = arr.size();

		// Sort the array

		Collections.sort(arr);



		// Pointers to mark the starting and ending poin of initial array and pointer for creating the new array

		int k = 0, l = 0, r = n - 1;

		ArrayList a = new ArrayList();



		// Condoition to fill the array

		while (l < r) {

			a.add(arr.get(l++));

			a.add(arr.get(r--));

		}



		// Returning the rearranged array

		return a;

	}

}

Accepted Answer

Traverse Array

We will traverse the array and check if every second element is greater than the left and right elements. If the present element is less than its left element, then we swap the elements. If the current element is less than its right element, then we swap the elements. We continue this for every alternate element. Finally, we return the rearranged array as our final answer.

The steps are as follows:

We run a for loop and traverse every alternate element starting from 1, i.e., i = 1 to i = N-1:
- If the value of array[i] is less than the element at index i - 1, we swap the elements.
- If the value of array[i] is less than the element at index i + 1 and i + 1 is less than N, we swap the elements.
Finally, we return the array as the final answer.

Space Complexity: O(1)Explanation:

O(1).

As we are not using any extra space, hence the overall complexity is O(1).

Time Complexity: O(n)Explanation:

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

As we are traversing every alternating element of the array, we have at most N/2 iterations. Hence, the overall complexity is O(N).