Convert Array into Zig-Zag Fashion: A Comprehensive Guide

Creating a zig-zag array from a given array is a common problem in computer science and algorithm design. In a zig-zag fashion, the elements of the array are arranged in an alternating order of smaller and larger elements. Specifically, for an array arr, it should satisfy the condition: arr[0] < arr[1] > arr[2] < arr[3] > arr[4] < .... This pattern is often visualized as a zig-zag line when plotted.

For example, if we have an input array [4, 3, 7, 8, 6, 2, 1], a possible zig-zag conversion would be [3, 7, 4, 8, 2, 6, 1]. Notice how the elements follow the zig-zag pattern: 3 < 7, 7 > 4, 4 < 8, 8 > 2, 2 < 6, 6 > 1. There might be multiple valid zig-zag arrangements for a given input array, as long as they adhere to the zig-zag condition.

Let’s explore two common approaches to convert an array into zig-zag fashion: a naive approach using sorting and an efficient linear time approach.

Naive Approach: Leveraging Sorting for Zig-Zag Conversion

One straightforward method to achieve a zig-zag array is to utilize sorting. The core idea is to first sort the input array and then strategically swap adjacent elements to enforce the zig-zag pattern.

Algorithm:

1. Sort the array: Begin by sorting the given array in ascending order. This step ensures that we have the elements in a predictable order, making it easier to arrange them in a zig-zag manner.
2. Swap adjacent elements: Iterate through the sorted array, starting from the second element (index 1) and incrementing by 2 in each step. In each iteration, swap the current element with the next adjacent element. This swapping process effectively places the larger elements at the “peak” positions of the zig-zag pattern and smaller elements in the “valley” positions.

Code Implementation:

Here are code implementations of the naive approach in various popular programming languages:

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void zigZag(vector<int>& arr, int N) {
    sort(arr.begin(), arr.end());
    for (int i = 1; i < N - 1; i += 2) {
        swap(arr[i], arr[i + 1]);
    }
    for (int i = 0; i < N; i++) {
        cout << arr[i] << " ";
    }
}

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

C

#include <stdio.h>
#include <stdlib.h>

int comparator(const void *p, const void *q) {
    return (*(int *)p - *(int *)q);
}

void zigZag(int arr[], int N) {
    qsort((void *)arr, N, sizeof(arr[0]), comparator);
    for (int i = 1; i < N - 1; i += 2) {
        int temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
    }
    for (int i = 0; i < N; i++)
        printf("%d ", arr[i]);
}

int main() {
    int arr[] = {2, 3, 4, 1, 5, 7, 6};
    int N = 7;
    zigZag(arr, N);
    return 0;
}

Java

import java.util.Arrays;

class Test {
    static int arr[] = new int[] { 4, 3, 7, 8, 6, 2, 1 };

    static void zigZag() {
        Arrays.sort(arr);
        for (int i = 1; i < arr.length - 1; i += 2) {
            int temp = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = temp;
        }
    }

    public static void main(String[] args) {
        zigZag();
        System.out.println(Arrays.toString(arr));
    }
}

Python

def zigZag(arr, n):
    arr.sort()
    for i in range(1, n - 1, 2):
        arr[i], arr[i + 1] = arr[i + 1], arr[i]
    print(arr)

if __name__ == "__main__":
    arr = [4, 3, 7, 8, 6, 2, 1]
    n = len(arr)
    zigZag(arr, n)

C#

using System;

class GFG{
    static int[] arr = new int[] { 4, 3, 7, 8, 6, 2, 1 };

    static void zigZag() {
        Array.Sort(arr);
        for (int i = 1; i < arr.Length - 2; i += 2) {
            int temp = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = temp;
        }
    }

    public static void Main(String[] args) {
        zigZag();
        foreach (int i in arr)
            Console.Write(i + " ");
    }
}

JavaScript

function zigZag(arr, n) {
    arr.sort();
    for (let i = 1; i < n - 2; i++) {
        let temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
    }
}

let arr = [4, 3, 7, 8, 6, 2, 1];
let n = arr.length;
zigZag(arr, n);
for (let i = 0; i < n; i++)
    document.write(arr[i] + " ");

This image shows a code snippet in C++ demonstrating the naive approach to convert an array into zig-zag fashion using sorting and swapping.

Time and Space Complexity:

• Time Complexity: O(N*log(N)) due to the sorting step, which is the dominant factor in the time complexity. The swapping step takes linear time, O(N), but it’s overshadowed by the sorting complexity.
• Space Complexity: O(1) as the sorting is typically done in-place, and we only use a constant amount of extra space for variables.

Efficient Approach: Linear Time Zig-Zag Rearrangement using Triplets

While the sorting approach is simple to understand and implement, it’s not the most efficient solution. A more optimized method achieves zig-zag conversion in linear time, O(N). This approach leverages the triplet relationship inherent in the zig-zag pattern: arr[i-1] < arr[i] > arr[i+1] or arr[i-1] > arr[i] < arr[i+1].

Algorithm:

The core idea of this efficient approach is to iterate through the array and, for each triplet of elements (considering the current element and its immediate neighbors), ensure that the middle element satisfies the zig-zag condition.

1. Initialize a flag: Introduce a boolean flag variable, say flag, and set it to true. This flag will help us alternate between expecting a “<” relationship and a “>” relationship in the zig-zag pattern. true indicates we expect arr[i] < arr[i+1], and false indicates we expect arr[i] > arr[i+1].
2. Iterate through the array: Traverse the array from the first element up to the second-to-last element (index n-2).
3. Check and swap based on the flag: In each iteration i:
   • If flag is true (expecting arr[i] < arr[i+1]):
     • If arr[i] > arr[i+1], swap arr[i] and arr[i+1] to satisfy the “<” condition.
   • If flag is false (expecting arr[i] > arr[i+1]):
     • If arr[i] < arr[i+1], swap arr[i] and arr[i+1] to satisfy the “>” condition.
4. Flip the flag: After each comparison and potential swap, flip the value of the flag (flag = !flag). This ensures that the relationship expectation alternates between “<” and “>” for subsequent elements, creating the zig-zag pattern.

Code Implementation:

Here are code implementations of the efficient approach in different languages:

C++

#include <iostream>

using namespace std;

void zigZag(int arr[], int n) {
    bool flag = true;
    for (int i = 0; i <= n - 2; i++) {
        if (flag) {
            if (arr[i] > arr[i + 1])
                swap(arr[i], arr[i + 1]);
        } else {
            if (arr[i] < arr[i + 1])
                swap(arr[i], arr[i + 1]);
        }
        flag = !flag;
    }
}

int main() {
    int arr[] = {4, 3, 7, 8, 6, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    zigZag(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

C

#include <stdio.h>
#include <stdbool.h>

void swap(int *xp, int *yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

void zigZag(int arr[], int n) {
    bool flag = true;
    for (int i = 0; i <= n - 2; i++) {
        if (flag) {
            if (arr[i] > arr[i + 1])
                swap(&arr[i], &arr[i + 1]);
        } else {
            if (arr[i] < arr[i + 1])
                swap(&arr[i], &arr[i + 1]);
        }
        flag = !flag;
    }
}

int main() {
    int arr[] = {4, 3, 7, 8, 6, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    zigZag(arr, n);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

Java

import java.util.Arrays;

class Test {
    static int arr[] = new int[] { 4, 3, 7, 8, 6, 2, 1 };

    static void zigZag() {
        boolean flag = true;
        int temp = 0;
        for (int i = 0; i <= arr.length - 2; i++) {
            if (flag) {
                if (arr[i] > arr[i + 1]) {
                    temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            } else {
                if (arr[i] < arr[i + 1]) {
                    temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
            flag = !flag;
        }
    }

    public static void main(String[] args) {
        zigZag();
        System.out.println(Arrays.toString(arr));
    }
}

Python

def zigZag(arr, n):
    flag = True
    for i in range(n - 1):
        if flag is True:
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
        else:
            if arr[i] < arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
        flag = bool(1 - flag)
    print(arr)

arr = [4, 3, 7, 8, 6, 2, 1]
n = len(arr)
zigZag(arr, n)

C#

using System;

class GFG{
    static int[] arr = new int[] { 4, 3, 7, 8, 6, 2, 1 };

    static void zigZag() {
        bool flag = true;
        int temp = 0;
        for (int i = 0; i <= arr.Length - 2; i++) {
            if (flag) {
                if (arr[i] > arr[i + 1]) {
                    temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
            else {
                if (arr[i] < arr[i + 1]) {
                    temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
            flag = !flag;
        }
    }

    public static void Main(String[] args) {
        zigZag();
        foreach (int i in arr)
            Console.Write(i + " ");
    }
}

JavaScript

function zigZag(arr, n) {
    let flag = true;
    for (let i = 0; i <= n - 2; i++) {
        if (flag) {
            if (arr[i] > arr[i + 1]) {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
        else {
            if (arr[i] < arr[i + 1]) {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
        flag = !flag;
    }
}

let arr = [4, 3, 7, 8, 6, 2, 1];
let n = arr.length;
zigZag(arr, n);
for (let i = 0; i < n; i++)
    document.write(arr[i] + " ");

This image showcases a Java code example illustrating the efficient linear time algorithm for converting an array into a zig-zag pattern.

Time and Space Complexity:

• Time Complexity: O(N) because we iterate through the array once. The comparisons and swaps within the loop take constant time.
• Space Complexity: O(1) as we are using a constant amount of extra space for variables like the flag and temporary variables for swapping.

Choosing the Right Approach

Both the naive sorting approach and the efficient linear time approach successfully convert an array into zig-zag fashion. However, the choice between them depends on the specific needs of your application:

• Naive Approach (Sorting):

  • Simpler to understand and implement, especially for beginners.
  • Suitable for smaller arrays where the O(N*log(N)) time complexity is acceptable.
  • Might be preferred when code readability and ease of maintenance are prioritized over absolute performance for moderately sized inputs.

• Efficient Approach (Linear Time):

  • Offers optimal time complexity of O(N), making it significantly faster for larger arrays.
  • Slightly more intricate logic compared to the sorting approach.
  • The preferred choice when performance is critical, especially when dealing with large datasets or in time-sensitive applications.

In scenarios where performance is paramount or when working with large arrays, the linear time approach is undoubtedly the better option. However, for smaller arrays or situations where simplicity is favored, the sorting-based naive approach remains a viable and understandable solution to convert an array into zig-zag fashion.