Wave Array — Easy Problem & Solution

Problem statement

An array is in wave form when arr[0] >= arr[1] <= arr[2] >= arr[3] <= ….

Given arr, return the lexicographically smallest wave arrangement of its elements. That arrangement is obtained by sorting the array ascending and then swapping every adjacent pair: positions (0,1), (2,3), and so on.

Example 1

Input: arr = [1,2,3,4,5]
Output: [2,1,4,3,5]
Explanation: Sorted it is [1,2,3,4,5]; swapping (0,1) and (2,3) gives [2,1,4,3,5]. The lone last element stays put.

Example 2

Input: arr = [20,10,8,6,4,2]
Output: [4,2,8,6,20,10]

Example 3

Input: arr = [9]
Output: [9]

Constraints

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

How to solve Wave Array

After sorting, swapping each disjoint adjacent pair puts a larger value in every even position and a smaller one in every odd position — exactly the wave condition — and because the sort came first, no smaller arrangement exists.

Approach

1. Sort a copy of arr ascending.
2. For i = 0, 2, 4, … while i + 1 < n, swap s[i] and s[i+1].
3. Return the result.

Why it works

In sorted order s[i] <= s[i+1], so after the swap position i holds the larger of the pair and position i+1 the smaller — giving s[i] >= s[i+1]. Across a pair boundary, s[i+1] (the old s[i]) is at most s[i+2] (the old s[i+3]), so <= holds there too.

Complexity

• Time — O(n log n)
• Space — O(n)

Pitfalls

• Swapping overlapping pairs (0,1), (1,2) destroys the invariant the previous swap just established.
• Skipping the i + 1 < n guard reads past the end on an odd-length array.

Reference solution

Python

from typing import List

def waveArray(arr: List[int]) -> List[int]:
    s = sorted(arr)
    for i in range(0, len(s) - 1, 2):
        s[i], s[i + 1] = s[i + 1], s[i]
    return s

JavaScript

var waveArray = function(arr) {
    var s = arr.slice().sort(function(a, b) { return a - b; });
    for (var i = 0; i + 1 < s.length; i += 2) {
        var t = s[i];
        s[i] = s[i + 1];
        s[i + 1] = t;
    }
    return s;
};

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