Rearrange Array - C++ Solution

1. Introduction

In this blog post, we will tackle an interesting problem of rearranging elements in an array. The goal is to rearrange the array in such a way that every second element is greater than its left and right neighbors. This problem not only tests your understanding of array manipulation but also your ability to optimize for a single-pass solution.

Problem

Given an integer array, rearrange it in-place so that every second element becomes greater than its adjacent elements. The solution should complete in a single traversal of the array. Multiple valid rearrangements are acceptable.

2. Solution Steps

1. Traverse the array from the second element to the second last element.

2. For each element at an even index (considering 0 as the first index), check if it's greater than its adjacent elements.

3. If not, swap it with the greater of its two neighbors.

4. Continue this process until the end of the array is reached.

5. This ensures every second element (at even indices) is greater than its neighbors.

3. Code Program

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

// Function to rearrange the array
void rearrangeArray(vector<int>& nums) {
    for (size_t i = 1; i < nums.size() - 1; i += 2) {
        // If the current element is less than the previous, swap them
        if (nums[i] < nums[i - 1]) {
            swap(nums[i], nums[i - 1]);
        }
        // If the current element is less than the next, swap them
        if (nums[i] < nums[i + 1]) {
            swap(nums[i], nums[i + 1]);
        }
    }
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
    rearrangeArray(nums);
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

Output:

1 3 2 5 4 7 6

Explanation:

- For [1, 2, 3, 4, 5, 6, 7], a possible rearrangement is [1, 3, 2, 5, 4, 7, 6]. Here, every second element (3, 5, 7) is greater than its adjacent elements.

- For [6, 9, 2, 5, 1, 4], one rearrangement could be [6, 9, 2, 5, 1, 4] or [1, 5, 2, 6, 4, 9]. The solution can yield any valid combination as per the problem's constraints.