Problem Statement

Given an unsorted array of integers, the task is to rearrange the array in such a way that it forms a waveform. An array is said to be sorted in a waveform if the elements satisfy the condition:
arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= ....

In other words, the elements at even indices should be greater than or equal to their adjacent elements, and elements at odd indices should be smaller than or equal to their adjacent elements.

Examples

Example 1:

Input: arr = [10, 5, 6, 3, 2, 20, 100, 80]
Output: [10, 5, 6, 2, 20, 3, 100, 80]

Example 2:

Input: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Output: [2, 1, 4, 3, 6, 5, 8, 7, 9]

Different Approaches

Intuition:

The waveform pattern alternates between peaks and valleys. If we think in terms of pairs of adjacent elements:

• At even indices, we want the element to be greater than or equal to its next element (if possible).
• At odd indices, we want the element to be less than or equal to its next element.

To achieve this, one approach is to ensure that for every adjacent pair, we swap elements if they don’t satisfy the waveform condition. Alternatively, we can sort the array and then rearrange the elements to follow the waveform pattern.

1️⃣ Sorting Approach

Approach:

1. First, sort the array.
2. Swap every adjacent pair of elements starting from the second element (i.e., at index 1, swap it with index 2, at index 3 swap with index 4, and so on).
3. After sorting, the adjacent elements will automatically form a waveform pattern by swapping.

Code:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void waveSortBySorting(vector<int>& arr) {
    // Step 1: Sort the array
    sort(arr.begin(), arr.end());

    // Step 2: Swap adjacent elements
    for (int i = 1; i < arr.size(); i += 2) {
        swap(arr[i], arr[i - 1]);
    }
}

void printArray(const vector<int>& arr) {
    for (int x : arr) {
        cout << x << " ";
    }
    cout << endl;
}

int main() {
    vector<int> arr = {10, 5, 6, 3, 2, 20, 100, 80};
    
    cout << "Original array: ";
    printArray(arr);
    
    waveSortBySorting(arr);
    
    cout << "Waveform sorted array: ";
    printArray(arr);

    return 0;
}

Complexity Analysis:

• Time Complexity:
  • Sorting the array takes O(n log n), and swapping adjacent elements takes O(n).
  • Therefore, the total time complexity is O(n log n).
• Space Complexity:
  • The sorting algorithm typically takes O(n) space for the sorting process (depending on the implementation of sort()), but in-place sorting with std::sort() is often optimized for O(1) space.

2️⃣ Greedy Swap Method

Approach:

1. Traverse the array and for every even index i, check if arr[i] >= arr[i+1]. If not, swap the two.
2. Similarly, for every odd index i, check if arr[i] <= arr[i+1]. If not, swap the two.
3. This approach works because by ensuring that each adjacent pair follows the waveform condition, we are constructing the waveform gradually.

Dry Run:

Initialization:

      +-----+-----+-----+-----+-----+-----+-----+-----+
arr = | 10  |  5  |  6  |  3  |  2  | 20  | 100 | 80  |
      +-----+-----+-----+-----+-----+-----+-----+-----+
         0     1     2     3     4     5     6     7

Iteration 1:

      +-----+-----+-----+-----+-----+-----+-----+-----+
arr = | 10  |  5  |  6  |  3  |  2  | 20  | 100 | 80  |
      +-----+-----+-----+-----+-----+-----+-----+-----+
         0     1     2     3     4     5     6     7
         ^
         |
         i
  
  arr[i]: arr[0] = 10
  Check neighbors:
        arr[0] = 10, arr[1] = 5
        Since 10 >= 5 (condition satisfied, no swap needed)

Iteration 2:

      +-----+-----+-----+-----+-----+-----+-----+-----+
arr = | 10  |  5  |  6  |  3  |  2  | 20  | 100 | 80  |
      +-----+-----+-----+-----+-----+-----+-----+-----+
         0     1     2     3     4     5     6     7
                     ^
                     |
                     i
  
  arr[i]: arr[2] = 6
  Check neighbors:
        arr[2] = 6, arr[3] = 3
        Since 6 >= 3 (condition satisfied, no swap needed)

Iteration 3:

      +-----+-----+-----+-----+-----+-----+-----+-----+
arr = | 10  |  5  |  6  |  3  |  2  | 20  | 100 | 80  |
      +-----+-----+-----+-----+-----+-----+-----+-----+
         0     1     2     3     4     5     6     7
                                 ^
                                 |
                                 i
  
  arr[i]: arr[4] = 2
  Check neighbors:
        arr[4] = 2, arr[5] = 20
        Since 6 >= 3 (condition not satisfied, swap them)
        swap arr[4] and arr[5]

Iteration 4:

      +-----+-----+-----+-----+-----+-----+-----+-----+
arr = | 10  |  5  |  6  |  3  | 20  |  2  | 100 | 80  |
      +-----+-----+-----+-----+-----+-----+-----+-----+
         0     1     2     3     4     5     6     7
                                             ^
                                             |
                                             i
  
  arr[i]: arr[4] = 2
  Check neighbors:
        arr[4] = 2, arr[5] = 20
        Since 6 >= 3 (condition satisfied, no swap needed)

Iteration 6 (Loop Termination):

      +-----+-----+-----+-----+-----+-----+-----+-----+
arr = | 10  |  5  |  6  |  3  | 20  |  2  | 100 | 80  |
      +-----+-----+-----+-----+-----+-----+-----+-----+
         0     1     2     3     4     5     6     7
                                                         ^
                                                         |
                                                         i
  
  Since i has exceeds the bounds of the array. so, loop will terminate.

Code:

#include <iostream>
#include <vector>
using namespace std;

void waveSort(vector<int>& arr) {
    int n = arr.size();
    
    for (int i = 0; i < n; i += 2) {
        // If current element is smaller than the previous one, swap
        if (i > 0 && arr[i] < arr[i - 1]) {
            swap(arr[i], arr[i - 1]);
        }

        // If current element is smaller than the next one, swap
        if (i < n - 1 && arr[i] < arr[i + 1]) {
            swap(arr[i], arr[i + 1]);
        }
    }
}

void printArray(const vector<int>& arr) {
    for (int x : arr) {
        cout << x << " ";
    }
    cout << endl;
}

int main() {
    vector<int> arr = {10, 5, 6, 3, 2, 20, 100, 80};
    
    cout << "Original array: ";
    printArray(arr);
    
    waveSort(arr);
    
    cout << "Waveform sorted array: ";
    printArray(arr);

    return 0;
}

Complexity Analysis:

• Time Complexity:  O(n), where n is the size of the array.
  • We traverse the array only once, and the operations within each iteration (checking and swapping) take constant time.
• Space Complexity: O(1)
  • No additional data structures are used, so the space complexity is O(1).