Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Brute Force Approach
2.1.
Algorithm
2.2.
Code in C++
2.2.1.
Algorithm Complexity 
3.
Optimized Approach
3.1.
Algorithm
3.2.
Code in C++
3.2.1.
Algorithm Complexity
4.
Frequently asked questions
4.1.
Can we create an array of negative sizes?
4.2.
Why is the complexity of fetching an element from an array O(1)?
4.3.
How can we remove a particular element from an array?
5.
Conclusion
Last Updated: Mar 27, 2024

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

Introduction

An array comes under one of the essential topics for programming interviews. Many companies like Amazon, Microsoft, and Google ask questions of the array in the interviews. So an individual needs to have a clear understanding of this topic.

In this blog, we will discuss the problem of rearranging an array such that the even index elements are smaller and the odd index elements are greater. We will discuss two approaches for this problem, first one is the brute force approach, and the other one is the optimal approach. 

Must Read, Array Implementation of Queue and  Rabin Karp Algorithm

Problem Statement

Ninjas has an array of size N. After giving the array. He said he wanted to rearrange the array such that the even index elements are smaller and the odd index elements are greater. But, the problem is that he cannot rearrange the array by himself. Can you help him rearrange the array?

For every i in the rearranged array:

  • If i is odd then arr[i]>=arr[i+1] 
  • If i is even then arr[i]<=arr[i+1]
     

You need to output the rearranged array; note that there can be multiple possible answers. 

Before we deep dive into the solution to this problem, we should look at some examples that will help us understand the problem better. 

Sample Examples

Input

N=4, arr[] = {4, 7, 7, 2}

 

Output

arr[] = {4, 7, 2, 7}

Explanation:
Elements at the even index are smaller than the elements at the odd index.
Note: {2, 7, 4, 7} is also a valid answer.

 

Input

N=6, arr[] = {7, 1, 4, 6, 9, 3}

 

Output

{1, 6, 3, 7, 4, 9}

 

Input

N=3, arr[] = {1,3,2}

 

Output

{1,3,2}
Explanation: In this case the array is already arranged as required in the question.

 

Also see, Morris Traversal for Inorder

Brute Force Approach

The brute force 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 simple. We first sort the array, and after that, we will start iterating from the second element, and we will take a pointer j which will start from (n/2 + 1) if n is odd. Else if n is even, it will start from (n/2). We will swap the ith element and the jth element, and after swapping, the elements will increment i by 2, and we will increment j by 1. We will perform these operations till i<n.

Algorithm

  1. To solve this problem, we will create a function called rearrangeArray(), and it will take one argument: the initial array.
  2. After that, we will sort the array.
  3. We will start from i=1, and we will take a pointer j which would point to (n/2+1)th element if n is odd; else, it would point to (n/2)th element. In every iteration, we will swap the ith and jth element, and then we will increment i by 2 and j by 1.
  4. The loop will terminate when i would be greater than or equal to n.
  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();

    // sort the given array
    sort(a.begin(), a.end());

    int j = n / 2;

    // if n is odd then even index elements in the array would be n/2 - 1
    if (n % 2)
    {
        j++;
    }

    for (int i = 1; i < n; i += 2)
    {
        swap(a[j++], a[i]);
    }
}

// Driver Code
int main()
{

    int n = 6;

    vector<int> a(n);

    a = {7, 1, 4, 6, 9, 3};

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

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

    cout << endl;

    rearrangeArray(a);

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

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

    cout << endl;
}

 

Input

The array before rearranging elements is:  7 1 4 6 9 3 

 

Output

The array after rearranging elements is: 1 6 4 7 3 9

 

Algorithm Complexity 

Time Complexity: O(N*log(N))

Since we are sorting the array, sorting is performed in O(N*log(N)) time complexity. Therefore the time complexity would be O(N*log(N)).

Space Complexity: O(1)

Since we are not using extra space to store the new rearranged array, the space complexity is O(1).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

 

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 -

You can also refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingSystem 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 problemsinterview 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.

Previous article
Rearrange positive and negative using the inbuilt sort function
Next article
Rearrange array such that arr[i] >= arr[j] if "i" is even and arr[i]<=arr[j] if "i" is odd and j < i
Live masterclass