Given an array arr of distinct elements of size N, the task is to rearrange the elements of the array in a zig-zag fashion so that the converted array should be in the below form: 
arr[0] < arr[1]  > arr[2] < arr[3] > arr[4] < . . . . arr[n-2] < arr[n-1] > arr[n]. 
NOTE: If your transformation is correct, the output will be 1 else the output will be 0. 
Example 1:
Input:
N = 7
Arr[] = {4, 3, 7, 8, 6, 2, 1}
Output: 3 7 4 8 2 6 1
Explanation: 3 < 7 > 4 < 8 > 2 < 6 > 1
Example 2:
Input:
N = 4
Arr[] = {1, 4, 3, 2}
Output: 1 4 2 3
Explanation: 1 < 4 > 2 < 3
Your Task:
You don't need to read input or print anything. Your task is to complete the function zigZag() which takes the array of integers arr and n as parameters and returns void. You need to modify the array itself.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{6}
0 <= Arr_{i} <= 10^{9}

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3





class Solution:

    # Program for zig-zag conversion of array

    def zigZag(self, arr, n):

Solutions:
class Solution:

	def zigZag(self, arr, n):
		for i in range(1, n):
			a = arr[i]
			b = arr[i - 1]
			if i % 2 == 1 and b > a:
				t = a
				arr[i] = b
				arr[i - 1] = t
			elif i % 2 == 0 and b < a:
				t = a
				arr[i] = b
				arr[i - 1] = t
		return arr


class Solution:

	def zigZag(self, arr, n):
		flag = 1
		for i in range(n - 1):
			if flag == 1:
				if arr[i] > arr[i + 1]:
					(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
				flag = 0
			elif flag == 0:
				if arr[i] < arr[i + 1]:
					(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
				flag = 1


class Solution:

	def zigZag(self, arr, n):
		for i in range(1, n, 2):
			if arr[i] < arr[i - 1]:
				(arr[i], arr[i - 1]) = (arr[i - 1], arr[i])
			if i < n - 1 and arr[i] < arr[i + 1]:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])


class Solution:

	def zigZag(self, arr, n):
		for i in range(1, n):
			if i % 2 == 0:
				if arr[i] > arr[i - 1]:
					(arr[i], arr[i - 1]) = (arr[i - 1], arr[i])
			elif arr[i] < arr[i - 1]:
				(arr[i], arr[i - 1]) = (arr[i - 1], arr[i])
		return arr


class Solution:

	def zigZag(self, arr, n):
		flag = True
		for i in range(n - 1):
			if flag:
				if arr[i] > arr[i + 1]:
					(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			elif arr[i] < arr[i + 1]:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			flag = not flag


class Solution:

	def zigZag(self, arr, n):
		flag = True
		for i in range(n):
			if i == n - 1:
				break
			ar1 = arr[i]
			ar2 = arr[i + 1]
			if flag == True and ar1 > ar2:
				arr[i] = ar2
				arr[i + 1] = ar1
			elif flag == False and ar1 < ar2:
				arr[i] = ar2
				arr[i + 1] = ar1
			flag = not flag


class Solution:

	def zigZag(self, arr, n):

		def bubble(a, n):
			flag = 1
			for i in range(n - 1):
				j = i + 1
				if flag:
					if a[i] > a[j]:
						(a[i], a[j]) = (a[j], a[i])
				elif a[i] < a[j]:
					(a[i], a[j]) = (a[j], a[i])
				flag = not flag
			return a
		arr = bubble(arr, n)
		return


class Solution:

	def zigZag(self, arr, n):
		(min, max, j) = (arr[0], arr[0], 0)
		for i in range(1, n):
			if j % 2 == 0:
				arr[j] = min if min < arr[i] else arr[i]
				max = min if min > arr[i] else arr[i]
				j += 1
			else:
				arr[j] = max if max > arr[i] else arr[i]
				min = max if max < arr[i] else arr[i]
				j += 1


class Solution:

	def zigZag(self, arr, n):
		for i in range(len(arr) - 1):
			if i % 2 == 0:
				if arr[i] > arr[i + 1]:
					(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
				else:
					continue
			elif arr[i] < arr[i + 1]:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			else:
				continue


class Solution:

	def zigZag(self, arr, n):
		flag = True
		for i in range(n - 1):
			if flag and arr[i] >= arr[i + 1] or (not flag and arr[i] <= arr[i + 1]):
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			flag = not flag
		return 1


class Solution:

	def zigZag(self, arr, n):
		for i in range(len(arr) - 1):
			if (i % 2 == 0) != (arr[i] < arr[i + 1]):
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])


class Solution:

	def zigZag(self, arr, n):
		for v in range(1, len(arr), 2):
			if arr[v] < arr[v - 1]:
				(arr[v], arr[v - 1]) = (arr[v - 1], arr[v])
			if v != n - 1 and arr[v] < arr[v + 1]:
				(arr[v], arr[v + 1]) = (arr[v + 1], arr[v])
		return


class Solution:

	def zigZag(self, arr, n):
		v = True
		for i in range(n - 1):
			if v:
				if arr[i] > arr[i + 1]:
					(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			elif arr[i] < arr[i + 1]:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			v = not v
		return arr


class Solution:

	def zigZag(self, arr, n):
		click = 0
		for i in range(n - 1):
			if click == 1:
				if arr[i] < arr[i + 1]:
					(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
				click = 0
			elif click == 0:
				if arr[i] > arr[i + 1] and i != n - 1:
					(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
				click = 1
		return arr


class Solution:

	def zigZag(self, arr, n):
		e = True
		for i in range(0, len(arr) - 1):
			if e:
				if arr[i] > arr[i + 1]:
					(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			elif arr[i] < arr[i + 1]:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			e = not e


class Solution:

	def zigZag(self, arr, n):
		less_than = True
		for i in range(n - 1):
			if less_than:
				if arr[i] > arr[i + 1]:
					(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
				less_than = False
			else:
				if arr[i] < arr[i + 1]:
					(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
				less_than = True


class Solution:

	def zigZag(self, arr, n):
		k = True
		for i in range(n - 1):
			if k == True:
				if arr[i] > arr[i + 1]:
					x = arr[i]
					arr[i] = arr[i + 1]
					arr[i + 1] = x
				else:
					pass
				k = False
			else:
				if arr[i] < arr[i + 1]:
					x = arr[i]
					arr[i] = arr[i + 1]
					arr[i + 1] = x
				else:
					pass
				k = True


class Solution:

	def zigZag(self, arr, n):
		x = 1
		for i in range(1, n):
			if x:
				if arr[i - 1] > arr[i]:
					(arr[i - 1], arr[i]) = (arr[i], arr[i - 1])
				x = 0
			else:
				if arr[i - 1] < arr[i]:
					(arr[i - 1], arr[i]) = (arr[i], arr[i - 1])
				x = 1
		return arr


class Solution:

	def zigZag(self, arr, n):
		i = 0
		j = 1
		while j < n:
			if j % 2 == 0:
				if arr[i] < arr[j]:
					(arr[i], arr[j]) = (arr[j], arr[i])
			elif arr[i] > arr[j]:
				(arr[i], arr[j]) = (arr[j], arr[i])
			i += 1
			j += 1


class Solution:

	def zigZag(self, arr, n):
		i = 1
		while i < n:
			if arr[i] < arr[i - 1]:
				(arr[i - 1], arr[i]) = (arr[i], arr[i - 1])
			if i != n - 1 and arr[i] < arr[i + 1]:
				(arr[i + 1], arr[i]) = (arr[i], arr[i + 1])
			i += 2
		return arr


class Solution:

	def zigZag(self, arr, n):
		f = 1
		for i in range(n - 1):
			if f:
				if arr[i] > arr[i + 1]:
					(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			elif arr[i] < arr[i + 1]:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			f = f ^ 1


class Solution:

	def zigZag(self, arr, n):
		L = len(arr)
		for i in range(0, L - 1, 2):
			if i < L - 1 and arr[i] > arr[i + 1]:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			if i < L - 2 and arr[i + 1] < arr[i + 2]:
				(arr[i + 1], arr[i + 2]) = (arr[i + 2], arr[i + 1])
		return arr


class Solution:

	def zigZag(self, a, n):
		for i in range(1, n):
			cond = a[i] < a[i - 1] if i % 2 != 0 else a[i] > a[i - 1]
			if cond:
				(a[i], a[i - 1]) = (a[i - 1], a[i])
		return a