Positive elements at even and negative at odd positions

Optimal Approach - 1 

This approach will be better than the brute force approach in terms of time complexity; the time complexity of the above approach is O(N log(N)) whereas, in this approach, the time complexity would be O(N), and the space complexity will be O(1). 

Algorithm

1. Take two-pointers Even = 0 and odd = 1 as the initial values for two-pointers.
2. Iterate through the array's elements from index=0 to the last element i.e., while it is true, and stop if it gets out of range.
3. Increase the even pointer by 2 if the element at the even index is even or zero.
4. Increase the odd pointer by 2 if the element at the odd index is odd or zero.
5. Swap the items and increase both pointers by two if the element at the even index is odd and the element at the odd index is even.
6. For swapping, we'll utilize a built-in C++ method. If you desire, you can create your own swap function.
7. At the end of the loop, you will get the desired result.

In the C++ code below, we will make a separate function for rearrangement of the array for better understanding.

Implementation in C++

// including header files
#include <bits/stdc++.h>
using namespace std;

// function in which rearrangement of the array will be done
void solve(int arr[], int n)
{
    // initilize even and odd pointer
    int even = 0, odd = 1;

    for (even, odd; even < n && odd < n;)
    {
        // check for positive at even positions
        while (even < n && arr[even] >= 0)
            even += 2;

        // check for negative at odd positions
        while (odd < n && arr[odd] <= 0)
            odd += 2;

        // Swap elements
        if (even < n && odd < n)
            swap(arr[even], arr[odd]);
    }
}

int main()
{
    // taking input for the size of array
    int n;
    cin >> n;
    cout<<"The size of the array:";
    cout<<n<<endl;
    // initializing and taking input for the array.
    int a[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    cout<<"The array elements before rearrangement: ";    
    for (int i = 0; i < n; i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    // calling our solve function
    solve(a, n);
    cout<<"The array elements after rearrangement: ";
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout<<endl;

    return 0;
}

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

Run Code

Input

n=6, arr[]={1, 2, 3, -1, -2, -3}

Output 

The size of the array: 6
The array elements before rearrangement: 1 2 3 -1 -2 -3
The array elements after rearrangement:  1 -2 3 -1 2 -3

Complexity analysis

Time complexity
The time complexity is O(N), where n is the size of the array as we traverse the array only one time to swap the elements if needed.

Space complexity
O(1) will be the space complexity as we have taken only two pointers to traverse the array and haven't used any other data structure.

Also see, Morris Traversal for Inorder.

Optimal Approach-2

The aim is to discover a positive/negative element that is in the wrong place, then find the opposite sign element in the remaining array that is likewise in the wrong place, and then swap these two elements. The expected time complexity will be O(N), and space complexity will be O(1).

Algorithm

1. We take the input for the size of the array and elements of the array.
2. We make a void demo function for rearrangement of the array.
3. We make a SwapValue function to swap two numbers.
4. We loop through the array and check if the array element is positive or negative.
5. If it is positive and the index is an odd swap for the next negative and vice versa.
6. At the end of the loop, you will get the desired result.

Implementation in C++

// including header files
#include <bits/stdc++.h>
#include <cmath>
using namespace std;

// function to swap the misplaced elements
void swapValue(int *arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    return;
}

// function to print the array elements
void demo(int *arr, int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    return;
}

int main()
{ 
// initializing and taking input for no of elements.
    int n;
    cin >> n;
    cout << "The size of the array:"
         << " " << n << endl;
    // initializing and taking input for the array.
    int arr[n];
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    // printing array before modification
    cout << "The array elements before rearrangement: ";
    demo(arr, n);
    for (int i = 0; i < n; i++)
    { // checking for correct placement of positive elements
        if (arr[i] >= 0 && i % 2 == 1)
        {

            for (int j = i + 1; j < n; j++)
            {
                if (arr[j] < 0 && j % 2 == 0)
                {
                    // swapping the misplaced elements
                    swapValue(arr, i, j);
                    break;
                }
            }
        }
        else if (arr[i] < 0 && i % 2 == 0)
        {
            // checking for correct placement of negative elements
            for (int j = i + 1; j < n; j++)
            {
                if (arr[j] >= 0 && j % 2 == 1)
                {
                    // swapping the misplaced elements
                    swapValue(arr, i, j);
                    break;
                }
            }
        }
    }

    cout << "The array elements after rearrangement: ";
    demo(arr, n);
    return 0;
}

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

Run Code

Input

n=8, arr[]={9, 3, 4, -3, -8, -9, -3, 5}

Output

No of elements in array: 8
Array before modification : 9 3 4 -3 -8 -9 -3 5 
Array after modification: 9 -8 4 -3 3 -9 5 -3

Complexity analysis

Time complexity 
The time complexity is O(N), where n is the size of the array as we traverse the array only one time to check for all positive and negative numbers.

Space complexity
O(1) will be the space complexity as we have only traversed the array and haven't used any extra array.

Frequently Asked Questions

Define an array.

An array is a collection of similar data types stored in contiguous memory spaces. When declaring an array, the type of data must be specified together with the array name. The index of different elements in an array can be used to access them.

What is the time complexity of swapping two elements in an array?

It takes a constant time complexity to swap two elements of an array. We just maintain a temp variable to swap the elements and no loop is taken in action.

Why do we need arrays in C++?

Instead of defining distinct variables for each item, arrays are used to hold numerous values in a single variable.

Conclusion

In this article, we have analyzed how to rearrange an array such that positive elements are placed at even and negative at odd positions. We have gone through three different approaches to solving the problem; we have also discussed their algorithm, C++ code, and also their space and time complexity.

After reading about the array rearrangement, are you not feeling excited to read/explore more articles on the topic of array and data structures and algorithms? Don't worry; Coding Ninjas has you covered. To learn, see Data Structures and Algorithms, Competitive Programming.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Operating System, Unix File System, File System Routing, File Input/Output., JavaScript, 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 suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, 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 Learning!