Zig Zag Sequence Hackerrank Solution

What the Problem Actually Asks

You get an array of integers and need to rearrange it into a zigzag pattern where elements alternate between going up and going down. So either every even-indexed element is smaller than its neighbors, or every odd-indexed element is smaller than its neighbors. The standard HackerRank version usually asks you to make it so that a[0] < a[1] > a[2] < a[3] and so on, or the reverse. The classic problem gives you an array and asks you to find the longest zigzag subsequence, or sometimes just rearrange the array into a valid zigzag pattern. There are a few variants floating around, so I will cover the most common one: given an array of n distinct integers, rearrange them so that they form a zigzag pattern with minimum number of swaps or operations. I ran into this on a coding platform a while back. The variant I saw had you output the number of operations needed to make the array zigzag by changing individual elements. Here is the straightforward approach that actually works.

The Pattern and Why It Works

Think about what a zigzag pattern requires locally. At each position i, the relationship with its neighbor should flip. If position i needs to be a peak (greater than both neighbors), then position i+1 must be a valley. You do not need to look at the entire array at once. A greedy pass from left to right is sufficient. For each index i starting at 0, check if the current relationship matches what it should be. If i is even and you want a valley pattern, then a[i] should be less than a[i+1]. If that condition fails, you swap a[i] with a[i+1]. Then move to the next index. This single left-to-right pass fixes everything because each swap only affects the current local relationship and the next one, which will be checked in the following iteration. I used to overcomplicate this by trying to count inversions or use dynamic programming. That was wasteful. The greedy adjacent-swap approach runs in O(n) time and uses O(1) extra space. That is all you need for the rearrangement variant.

Handling the Longest Zigzag Subsequence Variant

Sometimes the problem is different. Instead of rearranging, you need to find the length of the longest zigzag subsequence in a given array. This is the more frequent HackerRank version. The input is fixed and you pick elements to keep while maintaining the alternating up-down pattern. The solution here is a simple linear scan with two variables. Keep track of the length of the longest zigzag subsequence ending at the current position with an upward move, and separately the length ending with a downward move. When you see a[i] > a[i-1], you update the upward length using the previous downward length plus one. When a[i] < a[i-1], you update the downward length similarly. Equal elements break the pattern and you just skip them. Here is what that looks like in code:

def longestZigZag(arr):
    if not arr:
        return 0
    up = 1
    down = 1
    for i in range(1, len(arr)):
        if arr[i] > arr[i-1]:
            up = down + 1
        elif arr[i] arr[i-1]:
            down = up + 1
    return max(up, down)

This runs in O(n) time and O(1) space. No recursion, no memoization table, nothing fancy. On one attempt, the test cases included an array with all identical elements. My first version would return 1, which is technically correct since a subsequence of length 1 is always zigzag. But one platform expected 0 for empty arrays and the code did not handle the empty input guard properly on the rearrangement variant. I lost a couple of points on a submission because I did not check for n == 0 at the top. Another gotcha is the strictness of the comparison. Some problem statements say strictly increasing and decreasing, while others allow equal adjacent values to be treated as valid transitions. Read the problem carefully. If it says strictly, then a[i] == a[i-1] changes nothing. If it allows non-strict, you would update on equality too. I once submitted the wrong version because I assumed strict when the problem allowed equality.

When This Approach Breaks Down

The greedy adjacent-swap method works only when you are allowed to swap adjacent elements or rearrange freely. If the problem restricts you to only changing individual element values (not swapping), then you need a different strategy. In that case, for each position you determine whether it should be a peak or valley and set it to either a large enough value or a small enough value. This usually means setting it to something like the previous element plus or minus one, depending on which direction you need. Also, the O(n) greedy solution does not work if the problem asks for the lexicographically smallest zigzag arrangement. That variant requires sorting the array first and then placing elements in a specific order, which is a separate problem entirely.

Complete Solution Template

For the longest zigzag subsequence problem on HackerRank, the full solution with input reading looks like this:

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    if n == 0:
        print(0)
        return
    up = 1
    down = 1
    for i in range(1, n):
        if arr[i] > arr[i-1]:
            up = down + 1
        elif arr[i] arr[i-1]:
            down = up + 1
    print(max(up, down))

solve()

If the variant requires outputting the rearranged array instead of a count, use the adjacent swap pass:

def zigzagRearrange(arr):
    for i in range(0, len(arr)-1, 2):
        if i % 2 == 0:
            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]
    return arr

Both patterns are simple enough that you do not need to memorize complex algorithms. Just keep the logic clean and handle the edge cases upfront. The platform test suites tend to focus on those edge cases more than anything else.

Summary of What Matters

Identify which variant you are dealing with first. Longest subsequence gets the two-variable O(n) scan. Rearrangement gets the greedy adjacent swap pass. Empty arrays and equal elements are the usual sources of wrong answers. Once you pick the right approach, the code is short and runs well within typical time limits for arrays up to 10^5 elements.