(**Asked in top MNC’S like AMAZON, MICROSOFT, GOLDMAN SACHS, PAYTM..etc**)

Given an unsorted array of integers, sort the array into a wave like array. An array ‘**arr[0..n-1]**’ is sorted in wave form if **arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= …..**

**Problem Statement:**

Given a sorted array **arr[]** of distinct integers. Sort the array into a wave-like array and return it. In other words, arrange the elements into a sequence such that **a1 >= a2 <= a3 >= a4 <= a5…..** (considering the increasing lexicographical order).

**Input Format:**

The first line contains an integer **T**, depicting total number of test cases. **T** testcases follow. The first line of each testcase contains an integer **N**depicting the size of the array. The second line contains N space separated elements of the array.

**Output Format:**

For each testcase, in a new line, print the array into wave-like array.

**User Task:**

The task is to complete the function **convertToWave**() which converts the given array to wave array.** The newline is automatically added by the driver code**.

**Expected Time Complexity: **O(N).

**Expected Auxiliary Space: **O(1).

**Constraints:**

1 ≤ T ≤ 100

1 ≤ N ≤ 10^{6}

0 ≤ A[i] ≤10^{7}

**Example:**

**Input**:

2

5

1 2 3 4 5

6

2 4 7 8 9 10

**Output**:

2 1 4 3 5

4 2 8 7 10 9

**Explanation:**

Testcase 1: Array elements after sorting it in wave form are 2 1 4 3 5.

**Testcase 2:** Array elements after sorting it in wave form are 4 2 8 7 10 9.

The simple apporach to solve the given problem is that

Iterate through the give array from index **0** to **n-1** times by incrementing the value of **i** by **2**.

**Function to sort array in wave from given below:**

public static void convertToWave(int arr[], int n){
for(int i=0; i<n-1; i+=2) {
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}

the above apporach will take O(nLOGn) time for sorting algorithm like merge sort.

So i hope you all understand the simple implementation of wave array in java.

Thank You..

Happy Coding..!

### Like this:

Like Loading...

Categories: HackerRank Questions, Interview, JAVA

Tags: Amazon, goldman sachs, paytm, simple solution to sort array in java, sort array, sort array in wave form, sorting in java, wave form in java, wave sort array

## Leave a Reply