HackerRank – Zig Zag Sequence solution

In this article, I’ll explain the Zig Zag Sequence algorithm problem on HackerRank.

Problem statement: You’re given an integer array with an odd number of elements (ex: [5, 2, 3, 1, 4]). You need to re-arrange the elements so they’re in a zig zag sequence, which means:

• The first half of elements (first to middle) are in increasing order (ex: 1, 2, 5).
• The last half of elements (middle to last) are in decreasing order (ex: 5, 4, 3).
• In other words: elements in increasing order < middle element > elements in decreasing order.

Here’s a diagram to help you visualize what a zig zag sequence looks like:

Furthermore, since there can be more than one valid zig zag sequence (ex: [1, 4, 5, 3, 2]), you need to return the lexicographically smallest one. In this example, [1, 2, 5, 4, 3] < [1, 4, 5, 3, 2] lexicographically, which is why [1, 2, 5, 4, 3] is the answer.

Note: For the actual problem in HackerRank, you have to fix a buggy implementation of this algorithm. In order to fix it, you have to know how it should be implemented, which I’ll explain here.

Approach

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

By definition of the zig zag sequence (increasing order < middle > decreasing order), notice that the middle element must the largest element. So we have:

Input: 7, 2, 5, 4, 3, 6, 1
Zig zag: _ _ _ < 7 > _ _ _Code language: plaintext (plaintext)

Second, because we need to find the lexicographically smallest sequence, this means we should put the smallest possible values at the beginning of the array. And they need to be in increasing order:

Input: 7, 2, 5, 4, 3, 6, 1
Zig zag: 1, 2, 3 < 7 > _ _ _ Code language: plaintext (plaintext)

The most efficient way to get to this point is to sort the input array in increasing order. After this, we know the largest element is at the end of the array, which means we can swap it to the middle:

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

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: 7, 2, 5, 4, 3, 6, 1
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, 4Code language: plaintext (plaintext)

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

This can be expressed in pseudocode like this:

given: int[] input

mid = input.Length / 2
last = input.Length - 1

//step 1 - sort in increasing order
sort(input)

//step 2 - put largest in middle
swap(input[mid], input[last])

//step 3 - reverse remaining elements
left = mid + 1
right = last - 1

loop while left < right
	swap(input[left], input[right])

	left++
	right--

return inputCode language: plaintext (plaintext)

Note: Swapping the largest element to the middle could’ve been done in the loop too (from mid to last). Technically, it’s not a special case. However, treating it like it’s special makes the algorithm easier to understand.

Since we know the array always has an odd length, and arrays start at 0, we can get the middle index by doing integer division (it chops off decimals). Hence, Length / 2 is the middle index.

Code

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

int[] arr = new int[] { 7, 2, 5, 4, 3, 6, 1 };
int n = arr.Length;
int midIndex = n / 2;
int lastIndex = n - 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));
Code language: C# (cs)

This outputs the zig zag sequence:

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