Sort an array in a waveform

EnjoyAlgorithms Blog Cover Image

Difficulty: Easy, Asked-in: Google, Amazon, Adobe

Key takeaway: An excellent problem to learn problem-solving using sorting and single scan (Incrementing the loop by 2). Such problems are popular where we need to rearrange the input in place to get the output.

Let’s understand the problem

Given an array of integers, sort the array into a wave-like arrangement. In other words, An array A[0...n-1] is sorted in waveform if A[0] >= A[1] <= A[2] >= A[3] <= A[4] >= …. Note: There can be multiple possible answers but we just need to return anyone possible wave-like arrangement.

Example 1

Input: A[] = [1, 2, 3, 4]

Output: A[] = [2, 1, 4, 3] or [4, 1, 3, 2] or any other wave form like structure.

Example 2

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

Output: A[] = [20, 8, 10, 4, 6, 2] or [10, 8, 20, 2, 6, 4] or any other wave form like structure.

Discussed Solution Approaches

  • A brute force solution using sorting
  • An efficient solution using a single loop: Increment by 2

A brute force solution using sorting

Solution Idea

The values are organized in an alternate order of max and min values if we look at the wave-like output. So how do we transform the given input in such an order? One idea is: if our input array is sorted, can we arrange the elements in waveform? Let’s think!

Suppose our input array is sorted, then all the elements will be arranged in the increasing order i.e. A[0] ≤ A[1] ≤ A[2] ≤ A[3]≤ ….≤A[n - 2] ≤ A[n - 1]. So if we pick the elements in pairs from the start and swap the adjacent elements, they will get arranged in wave order. Think!

Visualization of the Sorted Array

Visualization of the Sorted Array

Visualization after swapping adjacent elements in the sorted array

sort an array in a waveform solution idea

Solution Pseudocode

Solution Analysis

Here the time complexity is dominated by the sorting algorithm. It will be O(nlogn) if we use an efficient sorting algorithm like quicksort, merge sort, or heap sort.

Time complexity = Time complexity of sorting + Time complexity of swapping the adjacent element = O(nlogn) + O(n) = O(nlogn)

Space complexity = O(1) if we use heap sort.

Space complexity = O(n) if we use merge sort.

An efficient solution using a single loop: Increment by 2

Solution Idea

The critical question is: can we solve this problem in O(n) time complexity, i.e., without using sorting. Let's think and explore one level further!

From the given output pattern, if we ensure that values at all the even positions are greater than the odd position, we can achieve the wave-like structure. In other words, for every even index i, we need to ensure this order in triplet A[i - 1], A[i] and A[i + 1] => A[i - 1] < A[i] > A[i + 1]

  • Case 1: If A[i - 1] < A[i] < A[i + 1]

    We need to swap A[i] and A[i + 1] to get the order A[i - 1] < A[i] > A[i + 1].

  • Case 2: If A[i - 1] > A[i] > A[i + 1]

    we need to swap A[i - 1] and A[i] to get the order A[i - 1] < A[i] > A[i + 1].

  • Case 3: If A[i - 1] > A[i] < A[i + 1]

    We need to swap A[i - 1] and A[i] to get the order A[i - 1] < A[i]. Now if A[i] < A[i + 1], then we need to swap A[i] and A[i + 1].

  • Case 4: If A[i - 1] < A[i] > A[i + 1]

    There is no need to do any swapping because values are already arranged in the required order.

If we simplify further from cases 1, 2, and 3 (Think about this step!)

  • If A[i - 1] > A[i], we need to just swap A[i - 1] and A[i]
  • If A[i] < A[i + 1], we need to just swap A[i] and A[i + 1]

We can run a loop to compare adjacent elements at every iteration and ensure that all elements at even positions are greater than their adjacent elements at odd positions.

Solution Steps

  1. We run a loop incrementing by two to iterate over elements at even positions.
  2. If the current element A[i] is smaller than the previous element A[i - 1], then we swap the current element A[i] with the A[i - 1].

    if(i > 0 && A[i - 1] > A[i])
       swap(A[i], A[i - 1])
    
  3. If the current element A[i] is smaller than the next element A[i+1], then we swap the current element A[i] with the A[i + 1].

    if(i < n - 1 && A[i] < A[i + 1])  
       swap(A[i], A[i + 1])
    

Solution Pseudocode

Solution Analysis

The time complexity for the above solution would be O(n) because we are linearly traversing the array and performing O(1) operations at each iteration. Space complexity = O(1), we are not using constant extra memory.

Critical ideas to think!

  • How do we modify the above solutions to output the lexicographically smallest solution?
  • Does the above solution work if adjacent elements are equal?
  • Can we pick elements at odd positions and compare them with elements at even positions?
  • How many comparisons and swapping operations are made in the 2nd solution?
  • Can we solve this problem using another approach?

Comparisons of time and space complexities

  • Using sorting: Time = O(nlogn), Space = O(1), if we use heap sort.
  • Using a single loop: Time = O(n), Space = O(1)

Suggested coding questions to practice

Thanks to Navtosh Kumar for his contribution in creating the first version of the content. Please write comments if you find an error or you want to share more insights about the topic. Enjoy learning, Enjoy coding, Enjoy algorithms!

We'd love to hear from you

More content from EnjoyAlgorithms

Our weekly newsletter

Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops and math. enjoy learning!