Rearrange the array such that the even index elements are smaller and the odd index elements are greater

Optimized Approach

The optimal approach to solving this problem of rearranging an array such that the even index elements are smaller and the odd index elements are greater is by removing the sort function. In this approach, we will not sort the array. We will start from the 0th element and traverse till the (n-2)th element. For every i, in the array we will check if the ith element is even and if(a[i]>a[i+1]),then we will swap(a[i],a[i+1]) and if i is odd then we will check if(a[i]<a[i+1]), then we will swap(a[i],a[i+1]).

Algorithm

1. We will create a function called rearrangeArray(), and it will take one argument: the initial array. 
2. We will start from the first element and traverse until the (n-2)th element.
3. For every i, we will check if i is even, and if(a[i]>a[i+1]) if the conditions are true, then we will swap both the elements.
4. We will check if i is odd, and if(a[i]<a[i+1]), if the conditions are true, then we will swap both the elements.
5. After the iteration is over then, we will print the array.

Code in C++

// C++ to rearrange array such that the even index elements are smaller and the odd index elements are greater
#include <bits/stdc++.h>
using namespace std;

// function to rearrange the array
void rearrangeArray(vector<int> &a)
{
    int n = a.size();

    for (int i = 0; i < n - 1; i++)
    {
        // if i is even
        if (i % 2 == 0)
        {
            // if a[i]>a[i+1], then we will swap(a[i],a[i+1])
            if (a[i] > a[i + 1])
            {
                swap(a[i], a[i + 1]);
            }
        }
        // if i is odd
        else
        {
            // if a[i]<a[i+1], then we will swap(a[i],a[i+1])
            if (a[i] < a[i + 1])
            {
                swap(a[i], a[i + 1]);
            }
        }
    }
}

//Driver Code
int main()
{

    int n = 4;

    vector<int> a(n);

    a = {4, 7, 7, 2};

    cout << "The array before rearranging is:"<< " ";

    for (auto x : a)
    {
        cout << x << " ";
    }

    cout << endl;

    rearrangeArray(a);

    cout <<"The array after rearranging is:" << " ";

    for (auto x: a)
    {
        cout << x << " ";
    }

    cout << endl;
}

You can also try this code with Online C++ Compiler

Run Code

Input

The array before rearranging elements is:  4 7 7 2

Output

The array after rearranging elements is: 4 7 2 7

Algorithm Complexity

Time Complexity: O(N)

Since we are only using a single loop, the time complexity would be O(N).

Space Complexity: O(1)

Since we are not using any extra space, the space complexity would be O(1).

Frequently asked questions

Can we create an array of negative sizes?

A negative value cannot be used as the array size. If you enter a negative integer in Array size, the NegativeArraySizeException will be thrown at run time.

Why is the complexity of fetching an element from an array O(1)?

Arrays store objects in a contiguous memory location. If you know the address of the base object, you can get the address of the ith object.

address(arr[i]) = address(arr[0]) + i*size

Since this term is independent of n, the time complexity of fetching an element from an array is O(1).

How can we remove a particular element from an array?

We can remove a particular element from an array using two approaches:

• First, we copy all the elements of the array in another array and don’t copy the element we are removing.
• The second is that we search the element and shift all the elements by one index on the left. Note that we will only shift those elements present on the right side of the target element.

Conclusion

In this article, we have discussed the problem of rearranging an array such that the even index elements are smaller and the odd index elements are greater. We have discussed two approaches for this problem: the brute force approach and the optimized approach. We have also discussed the time complexities and space complexities of both approaches.

We hope you have gained a better understanding of the solution to this problem and, now it is your responsibility to solve the problem and try some new and different approaches to this problem. 

Recommended Problems -

• Rearrange Array Alternately
• Sum Of Two Arrays
• Merge K Sorted Arrays

You can also refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc., you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Coding.