Zig - Zag Array

Easy

0/40

12 upvotes

Asked in companies

Problem statement

You are given an array of distinct elements, and you have to rearrange the array elements in a zig-zag fashion. In other words, for every odd position ‘i’ in the array 'ARR,' 'ARR'[i] should be greater than 'ARR'[i-1] and 'ARR'[i] should be greater than 'ARR'[i+1].

For example:

Given ‘N’ = 4, 
'ARR' = { 4, 3, 2, 1} 
Then a possible array is 3, 4, 1, 2.

Note:

You are supposed to return the array, which is in a zig-zag fashion.

Since there can be multiple answers for a particular array, any of the possible solutions are accepted.

It can be proved. A zig-zag array is always possible for a given array.

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

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single integer, ‘N,’ where ‘N’ is the number of elements of the array.

The second line of each test case contains ‘N’ space-separated integers, denoting the array elements.

Output Format :

For each test case, You are supposed to return a zig-zag array for the given array. The runner function will print a single line containing a single integer which denotes whether the returned array is in zig-zag fashion or not.

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’ <= 5*10^3
0 <= 'ARR'[i] <= 10 ^ 6

Time Limit: 1sec.

Sample Input 1 :

Sample Output 1 :

1
1

Explanation of the Sample Input 1:

For the first test case :  
One possible configuration can be 3 4 1 2. Therefore, the array can be converted into a zig-zag fashion.

For the second test case:
One possible configuration can be 2, 8, 6, 10, 4. Therefore the given array can be converted.

Sample Input 2 :

Sample Output 2 :

1
1

Hint 1

Hint 2

Can we use sorting to solve this problem?

Approaches (2)

Approach 1

Approach 2

Sorting

The idea is to sort the array and swap the pair of elements starting from index 1 (0-based Indexing).

The steps are as follows:

Sort the array in ascending order.
Loop ‘i’ = 0, from index 1 to ‘N’ and at each iteration increase ‘i’ by 2.
- Swap elements at positions ‘i’ and ‘i + 1’.
We will return the array ‘arr’ as the final answer.

Time Complexity

O(N*log(N)), where ‘N’ is the number given.

Since we are sorting the array and traversing the array once, the time complexity is O(N + N*log(N)). Hence, the overall time complexity will be O(N*log(N)).

Space Complexity

O(1).

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

(100% EXP penalty)

Zig - Zag Array

Console