Problem
Given an array of integers, modify the array into a wave-like array such that the elements follow the pattern:
a1 >= a2 <= a3 >= a4 <= a5...
. In other words:
- Odd-indexed elements are lesser than or equal to their neighbours.
- Even-indexed elements are greater than or equal to their neighbours.
Problem
Examples
Example 1
|
|
Example 2
|
|
Solution
Method 1 - Using sorting
To achieve the desired outcome:
- A simple way is to ensure that alternating elements of the array follow the given pattern relative to their neighbours in the sorted order. This guarantees correctness because sorting ensures that all smaller elements appear together, and all larger elements follow them.
- After sorting, by swapping adjacent pairs (index
i
andi+1
), we ensure that:- The element at even indices (
i
) is greater than its next neighbour (i+1
). - The element at odd indices (
i+1
) is less than its previous neighbour (i
).
- The element at even indices (
This approach ensures that the wave-like pattern is met efficiently.
Approach
- Step 1: Sort the array in ascending order to bring neighbouring elements closer in value.
- Step 2: Swap consecutive elements (i.e.,
array[i]
andarray[i+1]
) to form the wave pattern. - Step 3: Return the modified array.
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n log n)
- Sorting the array takes
O(n log n)
. - Swapping elements in a loop takes
O(n)
.
- Sorting the array takes
- 🧺 Space complexity:
O(n)
. Sorting usually requires additional space for storage, resulting inO(n)
.