Rearrange Array Alternately with Positive and Negative Elements Optimal Approach

Arrays

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given an array of integers that contains both positive and negative numbers, your task is to rearrange the elements so that they appear in an alternating order of positive and negative values, starting with a positive number.

  • If there are extra positive or negative numbers, place them at the end of the array.
  • The relative order of elements is not required to be preserved.

If the array is empty or has only one type of number (only positive or only negative), it should be returned as-is.

Examples❯

Input Array Rearranged Output Description
[1, 2, -3, -4, 5, -6] [1, -3, 2, -4, 5, -6] Alternating positive and negative, starting with positiveVisualization
[-1, 2, -3, 4, -5, 6] [2, -1, 4, -3, 6, -5] Signs alternate starting with positive, values rearrangedVisualization
[1, 2, 3, 4] [1, 2, 3, 4] Only positive numbers, no rearrangement neededVisualization
[-1, -2, -3, -4] [-1, -2, -3, -4] Only negative numbers, no rearrangement neededVisualization
[1] [1] Single element array, returned as-isVisualization
[-1] [-1] Single negative number, returned as-isVisualization
[] [] Empty array, output is also emptyVisualization
[1, -2, 3, -4, 5, -6, 7] [1, -2, 3, -4, 5, -6, 7] One extra positive number at the endVisualization
[1, -2, -3, -4] [1, -2, -3, -4] More negatives than positives; remaining negatives stay at endVisualization

Solution❯

Understanding the Problem

We are given an array of integers containing both positive and negative numbers. Our task is to rearrange this array so that the signs alternate: starting with a positive number, then a negative number, then a positive again, and so on.

There are a few key constraints to keep in mind:

  • The rearrangement must happen in-place (without using extra arrays).
  • The relative order of elements is not important.
  • If one type (positive or negative) runs out before the other, the rest can remain at the end.

Approach: Step-by-Step Strategy

Step 1: Think in Terms of Index Positions

We’ll solve this using a two-pointer technique:

  • posIndex will point to even indices (0, 2, 4, ...) where positive numbers should go.
  • negIndex will point to odd indices (1, 3, 5, ...) where negative numbers should go.

We iterate through the array, and whenever we find a number at the wrong position based on its sign, we swap it with the correct index. After placing a number, we move the respective index forward by 2.

Step 2: Use an Example to Understand

Let’s take an example array:

[3, -2, 1, -7, -5, 6]

We want to rearrange this to something like:

[3, -2, 1, -7, 6, -5]

Notice how the signs alternate: positive, negative, positive, negative...

Step 3: Rearranging the Array

We go through the array, check each number’s sign, and place it at the correct posIndex or negIndex if needed. Swapping is allowed and we keep moving the pointers forward by 2.

Edge Cases and How We Handle Them

Case 1: Normal Case (Balanced Positives and Negatives)

This is the ideal case where we have an almost equal number of positive and negative numbers. Our strategy will produce a clean alternation of signs.

Case 2: Unequal Count

If we have more positives than negatives (or vice versa), then once we run out of the smaller group, the extra elements from the larger group are left at the end. This is acceptable based on the problem statement.

Case 3: All Positive or All Negative

There’s no way to alternate if we have all numbers of the same sign. So, we simply return the array as-is without making any changes.

Case 4: Empty Array

No elements to rearrange. We return an empty array.

Case 5: Single Element

With only one number (positive or negative), there’s nothing to alternate with. So, we return the array unchanged.

Algorithm Steps❯

  1. Given an array arr of integers containing both positive and negative numbers.
  2. We want to rearrange it such that the signs alternate, starting with a positive number.
  3. Initialize posIndex = 0 and negIndex = 1.
  4. Traverse the array once. For every positive element found at the wrong position (odd index), place it at posIndex and increment posIndex by 2.
  5. For every negative element found at the wrong position (even index), place it at negIndex and increment negIndex by 2.
  6. Repeat the process until both indices exceed the array length.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

void rearrangeAlternatingOptimal(int arr[], int n) {
    int result[n];
    int pos = 0, neg = 1;
    for (int i = 0; i < n; i++) {
        if (arr[i] >= 0 && pos < n) result[pos] = arr[i], pos += 2;
        else if (arr[i] < 0 && neg < n) result[neg] = arr[i], neg += 2;
    }
    printf("Rearranged Array: ");
    for (int i = 0; i < n; i++) printf("%d ", result[i]);
    printf("\n");
}

int main() {
    int arr[] = {1, 2, 3, -4, -1, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    rearrangeAlternatingOptimal(arr, n);
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)In the best case, where the array is already alternating with correct signs at correct indices, we still traverse the array once to validate, resulting in linear time.
Average CaseO(n)Each element in the array is visited once during the traversal to place it in the correct position, ensuring a single-pass solution.
Worst CaseO(n)Regardless of the initial arrangement of positive and negative numbers, the array is traversed once and elements are moved in constant time per element.

Space Complexity❯

O(n)

Explanation: Although the algorithm is optimal in time, it creates a new array to store elements in the correct alternating order, requiring space proportional to the input size.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...