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.