Convert Array Into Zig-Zag Fashion — Easy Problem & Solution

Problem statement

Rearrange arr so that it zig-zags: arr[0] < arr[1] > arr[2] < arr[3] > arr[4] ….

Produce the arrangement the single left-to-right pass gives: walk i from 0 to n - 2, alternating the relation you require starting with <, and swap arr[i] with arr[i+1] whenever the required relation does not already hold.

Example 1

Input: arr = [4,3,7,8,6,2,1]
Output: [3,7,4,8,2,6,1]
Explanation: 3 < 7 > 4 < 8 > 2 < 6 > 1.

Example 2

Input: arr = [1,4,3,2]
Output: [1,4,2,3]

Example 3

Input: arr = [5,5,5]
Output: [5,5,5]
Explanation: Equal values need no swap under either relation.

Constraints

• 1 <= arr.length <= 100000
• 0 <= arr[i] <= 1000000

How to solve Convert Array Into Zig-Zag Fashion

Fix the relations left to right. At each step only the pair (i, i+1) is examined; if it violates the required relation, swapping repairs it, and the repair cannot undo an earlier one.

Approach

1. Start with wantLess = true, meaning arr[0] < arr[1] is required.
2. For each i from 0 to n - 2: if wantLess and arr[i] > arr[i+1], swap; if not wantLess and arr[i] < arr[i+1], swap.
3. Flip wantLess and continue.

Why it works

When the pass swaps at i, the value moved into position i is the smaller (for <) or larger (for >) of the pair — which only strengthens the relation already established between i-1 and i. So each fixed relation stays fixed.

Complexity

• Time — O(n)
• Space — O(n) for the copy

Pitfalls

• Sorting first and then swapping pairs gives a valid zig-zag but a different one — this problem asks for the single-pass result.
• Starting the flag on > produces the mirror pattern and fails every case.

Reference solution

Python

from typing import List

def zigZag(arr: List[int]) -> List[int]:
    a = list(arr)
    want_less = True
    for i in range(len(a) - 1):
        if want_less:
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
        else:
            if a[i] < a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
        want_less = not want_less
    return a

JavaScript

var zigZag = function(arr) {
    var a = arr.slice();
    var wantLess = true;
    for (var i = 0; i + 1 < a.length; i++) {
        if (wantLess) {
            if (a[i] > a[i + 1]) { var t = a[i]; a[i] = a[i + 1]; a[i + 1] = t; }
        } else {
            if (a[i] < a[i + 1]) { var u = a[i]; a[i] = a[i + 1]; a[i + 1] = u; }
        }
        wantLess = !wantLess;
    }
    return a;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy