Sort Array in Waveform in Java
Java program to Sort Array in Waveform
Problem “Sort Array in Waveform in Java” is a popular and fundamental array manipulation question that frequently appears in coding interviews. It helps you understand sorting techniques, index based swapping, and how to modify the arrangement of elements in a pattern to meet specific conditions.
In this article, we will discuss what a wave array is, the logic behind it, multiple ways to implement it in Java, and the complexity analysis, all explained in simple language with complete executable code and examples.
Sort Array in Waveform in Java
What is a Waveform Array?
An array is said to be in waveform if its elements are arranged in a sequence where:
arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] ...
In other words, elements at even indices are greater than or equal to their next element, while elements at odd indices are smaller than or equal to their next element.
This arrangement creates a wave like pattern when you visualize the numbers.
Example:
Input:
arr = [10, 90, 49, 2, 1, 5, 23]
Output:
Waveform Array: [10, 49, 2, 90, 1, 23, 5]
Explanation:
After rearranging, the array satisfies the condition:
10 >= 49 <= 2 >= 90 <= 1 >= 23 <= 5
1. arrays based on positional relationships.
2. Use sorting and swapping efficiently.
3. Practice O(n) traversal and comparison logic.
If we plot step 1 (that is sorted array) on graph then it would look something like this.
If we plot step 2 (that is swapping adjacent elements) on graph then it would look something like this.
Approaches to Sort Array in Waveform in Java
There are 2 main approaches to solve the Sort Array in Waveform problem:
Learn DSA
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Approach 1: Sorting and Swapping Adjacent Elements
The idea is to first sort the array in ascending order. Once sorted, swap every adjacent pair of elements starting from index 0.
This ensures that every even index is greater than its next (odd) index, forming a wave pattern.
Algorithm:
- Sort the array in ascending order.
- Iterate over the array in steps of 2 (i = 0, 2, 4, …).
- For each i, swap arr[i] and arr[i + 1] if possible.
- The array is now rearranged into waveform order.
Java Code:
import java.util.Arrays;
public class WaveformArray {
public static void sortInWaveform(int[] arr) {
Arrays.sort(arr); // Step 1: Sort array
// Step 2: Swap adjacent elements
for (int i = 0; i < arr.length - 1; i += 2) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
public static void main(String[] args) {
int[] arr = {10, 90, 49, 2, 1, 5, 23};
sortInWaveform(arr);
System.out.println("Waveform Array: " + Arrays.toString(arr));
}
}
Input:
arr = [10, 90, 49, 2, 1, 5, 23]
Output:
Waveform Array: [2, 1, 10, 5, 49, 23, 90]
Space Complexity: O (1)
Approach 2: Single Pass
If the array elements are already distinct or we just want to rearrange them in wave order (without sorting), we can do it in one traversal using simple comparisons.
We iterate over the array and swap elements based on their index position:
- For even indices → ensure arr[i] >= arr[i+1]
- For odd indices → ensure arr[i] <= arr[i+1]
Algorithm:
Traverse the array from index 0 to n-2.
For every index:
If i is even and arr[i] < arr[i+1], swap them.
If i is odd and arr[i] > arr[i+1], swap them.
- Continue till the end.
Java Code:
import java.util.Arrays;
public class WaveformArrayOptimized {
public static void convertToWave(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
if (i % 2 == 0 && arr[i] < arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
} else if (i % 2 == 1 && arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
public static void main(String[] args) {
int[] arr = {10, 90, 49, 2, 1, 5, 23};
convertToWave(arr);
System.out.println("Waveform Array: " + Arrays.toString(arr));
}
}
Input:
arr = [10, 90, 49, 2, 1, 5, 23]
Output:
Waveform Array: [90, 10, 49, 2, 5, 1, 23]
Space Complexity: O(1)
Comparison Between Both Methods
| Approach | Sorting Used | Time Complexity | Space Complexity | Notes |
|---|---|---|---|---|
| Sort + Swap | Yes | O(n log n) | O(1) | Works well for unsorted arrays |
| Single Pass | No | O(n) | O(1) | Best when order doesn’t matter much |
Problem of Sort Array in Waveform in Java teaches you how to rearrange data efficiently and use sorting or swapping to create specific patterns.
- Sorting method is simpler to understand, while the single pass approach is faster for large arrays.
- Mastering this problem helps you strengthen your understanding of array manipulation, indexing, and in-place algorithms, essential topics for coding interviews and real world Java programming.
FAQ's related to Sort Array in Waveform in Java
Answer:
It means rearranging an array so that it follows the wave like pattern:
arr[0] >= arr[1] <= arr[2] >= arr[3] …
This pattern alternates between greater and smaller elements.
Answer:
- You can Sort the array first and then swap every adjacent pair (simpler).
- Or use a single traversal to swap elements based on their indices (more efficient).
Answer:
The sorting based method runs in O(n log n) time, while the one pass method runs in O(n).
Answer:
- If order matters and you need a consistent output, use the sorting method.
- And If speed matters and order doesn’t, use the one pass method.
Answer:
Yes. You can sort using Arrays.sort() or Collections.sort() and then rearrange using index based swaps for the same result.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Arrays
- Introduction to Arrays – C | C++ | Java
- Introduction to 2-D Arrays – C | C++ | Java
- Sorting of Array – C | C++ | Java
- Array Rotation – C | C++ | Java
- Reverse an array or string- C | C++ | Java
- Find pairs in array with given sum – C | C++ | Java
- Sort the array in Waveform – C | C++ | Java
- Majority Element in Array – C | C++ | Java
- Boyer-Moore’s Voting Algorithm – C | C++ | Java
- K-pairs with smallest sum in 2 arrays – C | C++ | Java
- Largest Sum Contigous SubArray – C | C++ | Java
- Maximum Average Sub-array of K length – C | C++ | Java
- Size of sub-array with max sum – C | C++ | Java
- Sub-array with given sum – C | C++ | Java
- Triplet that sum to a given value – C | C++ | Java
- Segregate 0’s and 1’s in array – C | C++ | Java
- Segregate 0’s 1’s and 2’s in array – C | C++ | Java
- Sort elements in array by frequency – C | C++ | Java
- Finding pythagorean triplets in an array – C | C++ | Java
- Reorder array using given indexes – C | C++ | Java
- Merging two sorted arrays – C | C++ | Java
- Minimum number of Merge Operations to make an Array Palindrome – C | C++ | Java
- Find Zeros to be Flipped so that number of Consecutive 1’s is maximized – C | C++ | Java
Login/Signup to comment
import java.util.Arrays;
public class ArrayWaveform {
int temporaryVariable = 0;
public void swapingOfTwoAdjacentNumbers(int[] array, int firstElement, int secondElement) {
temporaryVariable = array[firstElement];
array[firstElement] = array[secondElement];
array[secondElement] = temporaryVariable;
}
public void sortingArrayInWaveForm(int[] arr,int length) {
for(int i=0; i arr[i + 1]) && i % 2 == 1) {
swapingOfTwoAdjacentNumbers(arr, i, i + 1);
}
if ((arr[i] < arr[i + 1] && i % 2 == 0)) {
swapingOfTwoAdjacentNumbers(arr, i, i + 1);
}
}
System.out.println("array in waveform is:");
System.out.println(Arrays.toString(arr));
}
}
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("enter the length of the array:");
int lengthOfTheArray = sc.nextInt();
int[] array = new int[lengthOfTheArray];
System.out.println("enter the array of integer types:");
for(int i=0; i<lengthOfTheArray; i++) {
array[i] = sc.nextInt();
}
System.out.println("the array before sorting it in waveform is:");
System.out.println(Arrays.toString(array));
ArrayWaveform wave = new ArrayWaveform();
wave.sortingArrayInWaveForm(array,lengthOfTheArray);
}
}