Print an Array in Zigzag Order in Python

Rearranging an array into zigzag order means every element at an even index is less than its right neighbour, and every element at an odd index is greater. This O(n) pattern appears regularly in CRT coding rounds at Tier-2 and Tier-3 engineering colleges and tests conditional swapping with index parity.

This article covers the exact condition definition, the single-pass swap algorithm with a correctness explanation, a Python implementation, step-by-step traces of two test cases verified from first principles, and the edge cases interviewers include.

The Zigzag Condition

A list arr satisfies the zigzag property when every adjacent pair alternates direction:

• At every even index i: arr[i] < arr[i+1]
• At every odd index i: arr[i] > arr[i+1]

Written as a sequence: arr[0] < arr[1] > arr[2] < arr[3] > arr[4] < arr[5] > arr[6].

The condition governs adjacent pairs, not the global order. Most inputs have several valid zigzag arrangements. The algorithm below finds one of them without guaranteeing lexicographic minimality. Python’s comparison operators (< and >) apply directly to integer list elements with no conversion required.

The Single-Pass Algorithm

The algorithm iterates from index 0 to n-2 and checks one adjacent pair per step:

• At even index i: if arr[i] > arr[i+1], swap.
• At odd index i: if arr[i] < arr[i+1], swap.

One pass is sufficient. A swap at position i makes arr[i] smaller (even case) or larger (odd case). That directional change reinforces the already-satisfied condition at i-1 rather than invalidating it. No backtracking is needed.

Property	Value
Time complexity	O(n)
Space complexity	O(1)
Array passes	1
Modifies original	Yes (in-place)

A sort-then-interleave approach also produces a valid zigzag but costs O(n log n). The direct swap approach is what assessors expect when they want the optimal solution.

Python Implementation

def zigzag_array(arr):
    """
    Rearrange arr in zigzag order: arr[0] < arr[1] > arr[2] < arr[3] ...
    Modifies the list in-place and returns it.
    """
    n = len(arr)
    for i in range(n - 1):
        if i % 2 == 0:           # even index: enforce arr[i] < arr[i+1]
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
        else:                    # odd index: enforce arr[i] > arr[i+1]
            if arr[i] < arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
    return arr


# Example usage
print(zigzag_array([4, 3, 7, 8, 6, 2, 1]))  # [3, 7, 4, 8, 2, 6, 1]
print(zigzag_array([1, 4, 3, 2]))            # [1, 4, 2, 3]

The tuple assignment arr[i], arr[i+1] = arr[i+1], arr[i] is idiomatic Python. The right-hand side is evaluated fully before any assignment occurs, so no temporary variable is needed. See Python’s list documentation for background on in-place list operations.

Tracing Through Two Examples

Both traces verified from first principles.

Example 1: [4, 3, 7, 8, 6, 2, 1]

• i=0 (even): 4 > 3 is True, swap → [3, 4, 7, 8, 6, 2, 1]
• i=1 (odd): 4 < 7 is True, swap → [3, 7, 4, 8, 6, 2, 1]
• i=2 (even): 4 > 8 is False, no swap
• i=3 (odd): 8 < 6 is False, no swap
• i=4 (even): 6 > 2 is True, swap → [3, 7, 4, 8, 2, 6, 1]
• i=5 (odd): 6 < 1 is False, no swap
• Output: [3, 7, 4, 8, 2, 6, 1]
• Verify: 3 < 7, 7 > 4, 4 < 8, 8 > 2, 2 < 6, 6 > 1. All six conditions hold.

Example 2: [1, 4, 3, 2]

• i=0 (even): 1 > 4 is False, no swap
• i=1 (odd): 4 < 3 is False, no swap
• i=2 (even): 3 > 2 is True, swap → [1, 4, 2, 3]
• Output: [1, 4, 2, 3]
• Verify: 1 < 4, 4 > 2, 2 < 3. All three conditions hold.

Edge Cases Worth Testing

Before submitting in a placement assessment, run the function against these inputs:

Empty list and single element

• zigzag_array([]) returns []. With n=0, range(n-1) is range(-1), which produces zero iterations.
• zigzag_array([5]) returns [5]. With n=1, range(0) produces zero iterations.

Both are trivially valid: no adjacent pairs means no conditions to check.

Two elements

• zigzag_array([9, 3]): at i=0 (even), 9 > 3 is True, swap → [3, 9].
• zigzag_array([3, 9]): at i=0 (even), 3 > 9 is False, no swap → [3, 9].

Both outputs satisfy arr[0] < arr[1]. The two-element case is correct by the algorithm.

All equal elements

• zigzag_array([4, 4, 4, 4]) returns [4, 4, 4, 4]. Neither 4 > 4 nor 4 < 4 is True, so no swaps occur.
• The output is unchanged and does not satisfy the strict zigzag property: 4 < 4 is False.

If the problem statement allows weak inequalities (<= and >=), the algorithm is still valid. For strict inequality requirements, an all-equal array has no valid zigzag and the problem is typically stated with distinct elements to avoid this case.

Already-sorted ascending input

• zigzag_array([1, 2, 3, 4, 5]):
  • i=0 (even): 1 > 2 is False, no swap
  • i=1 (odd): 2 < 3 is True, swap → [1, 3, 2, 4, 5]
  • i=2 (even): 2 > 4 is False, no swap
  • i=3 (odd): 4 < 5 is True, swap → [1, 3, 2, 5, 4]
  • Output: [1, 3, 2, 5, 4]
  • Verify: 1 < 3, 3 > 2, 2 < 5, 5 > 4. All conditions hold.

Where This Pattern Appears in Placement Tests

CRT rounds at engineering colleges test zigzag rearrangement because it combines three skills in a single short function: iterating an array by index, applying a condition that flips on each step, and doing an in-place swap without introducing off-by-one errors.

Assessors specifically look for correct use of i % 2 == 0 to branch on index parity. A common submission mistake is to sort the array first and then interleave elements from opposite ends. That approach produces a valid zigzag but runs in O(n log n) rather than O(n). When the question asks for the optimal solution, the sort-based version loses marks.

The zigzag pattern pairs with other array questions in the same round. For array element operations in Python and the broader collection of standard Python practice programs, those articles cover the adjacent problems CRT sets typically combine with this one.

The single-pass swap in zigzag_array is a clear example of using index parity to drive control flow. Exploring how an LLM explains that correctness argument, suggests test cases for the all-equal edge case, or spots the off-by-one in a buggy version is the next practical use of the skill. TinkerLLM is the playground for that, at ₹299 a month.