Wave Sort

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

Input: [3, 6, 5, 10, 7, 20]
Output: [6, 3, 10, 5, 20, 7]
Explanation: The output array satisfies the wave-like pattern: 6 >= 3 <= 10 >= 5 <= 20 >= 7.

Example 2

Input: [1, 2, 3, 4]
Output: [2, 1, 4, 3]
Explanation: The output array satisfies the wave-like pattern: 2 >= 1 <= 4 >= 3.

Solution

Method 1 - Using sorting

To achieve the desired outcome:

1. 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.
2. After sorting, by swapping adjacent pairs (index i and i+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).

This approach ensures that the wave-like pattern is met efficiently.

Approach

1. Step 1: Sort the array in ascending order to bring neighbouring elements closer in value.
2. Step 2: Swap consecutive elements (i.e., array[i] and array[i+1]) to form the wave pattern.
3. Step 3: Return the modified array.

Code

Java

class Solution {
    public int[] waveSort(int[] nums) {
        // Step 1: Sort the array in ascending order
        Arrays.sort(nums);
        
        // Step 2: Swap adjacent elements to create the wave-like pattern
        for (int i = 0; i < nums.length - 1; i += 2) {
            // Swap nums[i] and nums[i+1]
            int temp = nums[i];
            nums[i] = nums[i + 1];
            nums[i + 1] = temp;
        }
        
        // Return the modified array
        return nums;
    }

    public static void main(String[] args) {
        // Test cases
        Solution solution = new Solution();
        int[] arr1 = {3, 6, 5, 10, 7, 20};
        int[] arr2 = {1, 2, 3, 4};
        
        System.out.println(Arrays.toString(solution.waveSort(arr1))); // Output: [6, 3, 10, 5, 20, 7]
        System.out.println(Arrays.toString(solution.waveSort(arr2))); // Output: [2, 1, 4, 3]
    }
}

Python

class Solution:
    def wave_sort(self, nums):
        # Step 1: Sort the array in ascending order
        nums.sort()
        
        # Step 2: Swap adjacent elements to create the wave-like pattern
        for i in range(0, len(nums) - 1, 2):
            # Swap nums[i] and nums[i+1]
            nums[i], nums[i + 1] = nums[i + 1], nums[i]
        
        # Return the modified array
        return nums

# Testing the solution
solution = Solution()

# Test cases
arr1 = [3, 6, 5, 10, 7, 20]
arr2 = [1, 2, 3, 4]

print(solution.wave_sort(arr1))  # Output: [6, 3, 10, 5, 20, 7]
print(solution.wave_sort(arr2))  # Output: [2, 1, 4, 3]

Complexity

• ⏰ Time complexity: O(n log n)
  • Sorting the array takes O(n log n).
  • Swapping elements in a loop takes O(n).
• 🧺 Space complexity: O(n). Sorting usually requires additional space for storage, resulting in O(n).