In this article, we will see the Zig Zag sequence problem solution in C#.

**Problem**

As per this problean m, you have element
of an integer array ( ex [ 2,6,1,4,7,3,5]), Now we need to rearrange this array of
elements in a zig-zag sequence, which means :

·
The first half of elements (first to the middle) are in increasing order (ex: 1, 2, 3,7).

·
The last half of elements (middle to
last) are in decreasing order (ex: 7, 6, 5,4).

· In other words: elements in increasing order < middle element > elements in decreasing order.

The output of the given array will be

1,2,3,7,6,5,4

Given an
array of **n** distinct integers, transform the array into a zig-zag
sequence by permuting the array elements. A sequence will be called a zig-zag
sequence if the first **k** elements in the sequence are in
increasing order and the last elements are in decreasing order, where **k = (n +1)/2**. You need to find the lexicographically smallest zig-zag sequence of the given array.

**Understanding problem solving**

Let’s understand
the algorithm by looking at input [2,6,1,4,7,3,5].

When we
are going to see a Zigzag sequence (increasing order < middle > decreasing
order), always remember middle element must be the largest element, so as
per the given array 7 is the largest number so the zig-zag array will be

Input: 2,6,1,4,7,3,5

Zig zag: _ _ _ < 7 > _ _

Now we need to find the lexicographically smallest sequence of numbers, which means we need the smallest possible values at the beginning of the array. And they should be to be in increasing order:

`Input:`

2,6,1,4,7,3,5

`Zig zag: 1, 2, 3 < 7 > _ _ _`

After this, we need the largest element at the end of the
array, which means we can swap it to the middle:

`Input:`

2,6,1,4,7,3,5

`Sorted: 1, 2, 3, 4, 5, 6, 7 `

`Swap largest to middle: 1, 2, 3 < 7 > 5, 6, 4`

Finally, the last half of the elements (7, 5, 6, 4)
need to be put in decreasing order (7, 6, 5, 4). The middle (7) and last
element (4) were swapped and are already in the correct positions. We can
reverse the remaining elements (5, 6) to put them in decreasing order (6, 5):

`Input:`

2,6,1,4,7,3,5

Code language: plaintext (plaintext)`Sorted: 1, 2, 3, 4, 5, 6, 7 Swap largest to middle: 1, 2, 3 < 7 > 5, 6, 4 Reverse sort remaining: 1, 2, 3, < 7 > 6, 5, 4`

And that’s the zig-zag sequence: 1, 2, 3, 7, 6,

And that’s the zig-zag sequence: 1, 2, 3, 7, 6, 5, 4.

Here is an example of the algorithm (implemented in C#):

Code language: C# (cs)`public static void zigZagSequesnce() { int[] arr = new int[] { 2, 6, 1, 4, 7, 3, 5 }; int length = arr.Length; int midIndex = length / 2; int lastIndex = length - 1; //Step 1 - Sort Array.Sort(arr); //Step 2 - Swap largest element into the middle int max = arr[lastIndex]; arr[lastIndex] = arr[midIndex]; //7 / 2 = 3.5, 3 arr[midIndex] = max; //Step 3 - Reverse remaining elements int leftIndex = midIndex + 1; int rightIndex = lastIndex - 1; while (leftIndex < rightIndex) { int tmp = arr[leftIndex]; arr[leftIndex] = arr[rightIndex]; arr[rightIndex] = tmp; leftIndex++; rightIndex--; } Console.WriteLine(string.Join(",", arr)); Console.ReadLine(); }`

The outputs are the zig-zag sequence:

**1,2,3,7,6,5,4**

----------------------------------------------------------------------------------------

EmoticonEmoticon