Zigzag Lineup
MediumSorting & Searching
Problem
A choreographer arranges dancers by height so the line goes up, down, up, down: line[0] ≤ line[1] ≥ line[2] ≤ line[3] ≥ .... Formally, for every even i with a neighbour, line[i] ≤ line[i + 1], and for every odd i with a neighbour, line[i] ≥ line[i + 1].
Given the dancers' heights, many arrangements may qualify. Return the lexicographically smallest one: compare arrangements position by position, and the first smaller value wins.
Example 1
- Input:
- heights = [3, 1, 2, 5, 4]
- Output:
- [1, 3, 2, 5, 4]
1 ≤ 3 ≥ 2 ≤ 5 ≥ 4. Starting with [1, 2, ...] is impossible, because the third dancer would need a height ≤ 2 and only 3, 4, 5 remain.
Example 2
- Input:
- heights = [2, 2, 1, 1]
- Output:
- [1, 2, 1, 2]
Constraints
- 1 ≤ heights.length ≤ 10^5
- 1 ≤ heights[i] ≤ 10^9
Hint
Show the first hint
Sort first. Which value must come first in the smallest arrangement, and is that always possible?
Walkthrough
How to approach it
01Clarify before coding
- Are the comparisons strict? No, equal neighbours are allowed (≤ and ≥).
- Which arrangement if several are valid? The lexicographically smallest, which makes the answer unique.
- Can there be one dancer? Yes: the line is just that dancer.
02Brute force
Generate every permutation, keep the valid zigzags, and return the smallest.
Cost: O(n! · n): impossible beyond about 10 dancers.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.