Convert Array Into Zig-Zag Fashion

Easy
615.

Convert Array Into Zig-Zag Fashion

Convert Array Into Zig-Zag Fashion is an easy coding problem on arrays and greedy, asked in Amazon, Wipro and Cognizant interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number[]}
 */
var zigZag = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Convert Array Into Zig-Zag Fashion — Problem & Solution

Convert Array Into Zig-Zag Fashion solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Convert Array Into Zig-Zag Fashion is an easy coding problem on arrays and greedy, asked in Amazon, Wipro and Cognizant interviews.

  • Difficulty: Easy
  • Topics: Arrays, Greedy
  • Asked at: Amazon, Wipro, Cognizant
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Convert Array Into Zig-Zag Fashion

  1. Hint 1

    One pass is enough — no sorting needed.

  2. Hint 2

    Keep a flag that alternates between 'the next relation must be <' and 'must be >'.

  3. Hint 3

    A swap only ever touches i and i+1, and it can never break the relation you fixed at i-1.

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

Java

public static int[] zigZag(int[] arr) {
    int[] a = arr.clone();
    boolean wantLess = true;
    for (int i = 0; i + 1 < a.length; i++) {
        if (wantLess) {
            if (a[i] > a[i + 1]) { int t = a[i]; a[i] = a[i + 1]; a[i + 1] = t; }
        } else {
            if (a[i] < a[i + 1]) { int t = a[i]; a[i] = a[i + 1]; a[i + 1] = t; }
        }
        wantLess = !wantLess;
    }
    return a;
}

C++

vector<int> zigZag(vector<int>& arr) {
    vector<int> a = arr;
    bool wantLess = true;
    for (size_t i = 0; i + 1 < a.size(); i++) {
        if (wantLess) {
            if (a[i] > a[i + 1]) swap(a[i], a[i + 1]);
        } else {
            if (a[i] < a[i + 1]) swap(a[i], a[i + 1]);
        }
        wantLess = !wantLess;
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms