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 <= 1000000 <= arr[i] <= 1000000
Hints for Convert Array Into Zig-Zag Fashion
Hint 1
One pass is enough — no sorting needed.
Hint 2
Keep a flag that alternates between 'the next relation must be <' and 'must be >'.
Hint 3
A swap only ever touches
iandi+1, and it can never break the relation you fixed ati-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
- Start with
wantLess = true, meaningarr[0] < arr[1]is required. - For each
ifrom0ton - 2: ifwantLessandarr[i] > arr[i+1], swap; if notwantLessandarr[i] < arr[i+1], swap. - Flip
wantLessand 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 aJava
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