Python Interview: Convert array into Zig-Zag fashion 

We have added some beginners interview question for Python Programming Language. Once, you are comfortable with easy to achieve guide we will add more advanced interview questions as well.

Let’s crack this interview question together!

Also Check Out our Interview Guide for other languages!

Front-End Prep Guide

Question: Given an array Arr (distinct elements) of size N. Rearrange the elements of array in zig-zag fashion. The converted array should be in form a < b > c < d > e < f. The relative order of elements is same in the output i.e you have to iterate on the original array only.

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 is to complete the function zigZag() which takes the array of integers array and n as parameters and returns void. You need to modify the array itself.
NOTE: In the mentioned complexity, only a unique solution will exist.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Constraints:
1 <= N <= 10⁵
0 <= Arr_i <= 10⁶

Problem Walkthrough

Solution

 
def zigZag(arr, n): 
  
    
    flag = True
  
    for i in range(n - 1): 
  
        # "<" relation expected 
        if flag is True: 
  
            # If we have a situation like 
            # A > B > C, we get A > B < C 
            # by swapping B and C 
            if arr[i] > arr[i + 1]: 
                arr[i], arr[i + 1] = arr[i + 1], arr[i] 
  
            # ">" relation expected 
        else: 
  
            # If we have a situation like 
            # A < B < C, we get A < C > B  
            # by swapping B and C     
            if arr[i] < arr[i + 1]: 
                arr[i], arr[i + 1] = arr[i + 1], arr[i] 
        flag = bool(1 - flag) 
    print(arr) 
  
# Print Output
arr = [4, 3, 7, 8, 6, 2, 1] 
n = len(arr) 
zigZag(arr, n)