Convert Array to Zigzag Pattern: O(n) Algorithm Explained

Converting an array to zigzag fashion means rearranging its elements so every even-indexed position holds a local minimum and every odd-indexed position holds a local maximum.

That is the full constraint. The problem is not asking you to sort the array or produce the lexicographically smallest result. It is asking for any arrangement where the alternating less-than and greater-than relationships hold across every adjacent pair.

What the Zigzag Constraint Means

The formal constraint is: `arr[0] < arr[1] > arr[2] < arr[3] > arr[4]` and so on to the last element. In prose: even-indexed elements must be smaller than their right neighbor, and odd-indexed elements must be larger than their right neighbor.

Two things are worth fixing in your mental model before looking at the algorithm.

First, “zigzag” does not mean the array oscillates around a sorted median. It means each pair of adjacent elements satisfies a simple directional rule. The output is not unique: for the input [4, 3, 7, 8, 6, 2, 1], both [3, 7, 4, 8, 2, 6, 1] and [3, 8, 4, 7, 2, 6, 1] are valid zigzag arrangements. The algorithm below produces one of them.

Second, the constraint is local, not global. `arr[0] < arr[1]` tells you nothing about how arr[0] compares to arr[3]. Only adjacent pairs matter. That locality is precisely why the O(n) single-pass approach works.

This type of problem shows up in placement test coding rounds. A campus placement evaluation test may include array rearrangement problems to test whether a candidate can recognise when a greedy local decision is globally valid.

The O(n) Single-Pass Algorithm

The key observation: if you walk through the array from left to right and fix each pair as you encounter it, fixing one pair cannot break any previously fixed pair.

The algorithm, in Python:

def zigzag(arr):
    n = len(arr)
    for i in range(n - 1):          # n-1 iterations, not n
        if i % 2 == 0:              # even index: arr[i] must be less than arr[i+1]
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
        else:                        # odd index: arr[i] must be greater than arr[i+1]
            if arr[i] < arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
    return arr

Three details to note in the code:

• Loop bound is range(n - 1). The loop accesses arr[i + 1], so the last safe index is n - 2. Using range(n) causes an IndexError at i = n - 1.
• Parity check is i % 2 == 0. Even-indexed elements should be local minima. Odd-indexed elements should be local maxima. Getting this backwards produces an array where every constraint is violated.
• Swap is conditional. The relationship is only wrong when the current pair is out of order for its expected direction. If the pair already satisfies the constraint, no swap happens.

Time complexity: O(n). Space complexity: O(1). The algorithm is in-place.

For more practice problems at this difficulty level, the time and work quantitative aptitude article covers a different problem category in the same aptitude-quants cluster.

Step-by-Step Trace on Both Sample Inputs

Sample Input 1

Input: [4, 3, 7, 8, 6, 2, 1] (n = 7, loop runs i = 0 to 5)

• Start: [4, 3, 7, 8, 6, 2, 1]
• i=0 (even): arr[0]=4 > arr[1]=3 — violation, swap → [3, 4, 7, 8, 6, 2, 1]
• i=1 (odd): arr[1]=4 < arr[2]=7 — violation, swap → [3, 7, 4, 8, 6, 2, 1]
• i=2 (even): arr[2]=4 < arr[3]=8 — no violation, no swap → [3, 7, 4, 8, 6, 2, 1]
• i=3 (odd): arr[3]=8 > arr[4]=6 — no violation, no swap → [3, 7, 4, 8, 6, 2, 1]
• i=4 (even): arr[4]=6 > arr[5]=2 — violation, swap → [3, 7, 4, 8, 2, 6, 1]
• i=5 (odd): arr[5]=6 > arr[6]=1 — no violation, no swap → [3, 7, 4, 8, 2, 6, 1]
• Result: [3, 7, 4, 8, 2, 6, 1]
• Verify: 3 < 7 ✓, 7 > 4 ✓, 4 < 8 ✓, 8 > 2 ✓, 2 < 6 ✓, 6 > 1 ✓

This matches the expected output in the problem statement.

Sample Input 2

Input: [1, 4, 3, 2] (n = 4, loop runs i = 0 to 2)

• Start: [1, 4, 3, 2]
• i=0 (even): arr[0]=1 < arr[1]=4 — no violation, no swap → [1, 4, 3, 2]
• i=1 (odd): arr[1]=4 > arr[2]=3 — no violation, no swap → [1, 4, 3, 2]
• i=2 (even): arr[2]=3 > arr[3]=2 — violation, swap → [1, 4, 2, 3]
• Result: [1, 4, 2, 3]
• Verify: 1 < 4 ✓, 4 > 2 ✓, 2 < 3 ✓

Both test cases match. The algorithm is verified correct on the sample inputs.

Why a Local Swap Preserves Prior Relationships

This is the non-obvious part of the algorithm. Why does fixing pair (i, i+1) not undo the fix we made at pair (i-1, i)?

Work through it for two cases.

Case: i is even. We swap only when arr[i] > arr[i+1]. After the swap, new arr[i] equals old arr[i+1], which is smaller than old arr[i]. The previous step (at i-1, which is odd) established that arr[i-1] > arr[i]. After our swap, arr[i] just got smaller, so arr[i-1] > new arr[i] is still true. The relationship at i-1 holds, and it holds more strongly than before.

Case: i is odd. We swap only when arr[i] < arr[i+1]. After the swap, new arr[i] equals old arr[i+1], which is larger than old arr[i]. The previous step (at i-1, which is even) established that arr[i-1] < arr[i]. After our swap, arr[i] just got larger, so arr[i-1] < new arr[i] is still true. Again, the relationship holds more strongly.

In both cases, a corrective swap at i makes the existing relationship at i-1 stricter, not weaker. That is why one pass is sufficient: each fix is additive, not destructive.

This is sometimes called a greedy-local argument. GeeksforGeeks documents the same proof sketch, and Wiggle Sort is a closely related variant that follows the same reasoning.

Three Common Implementation Errors

Error 1: Wrong direction at even indices. Some practice articles initialise a direction flag as flag = False (meaning “expect a decrease”) and apply it at i=0. But i=0 is even, so the correct expectation at i=0 is arr[0] < arr[1] (an increase). Starting with the wrong flag flips every comparison and produces a valid zigzag of the wrong type (one that starts with arr[0] > arr[1]). The fix is to tie the direction to index parity (i % 2) rather than a flag variable. Flags introduce an extra state that can be initialised or toggled incorrectly.

Error 2: Loop bound of range(n) instead of range(n - 1). The algorithm accesses arr[i + 1]. At i = n - 1, arr[n] does not exist. Python raises an IndexError. The loop must stop at n - 2, which range(n - 1) provides. This is the most common single-line bug in implementations reproduced without verification.

Error 3: Off-by-one confusion specific to odd-length arrays. For an array of length 7 (indices 0 through 6), the last iteration should be at i = 5, checking the pair (5, 6). A loop using range(n) goes up to i = 6, which tries to access arr[7]. Some implementations try to guard against this with if i + 1 < n: ... inside the loop, which works, but misses the cleaner fix: just use range(n - 1) and eliminate the guard entirely.

For placement drives that include algorithm-heavy coding rounds, D.E. Shaw’s campus recruitment process is a useful reference. Knowing which rounds test in-place array manipulation versus dynamic programming shifts how you allocate preparation time.

The best books for placement preparation article covers resources that include in-place array problems at varying difficulty levels, from introductory to product-company competitive.

---

The O(n) single-pass approach works because fixing a pair at position i tightens the constraint at i-1, never relaxes it. Language models generate tokens on the same no-backtrack principle: each output token is conditioned on the full prior sequence and committed to without revision. Experimenting with that sequential process hands-on is what TinkerLLM is for, at ₹299 for a month’s access.