Wave Array

Problem Statement

Sort an unsorted array arr of length n in a waveform. An array is said to be in wave form if it satisfies the following conditions:

• The array elements in the output should be such that arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] .....
• If there are multiple sorted orders in wave form, print any one of the viable solutions.
• The unsorted array may contain duplicate values. (The array [7, 7, 11, 3, 4, 5, 15] can output wave arrays [4, 3, 7, 5, 11, 7, 15] or [ 7, 7, 11, 3, 5, 4, 15] or any other valid wave array. )

Example

Example Explanation

Input: arr = [7, 7, 11, 3, 4, 5, 15] Output: [4, 3, 7, 5, 11, 7, 15] or any other array in wave form.

Explanation: In the above example, it can be seen that 4 >= 3 <= 7 >= 5 <= 11 >= 7 <= 15. Thus the resultant array will be [4, 3, 7, 5, 11, 7, 15] as it is sorted in wave form.

Input/Output

Input

• The first line of input contains integer n, which is the size of the array.
• The second line contains n space-separated elements of the unsorted array.

Output

• The output contains the array sorted in wave format.

Constraints

$1 ≤ n ≤ 10^{6}$
$0 ≤ arr[i] ≤ 10^{7}$

Transform Your Career

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

Algorithm 1 - Simple Brute Force Approach - Use Sorting and Swapping

Algorithm

• Step 1 - At the initial step, sort the input array in ascending order, (i.e. arr[0] <= arr[1] <= arr[2]...)

• Step 2 - Next, on swapping the alternate elements (i.e. arr[0] with arr[1] and arr[2] with arr[3]..) a wave array is obtained.

Note: This approach prints the lexicographically smallest array.

Code Implementation

C++

Java

Python

Output

Time complexity

On using heap sort, the time complexity for sorting becomes O(n * logn). To swap elements the entire array needs to be traversed. Hence the time complexity for swapping is O(n). Therefore, the total time complexity for this approach will be O(n * logn).

Space complexity

Since heap sort is being used no additional space is required. Thus, the space complexity for this approach will be O(1).

Algorithm 2 - Comparing Neighbors

Algorithm

• Step 1 - At the initial step, traverse all even positioned elements of the input array such that
  • If the current element is smaller than the previous element (positioned at the odd index), swap the elements at the previous and current index.
  • If the current element is smaller than the next element (positioned at the odd index), swap the elements at the next and current index.

Code Implementation

C++

Java

Python

Output

Time Complexity

Since the entire array needs to be linearly traversed the time complexity for this approach will be O(n).

Space Complexity

Since no extra space is required the space complexity for this approach will be O(1).