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 <= 1000001 <= arr[i] <= 1000000
Hints for Wave Array
Hint 1
Sort first — the wave then falls out of a fixed swap pattern.
Hint 2
Swap
(0,1),(2,3),(4,5)… and never(1,2).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
- Sort a copy of
arrascending. - For
i = 0, 2, 4, …whilei + 1 < n, swaps[i]ands[i+1]. - 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 < nguard 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 sJava
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