**13**

*Jul*

*2018*

### Convert an Array into Zig-Zag Fashion

You are given an array of some distinct elements, you have to rearrange those elements of the array in a zig-zag fashion. The resultant array should be in format a < b > c < d > e < f.

First, we will solve this problem in nlogn Time complexity. in this scenario, we will first sort the Array and then will apply the zig-zap logic.

```
import java.util.Arrays;
public class ZigZagArray {
public static void main(String[] args) {
//nlong approach
int[] arr = new int[] {4, 3, 7, 8, 6, 2, 1};
//Sort the array
Arrays.sort(arr);
//Swap elements in pair skipping first element
for(int i=1;i<arr.length-1;i+=2) {
int temp = arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
}
StringBuilder str = new StringBuilder();
for(int i=0;i<arr.length;i++) {
str.append(arr[i]).append(' ');
}
System.out.print(str);
}
}
```

The time complexity of the above solution is O(nlogn) for sorting the array using quick sort.

Now We will Optimize our solution for O(n) time complexity.

```
import java.util.Arrays;
public class ZigZagArray {
public static void main(String[] args) {
//O(n) approach
int[] arr = new int[] {4, 3, 7, 8, 6, 2, 1};
//flag to keep track of swapping order, i.e either increasing or decrasing order logic
Boolean isGreaterOrder = true;
//Swap elements in in alternate order
for(int i=0;i<arr.length-1;i++) {
//if it is increasing order
if(isGreaterOrder) {
if(arr[i]<arr[i+1]) {
int temp = arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
}
isGreaterOrder = !isGreaterOrder;
}
else {
if(arr[i]>arr[i+1]) {
int temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
}
isGreaterOrder = !isGreaterOrder;
}
}
StringBuilder str = new StringBuilder();
for(int i=0;i<arr.length;i++) {
str.append(arr[i]).append(' ');
}
System.out.print(str);
}
}
```

The Time complexity of the above solution is O(n) as we are iterating through the Array only once.