Convert an array into Zig-Zag order

Given an array of distinct integers, the task is to rearrange the elements in a Zig-Zag fashion. An array is in Zig-Zag fashion if the elements are ordered such that the first element is less than the second, the second is greater than the third, and so on. The sequence alternates between less than (**<**) and greater than (**>**).

For example, if the input array is [4, 3, 7, 8, 6, 2, 1], the output should be [3, 7, 4, 8, 2, 6, 1] to achieve the Zig-Zag pattern.

Input/Output Examples

plaintext
Example 1:
Input:
arr = [4, 3, 7, 8, 6, 2, 1]
Output: [3, 7, 4, 8, 2, 6, 1]
Explanation: The elements are rearranged in a Zig-Zag fashion as 3 < 7 > 4 < 8 > 2 < 6 > 1.

Example 2:
Input:
arr = [1, 4, 3, 2]
Output: [1, 4, 2, 3]
Explanation: The array is rearranged to 1 < 4 > 2 < 3.

Approach to convert the array into zig-zag order

  1. Initialize a Flag for Comparison:
    • Start with a flag indicating the required comparison. Begin with True, meaning the first comparison should be <. This indicates that arr[i] < arr[i+1].
  2. Traverse the Array and Swap Elements as Needed:
    • For each element at index i, check if it meets the required condition based on the flag:
      • If flag is True and arr[i] > arr[i+1], swap arr[i] and arr[i+1] to satisfy arr[i] < arr[i+1].
      • If flag is False and arr[i] < arr[i+1], swap arr[i] and arr[i+1] to satisfy arr[i] > arr[i+1].
    • After each comparison, toggle the flag to ensure the next pair satisfies the opposite condition.
  3. Repeat Until the Array is Processed:
    • Continue this process for the entire array, ensuring each pair of elements alternates between < and > according to the Zig-Zag pattern.

C++ Program to convert the array into Zig-Zag order

cpp
#include <iostream>
#include <vector>
using namespace std;

// Function to convert array into Zig-Zag fashion
void zigZagArray(vector<int>& arr) {
    bool flag = true; // Start with "<" comparison

    for (int i = 0; i < arr.size() - 1; i++) {
        if (flag) { // Expecting arr[i] < arr[i+1]
            if (arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
            }
        } else { // Expecting arr[i] > arr[i+1]
            if (arr[i] < arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
            }
        }
        flag = !flag; // Toggle flag for next comparison
    }
}

int main() {
    vector<int> arr = {4, 3, 7, 8, 6, 2, 1};
    zigZagArray(arr);

    cout << "Array in Zig-Zag fashion: ";
    for (int elem : arr) {
        cout << elem << " ";
    }
    cout << endl;

    return 0;
}

Java Program to convert the array into Zig-Zag order

java
import java.util.Arrays;

public class ZigZagArray {

    // Function to convert array into Zig-Zag fashion
    public static void zigZagArray(int[] arr) {
        boolean flag = true; // Start with "<" comparison

        for (int i = 0; i < arr.length - 1; i++) {
            if (flag) { // Expecting arr[i] < arr[i+1]
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            } else { // Expecting arr[i] > arr[i+1]
                if (arr[i] < arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
            flag = !flag; // Toggle flag for next comparison
        }
    }

    public static void main(String[] args) {
        int[] arr = {4, 3, 7, 8, 6, 2, 1};
        zigZagArray(arr);

        System.out.println("Array in Zig-Zag fashion: " + Arrays.toString(arr));
    }
}

Python Program to convert the array into Zig-Zag order

python
# Function to convert array into Zig-Zag fashion
def zig_zag_array(arr):
    flag = True  # Start with "<" comparison

    for i in range(len(arr) - 1):
        if flag:  # Expecting arr[i] < arr[i+1]
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
        else:  # Expecting arr[i] > arr[i+1]
            if arr[i] < arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
        flag = not flag  # Toggle flag for next comparison

# Example usage
if __name__ == "__main__":
    arr = [4, 3, 7, 8, 6, 2, 1]
    zig_zag_array(arr)
    print("Array in Zig-Zag fashion:", arr)

Time Complexity:

  • O(n): The algorithm processes each element of the array once, resulting in linear time complexity.

Space Complexity:

  • O(1): The array is modified in-place, using no extra space.

DSA

2606

544

Related Articles