## Google Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**Phone Interview

The 2nd solution may not work always. E.g:- It works for (0 1 2 3) giving 1 0 3 2 but for (2 3 0 1) it gives 3 2 1 0 which is incorrect.

The median solution looks cool. Find elements greater than the median and put them in even numbered locations. Find elements smaller than the median and put them in odd numbered locations.

Yeah, the median solution is cool. But what is it's efficiency class? Isn't it quadratic?

No, finding median is O(n). And then we linearly traverse the input array A. If A[i] > median, we put it in a even numbered location in the output array. If A[i] < median, we put it in a odd numbered location. So this will also take O(n) time but O(n) space too.

Yeah, finding median is O(n). That is fine. My question is about worst case efficiency. How does it perform on this worst case input (1 2 3 4 5 6 7 8 9)?

It will still be linear for your input.

The basic code is as follows:-

```
float median = find_median(a);
int even = 0;
int odd = 1;
for(int i = 0; i < n ; i++)
{
if(a[i] < median)
{
b[odd] = a[i];
odd = odd + 2;
}
else
{
b[even] = a[i];
even = even + 2;
}
}
```

Here is the C++ code for solution 2:

```
void rearrange(std::vector<int> &A) {
for (int i = 0; i < A.size(); ++i) {
if (((i & 1) == 0 && A[i] > A[i +1]) || (i & 1) && A[i] < A[A+1])) {
std::swap(A[i], A[i + 1])
}
}
}
```

Very nice solution of swapping adjacent numbers if they don't fit in the arrangement. O(n) solution without any extra space.

How did you come up with this?

Sorry the above code needs a few changes, because I typed too fast:

```
void rearrange(std::vector<int> &A) {
for (int i = 0; i < A.size() -1; i++) {
if ( ((i & 1) == 0 && A[i] < A[i +1]) || ((i & 1) && A[i] > A[i+1]) ) {
std::swap(A[i], A[i + 1]);
}
}
}
```

@pratik Here are the trace output after each swap for your counter example:

Start:

2 3 0 1

3 2 0 1

3 0 2 1

End: 3 0 2 1

@srini

Start:

8 9 6 7

9 8 6 7

9 6 8 7

End:9 6 8 7

@pratik, Yes, your above code runs in linear time but uses additional storage which is equal to original array.

@oOZz, That's cool. You are right, it runs in linear time. This can also be solved with 3 elements at a time, placing smallest of 3 in the middle position and moving 2 positions right, as I mentioned below. Also, about your solution 1, isn't it quadratic time in worst case?

No srini, they are both linear time solutions. In solution 1 you, you first find median in O(n) and then rearrange the elements in O(n), so it's 2 *O(n) , which is O(n) asymptotically, not O(n^2).

I support this solution. just keep checking backward for its right place. Only need update is swap once more if i-1<i<i+1 or other way around. if once more time swap then it will break the order and then it will algo will never look further back. So its still O(n).

Right. But after two numbers are swapped, don't forget to check if it violate the order of A[i-1] and A[i], it may happen.

Your solution 2 is the best. @Avaln: you don't need to check backwards. It is satisfied automatically.

For the 2nd solution, you will want to check the number at every index, not only the even-index ones. Otherwise it will not work, as shown by the counter example given previously by the other person: 8 9 6 7 => 9 8 7 6

So you should do as such (0-index):

at even index i, swap A[i] and A[i+1] if A[i] < A[i+1]

at odd index j, swap A[j] and A[j+1] if A[j] > A[j+1]

impresive .but this problem can have multiple sequence of answer .so what if they ask for some other sequence.

1) Sort the list first (5, 7, 1, 8, 3, 2, 9, 4, 2, 6 becomes 1, 2, 3, 4, 5, 6, 7, 8, 9)

2) Start filling the the odd indices. Keep track of remaining numbers and the number even slots (even slots are empty). The new array is like 1, _, 2, _, 3, _, 4 etc.

3) When the # of empty slots equals remaining numbers (there could be a boundary condition here +/- 1), start filling the even slots. That is when the array becomes 1, _, 2, _, 3, _, 4, _, 5 we have 4 dashes and 4 remaining numbers {6, 7, 8, 9}

So start filling the dashes. that is 1, 6, 2, 7, 3, _, 4, _, 5 and like that.

4) The end result will be 1, 6, 2, 7, 3, 8, 4, 9, 5 which is a solution.

Complexity = Sort + 2 pass

O ( n log n + 2*n) = O (n log n)

First, find the midpoint of the set. A great way to do this is to use a modified quicksort where you only drill into the partition on either side of your pivot that you know contains the midpoint. Return the midpoint as soon as the number of items to the left is equal to half the size of the list.

Then, just create a left and right list populated by taking every element from the original list except the midpoint and putting it in left if it's lower, right if it's higher. Merge the lists together by interleaving them, and put the midpoint at the end. The final ordering will match the required parameters, and except in worst case (an ordered list) the whole function is O(n).

```
import random
def arrange_high_low(shuffled_list):
list_copy = shuffled_list[:]
k = int(shuffled_list.__len__() / 2)+1
size_left = 0
pivot = 0
while size_left != k:
pivot = shuffled_list.pop()
left = []
right = []
while shuffled_list:
x = shuffled_list.pop()
if x < pivot:
left.append(x)
else:
right.append(x)
if size_left+left.__len__()+1 > k:
shuffled_list = left[:]
elif size_left+left.__len__()+1 < k:
shuffled_list = right[:]
size_left += left.__len__()+1
else:
break
print pivot
left = []
right = []
for i in list_copy:
if i < pivot:
left.append(i)
elif i > pivot:
right.append(i)
left.append(pivot)
right.append(pivot)
even = 0
final = []
for i in list_copy:
if even:
final.append(right.pop(0))
even = 0
else:
final.append(left.pop(0))
even = 1
return final
shuffled_list = range(1,21)
random.shuffle(shuffled_list)
print ', '.join(map(str, arrange_high_low(shuffled_list)))
```

Swapping alternate elements solves the problem

```
private static void arrangeList(int A[]) {
for (int i = 1; i < A.length; i++) {
if (i % 2 == 1 && A[i] < A[i - 1])
swap(A, i, i - 1);
if (i % 2 == 0 && A[i] > A[i - 1])
swap(A, i, i - 1);
}
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
```

Seems like most of swaps are done by the second if statement, if (i % 2 == 0 && A[i] > A[i - 1]). Under what case will it go into the first if statement?

Sorting => usually O(nlogn)

Then the swapping =>O(n)

Total =?

Wherease just swapping = O(n)

Sit down with pen and paper and trace code posted by people you trust, and find bugs OR learn from good code (whichever the case).

This algorithm will not work in below input

1,3,3,4

Above mentioned code will end up in showing same sequence, without any swapping.

Actual expected output is

3,4,1,3

This is a great example of a question where it can just be blow off to a completely hard problem. The trick is that the inequalities are not implying anything.

@thelineofcode is basically comparing 2 x 2 and making sure the inequality holds.

```
input = [7, 6, 5, 4, 3, 2, 1, 0]
print input
sorted_output = sorted(input)
sorted_output.reverse()
output = [sorted_output[0]]
for i in range(1, len(input)):
if i % 2 == 1 and len(input) > i + 1:
output.extend([sorted_output[i+1],sorted_output[i]])
if len(input) % 2 == 0:
output.append(sorted_output[-1])
print output
```

Question is ambiguous (as usualy for CC).

a < b > c < d <-expressions like this are not well defined nor used in math.

a < b < c is an idiom that has come to mean a < b && b < c

But since it's the same inequality < used in both places, it matters not whether we explicitly state that a < c also (because this is true by transitivity automatically).

We can extend this to a < b < c < d < e < f safely.

Note above implies 5 inequalities directly, and 6choose2 inequalities in total.

Now if you have something like a < b > c < d > e

What does this say about the relative ordering of a vs. d or b vs. e ?

Or does it say nothing about these?

Heres a full solution in C#:

1. Sort the array in incrementing order

2. Check each value of the array (starting at 0), and determine if it withholds the stated rules (if even index, should be less than right, if odd should be greater than)

3. If not, continue moving right along indices and find element that withholds rules

4. Continue till exhausted all indices

```
using System;
namespace SortNegativeArray
{
class MainClass
{
public static int[] nums = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
public static void Main (string[] args)
{
Array.Sort(nums); //First sort the array in incrementing order
PrintArray();
SortNums(0);
PrintArray();
}
public static void SortNums(int index) {
Console.WriteLine("Pass " + index);
if (index == nums.Length) return;
//If its an even number, handle appropraitly
if (index == 0 || (index%2 == 0)) {
//Check less than right â†’ We can assume this since we made it this far
for(int i = index+1; i < nums.Length; i++) {
//If Iâ€™m less then the next one, weâ€™re good, break the loop
if (nums[index] < nums[i] && i == index+1) {
break;
}
//Otherwise check if its less than the number if so replace whats already there
else if (nums[index] > nums[i]) {
int temp = nums[i];
nums[i] = nums[index];
nums[index] = temp;
break;
}
}
}
//Likewise for odd
else {
//Check greater than right â†’ We can assume this since we made it this far
for(int i = index+1; i < nums.Length; i++) {
if (nums[index] > nums[i] && i == index+1) break;
else if (nums[index] < nums[i]) {
int temp = nums[i];
nums[i] = nums[index];
nums[index] = temp;
}
}
}
SortNums(++index);
}
public static void PrintArray() {
Console.WriteLine("--Printing Array--");
foreach(int num in nums) Console.Write(num + " ");
Console.WriteLine("----------------");
}
}
```

}

```
#include <stdio.h>
#define MAX_SIZE_ARRAY 10
void sortarray(int a[]);
void swap(int *a, int *b);
void sequence_swap(int * a);
int main(void)
{
int a[MAX_SIZE_ARRAY], index;
printf("Enter array elements\n");
for(index = 0; index < MAX_SIZE_ARRAY; ++index)
scanf("%d",&a[index]);
printf("Entered array elements is:\n\n");
for(index = 0; index < MAX_SIZE_ARRAY; ++index)
printf("%d ",a[index]);
printf("\n");
sortarray(a);
printf("sorted array is:\n");
for(index = 0; index< MAX_SIZE_ARRAY; ++index)
printf("%d ", a[index]);
printf("\n");
sequence_swap(a);
printf("a<b>c<d>e etc sequence is:\n");
for(index = 0; index< MAX_SIZE_ARRAY; ++index)
printf("%d ", a[index]);
return 0;
}
void sortarray(int *a)
{
int i , j, n;
n = MAX_SIZE_ARRAY;
for(i = 0; i < n; ++i)
for (j = n - 1; j > i; --j)
if(a[j-1] > a[j])
swap(&a[j],&a[j-1]);
}
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void sequence_swap(int *a)
{
int i;
int temp;
for (i =1; i < MAX_SIZE_ARRAY-1 ; i +=2 )
{
temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
}
```

}

Here is my solution in Java. Let me know what you think.

```
package InterviewPractice;
import java.util.Arrays;
public class sortArray {
public static void main(String[] args) {
int[] nums = new int[]{1,8,2,5,9,3,6,4,7,15,21,12};//this is the array of ints, it can change
Arrays.sort(nums); //sort the array
int[] swapped= swap(nums); //call swap on nums array
System.out.println(Arrays.toString(swapped)); //print result of swap
}
public static int[] swap(int[] arr) {
int[] returnArr = new int[arr.length];
returnArr[0] = arr[0];
int arrCounter = 2;
for (int i = 1; i < arr.length - 1; i++) {
returnArr[i]=arr[arrCounter];
if(i%2==0){
arrCounter+=3;
}else{
arrCounter--;
}
}
if(arr.length%2==0){
returnArr[returnArr.length-1]=arr[arr.length-1];
}else{
returnArr[returnArr.length-1]=arr[arr.length-2];
}
return returnArr;
}
}
```

I think there is no need to sort complete array, we can make use of min-heap here. Complete algorithm can complete in O(n/2 * log n)

Steps:

1. Transform array into min-heap, in O(n)

2. Swap root with second last element in array

3. Reduce heap size by 2 (which means last 2 elements are already in required form)

4. Heapify root element.

5. Repeat steps 3 and 4 until heap size becomes 0 (this operation completes in O(n/2 * log n))

Please refer below source code

```
import java.util.Random;
public class Seven {
public static int[] numbers = new int[21];
public static int size = numbers.length;
public static void main(String [] args) {
//prepare input
Random rn = new Random();
System.out.println("Original array");
for (int i=0; i<numbers.length; i++){
numbers[i] = rn.nextInt(100);
System.out.print(" " + numbers[i]);
}
//transform array which contains actual algorithm
transformArray();
//print output
System.out.println("\nTransformed array");
for(int k=0; k<numbers.length; k++){
System.out.print(" " + numbers[k]);
}
}
private static void transformArray() {
//Transform un-sorted array into min-heap -> O(n)
for(int j=size-1/2; j>=0; j--){
minHeapify(j);
}
//Size getting decremented by 2, so n/2 iterations
while (size>0){
if(size%2==1){
swap(0,size-1);
size-=1;
}else{
swap(0,size-2);
size-=2;
}
//min-heapify single element -> O(log n)
minHeapify(0);
}
}
private static void minHeapify(int i) {
int smallest;
int left = i * 2;
int right = i * 2 + 1;
if (((left < size) && (numbers[left] < numbers[i]))) {
smallest = left;
} else {
smallest=i;
}
if (((right < size) && (numbers[right] < numbers[smallest]))) {
smallest = right;
}
if (smallest != i) {
swap(i, smallest);
minHeapify(smallest);
}
}
private static void swap(int i, int j) {
int t = numbers[i];
numbers[i] = numbers[j];
numbers[j] = t;
}
}
```

a brute force solution which lists all combinations of possible solutions given an unordered array.

```
public class ArrayTest1 {
public static void main(String[] args){
int[] a = new int[10];
Random r = new Random();
for (int i = 0; i < a.length; i++){
a[i] = r.nextInt(10);
System.out.print(a[i] + ",");
}
System.out.println();
List<List<Integer>> results = new ArrayList<List<Integer>>();
for (int i = 0; i < a.length; i++){
exch(a, 0, i);
inequalty(a, 0, true, results);
}
for (List<Integer> sol: results){
System.out.println();
for (Integer i: sol)
System.out.print(i + ",");
}
}
private static void inequalty(int[] a, int index, boolean condition, List<List<Integer>> results){
if (a == null || a.length == 0) return;
if (index == a.length - 1){
List<Integer> r = new ArrayList<Integer>();
for (int i = 0; i < a.length; i++)
r.add(a[i]);
results.add(r);
}
else{
for (int i = index + 1; i < a.length; i++){
if (a[i] > a[index] == condition && a[i] != a[index]){
if (i != index + 1)
exch(a, i, index + 1);
inequalty(a, index + 1, !condition, results);
}
}
}
}
private static void exch(int[] a, int i, int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
```

```
std::list<int> L ={16,2,9,7,1,8,5,3,6,2,8,2};
L.sort();
L.unique();
std::vector<int> V {std::make_move_iterator(std::begin(L)),
std::make_move_iterator(std::end(L)) };
for (int i = 0; i<V.size()/2; i++) {
if (i%2 ==1) {
// a < b > c < d > e, etc
std::iter_swap(V.begin()+i, V.begin()+i+V.size()/2-1);
}
}
for (int i = 0; i<V.size(); i++) {
std::cout<<V[i]<<" ";
}
```

a<b>c<d...

a<b means a must not be the maximum number, so let's swap a[0] and a[1] if a[0] > a[1], this guarantees a is not the maimum number in the array.

b>c means b must not be the minimum number, so let's swap b and a[2] if b < a[2], this guarantees b (the a[1] after possible swap) is not the minimum number from a[1] to a[n];

do it till end.

The algorithm is:

if i % 2 == 0, swap a[i] and a[i + 1] if a[i] > a[i + 1];

else swap a[i] and a[i + 1] if a[i] < a[i + 1];

for i = 0 to n -1;

```
void reorder(int* a, int size)
{
for (int i = 0; i < size - 1; ++i)
{
if ((i % 2 == 0 && a[i] > a[i + 1]) ||
(i % 2 == 1 && a[i] < a[i + 1]))
{
a[i] ^= a[i + 1];
a[i + 1] ^= a[i];
a[i] ^= a[i + 1];
}
}
}
```

The trick is to sort them.

```
#include<stdio.h>
void sort(int *array1, int size);
void scramble(int *array1, int size);
void print(int *array1, int size);
int main(void)
{
int array1[13] = {8,3,1,89,6,4,5,12,33,456,90,81,2};
print(array1, 13);
scramble(array1, 13);
print(array1, 13);
return 0;
}
void sort(int *array1, int size)
{
for(int i = 0; i < size - 1; i++)
{
for(int j = i + 1; j < size; j++)
{
if(array1[i] > array1[j])
{
int temp = array1[i];
array1[i] = array1[j];
array1[j] = temp;
}
}
}
}
void scramble(int *array1, int size)
{
sort(array1, size);
for(int i = 0; i < size - 1; i += 2)
{
int temp = array1[i];
array1[i] = array1[i+1];
array1[i+1] = temp;
}
}
void print(int *array1, int size)
{
for(int i = 0; i < size - 1; i++)
{
printf("%d, ", array1[i]);
}
printf("%d\n", array1[size-1]);
}
```

An O(n) time, O(1) space solution:

Consider 3 consecutive numbers A(i), A(i+1), A(i+2)

Suppose A(i) and A(i+1) are in correct order.

If A(i+1) and A(i+2) are also in correct order, then continue doing for A(i+1), A(i+2), A(i+3);

If A(i+1) and A(i+2) are not in correct order, then swap A(i+1) and A(i+2). After swapping, A(i), A(i+2), A(i+1) must be all in correct order (can you check that ?). Then, continue doing for A(i+2), A(i+1), A(i+3)...

Initially, we can swap A(1) with the max of (A). Then A(1), A(2) will be in correct order.

```
def waveSort(array):
# First sort the list.
array.sort()
# Get an index for the midpoint of the sorted list.
lenA = len(array)
splitIndex = lenA // 2
# Now we are going to go through half the list and append
# an element from the first half and from the second half
# to the solution, producing a wave.
result = []
for i in range(splitIndex):
result.append(array[splitIndex+i])
result.append(array[i])
# If the array had odd length, we have skipped the last element
# in above loop, so we simply append before returning solution
if lenA % 2 == 1: result.append(array[-1])
return result
# print waveSort([6,2,4,3,8,9,1,5,7])
# print waveSort([6,2,4,3,8,9,1,10,5,7])
```

```
This is O(n) solution.
public static int[] createWave(int[] arr){
for(int i=0; i<arr.length-1;i++){
if(i%2 == 0){
if(arr[i] < arr[i+1]){
arr = swap(arr,i,i+1);
}
}else{
if(arr[i] > arr[i+1]){
arr = swap(arr,i,i+1);
}
}
}
return arr;
}
private static int[] swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
```

Arrange first 3 elements (0,1,2) in desired order and then shift 2 positions right and again order next 3 elements (2,3,4) and continue doing the same till you reach end of the array. Resultant array is the desired one.

This algorithm does n/2 iterations and no extra space.

It is n/2 because you are shifting 2 positions right. But this will make 2 comparisons to find smallest of 3 on each iteration. So, effectively it is O(n).

And regarding comparisons, compare 3 elements and place smallest of 3 elements in the middle position (which is always odd position because we are shifting 2 positions on each iteration) of the 3 element window.

Example

Input: 1 2 3 4 5 6 7

1st: 3 1 2 4 5 6 7

2nd: 3 1 5 2 4 6 7

3rd: 3 1 5 2 7 4 6

O(n) Solution, can any tell am I correct or not?

Thanks in advance.

```
public class O {
public static void main(String[] args) {
int a[] = { 4, 3, 2, 1, 8, 9 };
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
for (int i = 0; i < a.length; i += 2) {
if (i + 1 == a.length) {
break;
}
if (a[i] < a[i + 1]) {
int t = a[i];
a[i] = a[i + 1];
a[i + 1] = t;
}
if ((i + 2) >= a.length) {
break;
}
if (a[i + 1] > a[i + 2]) {
int t = a[i + 1];
a[i + 1] = a[i + 2];
a[i + 2] = t;
}
}
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
}
```

sol1. First sort the array, then swap pairs of numbers.

sol2. Traverse the array starting from the first vertex till the second last vertex, when at an even position swap the value with the next position if the former is smaller; when at an odd position swap the value with the next position is the former is larger

```
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int main () {
int A[] = {1,2,3,4,5,6};
// solution 1, O(nlog(n))
int len_a = sizeof(A)/sizeof(int);
sort(A, A+len_a);
for (int i = 0; i < len_a; i+=2) {
swap(A[i], A[i+1]);
}
cout << "{";
for (int i = 0; i < len_a; i++) cout << A[i] << ", ";
cout << "}" << endl;
// solution 2 O(n)
for (int i = 0; i < len_a-1; i++) {
if (i & 1) {
if (A[i] > A[i+1]) swap(A[i], A[i+1]);
}
else {
if (A[i] < A[i+1]) swap(A[i], A[i+1]);
}
}
cout << "{";
for (int i = 0; i < len_a; i++) cout << A[i] << ", ";
cout << "}" << endl;
}
```

if we dont need to satisfy a1<a3<a5... and a2<a4<a6..., then will took O(n)

if we do, just do a quick sort before this, any way the sort will always took O(nlogn) average

```
void wave(int *a, int size)
{
if (size < 1)
return;
else if (size == 2)
{
if (a[0] < a[1])
swap(a[0], a[1]);
return;
}
for (int i = 0; i < size - 2; i+=2)
{
if (a[i] < a[i+1])
swap(a[i], a[i+1]);
if (a[i+1] > a[i+2])
swap(a[i+1], a[i+2]);
}
}
```

I have implemented simple soultion as mentioned by - tejaswi.yvs

```
import java.util.Arrays;
/**
* @author vishal.naik
*
*/
public class WaveSort {
public static void main(String[] args) {
int[] arr = { 7, 3, 6, 9, 2, 5, 8, 4 };
waveSort(arr);
printArray(arr);
}
/**
* Sorts the input array such that a1 >= a2 <= a3 >= a4 <= a5...
*
* @param arr , not null
*/
private static void waveSort(int[] arr) {
// Sort the array. This sorts array in ascending order.
Arrays.sort(arr);
//Reverse the array. So the array will be in descending order.
reverse(arr);
// Iterate over the sorted array.
for (int i = 1; i < arr.length - 1; i = i + 2) {
// Swap the numbers.
swap(i, i + 1, arr);
}
}
/**
* Prints the array.
*
* @param arr , not null
*/
private static void printArray(final int[] arr) {
for (int i : arr) {
System.out.print(i + " ");
}
}
/**
* Reverses the array.
*
* @param arr , not null
*/
private static void reverse(int[] arr) {
int start = 0;
int end = arr.length -1;
while(start <= end) {
swap(start, end, arr);
start++;
end--;
}
}
/**
* Swaps the element at position i with element at position j.
* @param i , not null
* @param j , not null
* @param arr , not null
*/
private static void swap(final int i, final int j, int[] arr) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
```

Please visit java-fries site for the complete article.

Keep track of the current wave trend, up or down in a boolean value, swap adjacent numbers if the trend is violated. If swapped, go back one position to make sure it doesn't violate the sorted trend, but do not go back if i is already 0.

P.S. Can't believe the solution that requires sorting the entire array got the most votes.

```
WaveArray(int[] A){
int i = 0;
boolean up = true;
while(i < A.length() - 1){
if(isValidWave(up, i)){
i++;
up = !up;
}
else{
swap(A, i, i+1);
if( i > 0){
i--;
up= !up;
}
}
}
}
isValidWave(boolean up, int i, int[] A){
if(up)
return A[i] <= A[i+1];
else
return A[i] >= A[i+1];
}
```

We can optimize this solution by not sorting.

1. Find the median (or kth element)... QuickSelect is O(n). This will enable us to find the median without sorting.

2. Iterate the array with two indices (one pointing to the next item equal or less than the median, and the second pointing to the next item larger than the median.)

2a. If odd iterator, swap with next equal or less.

2b. if even iterator, swap with next larger

The first part is a standard solution (you use either the built-ins or write your own). The second part is a simple coding...

```
int[] LTGTSort (int arr[], int size)
{
// check for invalid arr and size here
int median = QuickSelect(arr, size); // did not verify this function signature, but you get the idea.
for (int i = 0; i < size; i++)
{
for (int j = i; j < size; j++) // this search can only be at most n/2
{
if (i%1 && arr[j] <= median) // odd
{
swap(arr, i, j);
break;
}
else if (arr[j] > median) // even
{
swap(arr, i, j)
break;
}
}
}
return arr;
}
```

```
import java.util.*;
public class swap {
void swapElements(ArrayList<Integer> inp)
{
for(int i=1; i < inp.size();i++)
{
if((i%2==1 && inp.get(i) > inp.get(i-1)) || (i%2==0 && inp.get(i) < inp.get(i-1)))
{
//swap Elements
inp.set(i-1, inp.get(i-1)^inp.get(i));
inp.set(i,inp.get(i-1)^inp.get(i));
inp.set(i-1, inp.get(i-1)^inp.get(i));
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
swap obj=new swap();
ArrayList<Integer> inp=new ArrayList<Integer>(Arrays.asList(2, 3, 0, 1 ));
obj.swapElements(inp);
for(int elem : inp)
System.out.print(elem+" ");
}
}
```

```
vector<int> build_wave(vector<int> v) {
sort(v.begin(), v.end());
int sz = v.size();
int num_up = sz / 2 + sz %2;
int num_down = sz / 2;
vector<int> n(sz);
// up values
for (int i = 0, k = 0; i < sz; i+= 2, k++) {
n[i] = v[k + sz/2];
}
// down values
for (int i = 1, k = 0; i < sz; i+= 2, k++) {
n[i] = v[k];
}
}
```

```
vector<int> build_wave(vector<int> v) {
sort(v.begin(), v.end());
int sz = v.size();
int num_up = sz / 2 + sz %2;
int num_down = sz / 2;
vector<int> n(sz);
// up values
for (int i = 0, k = 0; i < sz; i+= 2, k++) {
n[i] = v[k + sz/2];
}
// down values
for (int i = 1, k = 0; i < sz; i+= 2, k++) {
n[i] = v[k];
}
}
```

//without expensive sorting algo; complexity O(n)

public class waveSort2 {

public static void main (String[] args){

int [] arr = {9,12,10,3,7,17,4,10,20};

//output must be {a1 >= a2 <= a3 >= a4 <= a5 >=a6 <=a7}, {12 9 10 3 7 4 17 10 20}

waveSort(arr);

printArray(arr);

}

private static void printArray(int[] arr) {

// TODO Auto-generated method stub

for (int i : arr) {

System.out.print(i + " ");

}

}

public static void waveSort(int[] arr) {

// TODO Auto-generated method stub

for (int i=1; i < arr.length-2; i=i+2)

{

if ((arr[i-1] < arr[i]) && (arr[i] < arr[i+1]) && (arr[i-1] < arr[i+1]))

{

swap(i-1, i+1, arr);

}

else if ((arr[i-1] < arr[i]) && (arr[i] > arr[i+1]) && (arr[i-1] < arr[i+1]))

{

swap(i-1, i, arr);

}

else if ((arr[i-1] > arr[i]) && (arr[i] > arr[i+1]) && (arr[i-1] > arr[i+1]))

{

swap(i, i+1, arr);

}

else if ((arr[i-1] < arr[i]) && (arr[i] > arr[i+1]) && (arr[i-1] > arr[i+1]))

{

swap(i, i+1, arr);

}

else if ((arr[i-1] < arr[i]) && (arr[i] > arr[i+1]) && (arr[i-1] < arr[i+1]))

{

swap(i, i-1, arr);

}

}

}

public static void swap(int i, int j, int[] arr) {

// TODO Auto-generated method stub

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

}

#include<bits/stdc++.h>

using namespace std;

int a[1000<<2];

int main()

{

long long int i,j,k,m,n;

cin>>n;

for(i=0;i<n;i++)

{

cin>>a[i];

}

for(i=0;i<n;i=i+2)

{

if(i==0)

{

if(a[i]<a[i+1])

{

swap(a[i],a[i+1]);

}

}

if(a[i]<a[i+1])

{

swap(a[i],a[i+1]);

}

if(a[i]<a[i-1])

{

swap(a[i],a[i-1]);

}

}

for(i=0;i<n;i++)

{

cout<<a[i]<<" ";

}

}

#include<bits/stdc++.h>

using namespace std;

int a[1000<<2];

int main()

{

long long int i,j,k,m,n;

cin>>n;

for(i=0;i<n;i++)

{

cin>>a[i];

}

for(i=0;i<n;i=i+2)

{

if(i==0)

{

if(a[i]<a[i+1])

{

swap(a[i],a[i+1]);

}

}

if(a[i]<a[i+1])

{

swap(a[i],a[i+1]);

}

if(a[i]<a[i-1])

{

swap(a[i],a[i-1]);

}

}

for(i=0;i<n;i++)

{

cout<<a[i]<<" ";

}

}

There are two O(n) solutions for this problem that does not require ordering.

- oOZz April 22, 20141. You can find the median in O(n) and then rearrange the elements around the median

2. (Better Solution) If you notice the desired ordering, the even numbered elements are bigger (or equal) than the next element, and the odd numbered elements are less than (or equal) than the next element, of course I am assuming the array is 0 offset.

So, you can iterate the array and swap the elements that doesn't match this arrangements,e.g., swap A[i] and A[i+1], when i is even and A[i] < A[i + 1].