Sort an array in a waveform
Difficulty Level
Easy
Asked In
Google, Amazon, Adobe
Two Solutions Discussed
- Brute force solution using sorting
- Efficient solution using the single scan: Incrementing the loop by two
Key takeaway after reading this blog
This is an excellent problem to learn problem-solving using a single scan, where we can improve the efficiency of the solution by incrementing the loop by two. The code is intuitive and simple to visualize.
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 wave form if A[0] >= A[1] <= A[2] >= A[3] <= A[4] >= … so on.
NOTE: There can be multiple possible answers, but we just return any one possible wave-like arrangement.
Examples
Input: A[] = [1, 2, 3, 4]
Output: A[] = [2, 1, 4, 3] OR [4, 1, 3, 2] OR any other array that is in wave form.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 array that is in wave form.
Brute Force Solution Using Sorting
If we look at the wave-like output, the numbers are arranged in alternate order of maximum and minimum values. So how we transform the input in such order? If our input array is sorted then, can we arrange the array 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]. Now if we pick the elements in pairs from the start and swap the adjacent elements then it gets arranged in the form of the wave order. Can you see why?
Visualization of the Sorted Array
After swapping adjacent elements in the sorted array
Algorithm Code C++
Algorithm 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 heapsort. Time complexity = time complexity of sorting + time complexity of swapping adjacent elements = O(nlogn) + O(n) = O(nlogn)
Space complexity: O(1) if we use heapsort.
Space complexity: O(n) if we use merge sort.
Efficient solution using the single scan: Incrementing the loop by two
In this approach, we compare adjacent elements at odd and even positions at every iteration. The idea is to ensure that all elements at even positions are greater (or smaller) than their adjacent elements.
Algorithm Steps
- Iterate over even-positioned elements at every step.
- If the current element is smaller than the last odd element, swap the current element with the last element.
- If the current element is smaller than the next odd element, swap the current element with the next element.
Algorithm Code C++
Algorithm Analysis
The time complexity of the above algorithm would be O(n) because we are linearly traversing the elements of the array. Space complexity: O(1) as no extra memory is being used.
Possible questions by the Interviewer
- How would we modify the above algorithm if we were told to output the lexicographically smallest solution?
- Does the above algorithm work if adjacent elements are equal?
- Can we pick elements at odd positions and compare them with elements at even positions?
- How many comparisons are made in the second approach?
- Compare various sorting algorithms.
Reviewer: Shubham Gautam
Suggested Problems to learn problem solving using a single loop, two pointers and sliding window
- Buildings Facing Sun
- Leaders in an Array
- Valid Mountain Array
- Roman to Integer
- Find Equilibrium Index
- Sort Array of 0s, 1s, and 2s
- Find Product Except Self
- Maximum and Minimum in Array
- FizzBuzz Problem
- Check Pair Sum in Array
- Triplets with Zero Sum
- Intersection of Two Arrays
- Check Subset Arrays
- Move Zeroes to End
- Remove Duplicates Sorted Array
- Container with Most Water
- Trapping Rainwater Problem
- Longest Unique Substring
- Distinct Elements in Window
- Max Continuous Series of 1s
- Maximum Subarray Sum
- Max Consecutive Ones
- N-Repeated Element
- Majority Element in Array
For more content, explore our free DSA course and coding interview blogs.
If you have any queries or feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!
Originally published at: https://www.enjoyalgorithms.com/blog/sort-an-array-in-a-waveform/
