Wave Array

Easy
614.

Wave Array

Wave Array is an easy coding problem on arrays and sorting, asked in Amazon, TCS and Infosys interviews.

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
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 waveArray = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Wave Array — Solution in Python, Java & C++

Wave Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and TCS.

Wave Array is an easy coding problem on arrays and sorting, asked in Amazon, TCS and Infosys interviews.

  • Difficulty: Easy
  • Topics: Arrays, Sorting
  • Asked at: Amazon, TCS, Infosys
  • 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

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

Hints for Wave Array

  1. Hint 1

    Sort first — the wave then falls out of a fixed swap pattern.

  2. Hint 2

    Swap (0,1), (2,3), (4,5) … and never (1,2).

  3. Hint 3

    An odd-length array leaves the final element alone; it is already larger than its left neighbour.

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

Java

public static int[] waveArray(int[] arr) {
    int[] s = arr.clone();
    Arrays.sort(s);
    for (int i = 0; i + 1 < s.length; i += 2) {
        int t = s[i];
        s[i] = s[i + 1];
        s[i + 1] = t;
    }
    return s;
}

C++

vector<int> waveArray(vector<int>& arr) {
    vector<int> s = arr;
    sort(s.begin(), s.end());
    for (size_t i = 0; i + 1 < s.size(); i += 2) swap(s[i], s[i + 1]);
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms