*79*

# Zigzag Array in Java

In this section, we are going to discuss **what is a zigzag array** with proper examples. Also, we will create a **Java program to convert a simple or ordinary array into a zigzag array** and vice-versa.

## What is a zigzag array?

An array is said to be a **zigzag array** if there are no three consecutive elements of the array are in either increasing or decreasing order. In other words, we can say if there are three elements (say **a _{i}, a_{i+1}, a_{i+2}**) in the array such that

**a**or

_{i}< a_{i+1}< a_{i+2 }**a**, the array is not a zigzag array.

_{i}> a_{i+1}> a_{i+2}Hence, we can symbolically represent the condition as follows:

Where a, b, c, d, e, and f are the elements of the array.

In short, we can say that array elements must follow less than (<) and greater than (>), order alternatively. Every element is either greater than or less than its neighbors.

### Example of Zigzag Array

The arrays **A = [4, 2, 6, 3, 10, 1]** and **B = [8, 4, 6, 3, 5, 1, 10, 9]** are zigzag arrays. Because no three consecutive elements of the array are in either increasing or decreasing order.

An array **C = [5, 2, 3, 6, 1]** is not a zigzag array because the element a_{1} < a_{2} < a_{3} i.e. (2 < 3 < 6). If we remove the third element i.e. 6, the array becomes [5, 2, 3, 1] that is a zigzag array. Other zigzag arrays are:

The following arrays are not zigzag arrays because the elements (that are in red color) do not follow the order.

The following two approaches can be used:

### Approach 1: Simple Solution

- First, short the given array.
- Fix the first element.
- After that, swap the remaining elements in pairs. It means that swap a[1] and a[2], swap a[3] and a[4], and so on.

For the above approach, the complexity will be **O(n log n)** and the space complexity is **O(1)** because no extra space is required.

### Approach 2: Efficient Solution

The second approach provides an efficient solution by performing the **bubble** short in one pass. It converts the array in the zigzag form in **O(n)** time.

For performing the bubble short, we need to maintain a **flag** that represents the order (less than (<) or greater than (>)). If the two elements are not in that order then swap those two elements, else not.

### Algorithm

- Set the flag to true.
- Traverse over the array from 0 to n-2 (where n is the length of the array).
- Check if the flag is true
- Check if the current element is greater than the next element.
- Swap those values.

- Else, check if the current element is greater than the next element.
- Check if the current element is lesser than the next element.
- Swap those values.

- Check if the flag is true
- Flip the value of the flag.

Let’s see an example.

Consider an array A having three elements A = [5, 3, 1]. Here, 5 > 3 > 1. It means not a zigzag array. Suppose, we are processing 3 and 1 which is 3 > 1. So, if we swap 3 and 1 then the relationship becomes 5 > 1 and 1 < 3 and finally, we get the zigzag array i.e. [5, 1, 3].

## Convert an Ordinary Array into Zigzag Array

Consider an array given below and convert it into a zigzag array.

Initially, the variable flag is set to **false**. In the following steps, a[i] is the current element and a[i+1] is the next element.

**Step 1:** Keep the first element as it is because the first element does not have its left neighbor and we cannot compare it with the previous element.

Here, **flag = false** and **a[i]** i.e. 3 is **less** than **a[i+1]** i.e. 4. So, we will not swap the elements. Increment i by 1 and set the flag variable to **true**.

**Step 2:** Here, **flag = true** and **a[i]** i.e. 4 is **less** than **a[i+1]** i.e. 6. The condition i>i+1 becomes false. So, we will swap the elements (a[i], a[i+1]). Increment i by 1 and set flag to **false**.

**Step 3:** Here, **flag = false** and **a[i]** i.e. 4 is **greater** than **a[i+1]** i.e. 2. The condition i<i+1 becomes false. So, we will swap the elements (a[i], a[i+1]). Increment i by 1 and set flag to **true**.

**Step 4:** Here, **flag = true** and **a[i]** i.e. 4 is **greater** than **a[i+1]** i.e. 1. The condition i<i+1 becomes false. So, we will not swap the elements (a[i], a[i+1]). Increment i by 1 and set flag to **false**.

**Step 5:** Here, **flag = false** and **a[i]** i.e. 1 is **less** than **a[i+1]** i.e. 6. The condition i<i+1 satisfies. So, we will not swap the elements (a[i], a[i+1]). Increment i by 1 and set flag to **true**.

**Step 6:** Here, **flag = true** and **a[i]** i.e. 8 is **less** than **a[i+1]** i.e. 9. The condition i>i+1 becomes false. So, we will swap the elements (a[i], a[i+1]). Set flag to **false**.

In the above example, we observe that the **flag** alternatively becomes **true** and **false**.

Let’s check the array is a zigzag array or not.

The above array is a zigzag array because less-than and greater-than operations are placed alternatively.

Let’s implement the above algorithm in a Java program.

**ZigzagArrayExample.java**

**Output:**

[2, 5, 1, 7, 4, 8, 6]

Let’s see another example.

**ZigzagArrayExample.java**

**Output:**

In order to convert an array into zigzag form, we can also use the following logic:

The above logic also works fine.