Rearrange Array Alternating Positive and Negative Elements

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.

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.

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.

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

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

vector<int> rearrangeAlternatingOptimal(const vector<int>& arr) {
    int n = arr.size();
    vector<int> result(n);
    int pos = 0, neg = 1;
    for (int num : arr) {
        if (num >= 0 && pos < n) result[pos] = num, pos += 2;
        else if (num < 0 && neg < n) result[neg] = num, neg += 2;
    }
    return result;
}

int main() {
    vector<int> arr = {1, 2, 3, -4, -1, 4};
    vector<int> res = rearrangeAlternatingOptimal(arr);
    cout << "Rearranged Array: ";
    for (int num : res) cout << num << " ";
    cout << endl;
    return 0;
}

def rearrange_alternating_optimal(arr):
    n = len(arr)
    result = [0] * n
    pos_index, neg_index = 0, 1
    for num in arr:
        if num >= 0 and pos_index < n:
            result[pos_index] = num
            pos_index += 2
        elif num < 0 and neg_index < n:
            result[neg_index] = num
            neg_index += 2
    return result

arr = [1, 2, 3, -4, -1, 4]
print("Rearranged Array:", rearrange_alternating_optimal(arr))

public class RearrangeAlternatingOptimal {
    public static int[] rearrange(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        int pos = 0, neg = 1;
        for (int num : arr) {
            if (num >= 0 && pos < n) {
                result[pos] = num;
                pos += 2;
            } else if (num < 0 && neg < n) {
                result[neg] = num;
                neg += 2;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, -4, -1, 4};
        int[] res = rearrange(arr);
        System.out.print("Rearranged Array: ");
        for (int num : res) System.out.print(num + " ");
        System.out.println();
    }
}

function rearrangeAlternatingOptimal(arr) {
    const n = arr.length;
    const result = new Array(n);
    let pos = 0, neg = 1;
    for (let 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;
        }
    }
    return result;
}

const arr = [1, 2, 3, -4, -1, 4];
console.log("Rearranged Array:", rearrangeAlternatingOptimal(arr));

package main
import "fmt"

func rearrangeAlternatingOptimal(arr []int) []int {
    n := len(arr)
    result := make([]int, n)
    pos, neg := 0, 1
    for _, num := range arr {
        if num >= 0 && pos < n {
            result[pos] = num
            pos += 2
        } else if num < 0 && neg < n {
            result[neg] = num
            neg += 2
        }
    }
    return result
}

func main() {
    arr := []int{1, 2, 3, -4, -1, 4}
    res := rearrangeAlternatingOptimal(arr)
    fmt.Print("Rearranged Array: ")
    for _, num := range res {
        fmt.Printf("%d ", num)
    }
    fmt.Println()
}

fn rearrange_alternating_optimal(arr: Vec<i32>) -> Vec<i32> {
    let n = arr.len();
    let mut result = vec![0; n];
    let (mut pos, mut neg) = (0, 1);
    for &num in &arr {
        if num >= 0 && pos < n {
            result[pos] = num;
            pos += 2;
        } else if num < 0 && neg < n {
            result[neg] = num;
            neg += 2;
        }
    }
    result
}

fn main() {
    let arr = vec![1, 2, 3, -4, -1, 4];
    let res = rearrange_alternating_optimal(arr);
    print!("Rearranged Array: ");
    for num in res {
        print!("{} ", num);
    }
    println!();
}

fun rearrangeAlternatingOptimal(arr: IntArray): IntArray {
    val n = arr.size
    val result = IntArray(n)
    var pos = 0
    var neg = 1
    for (num in arr) {
        if (num >= 0 && pos < n) {
            result[pos] = num
            pos += 2
        } else if (num < 0 && neg < n) {
            result[neg] = num
            neg += 2
        }
    }
    return result
}

fun main() {
    val arr = intArrayOf(1, 2, 3, -4, -1, 4)
    val res = rearrangeAlternatingOptimal(arr)
    print("Rearranged Array: ")
    for (num in res) print("$num ")
    println()
}

func rearrangeAlternatingOptimal(_ arr: [Int]) -> [Int] {
    var result = Array(repeating: 0, count: arr.count)
    var pos = 0, neg = 1
    for num in arr {
        if num >= 0 && pos < arr.count {
            result[pos] = num
            pos += 2
        } else if num < 0 && neg < arr.count {
            result[neg] = num
            neg += 2
        }
    }
    return result
}

let arr = [1, 2, 3, -4, -1, 4]
let res = rearrangeAlternatingOptimal(arr)
print("Rearranged Array:", res)

function rearrangeAlternatingOptimal(arr: number[]): number[] {
    const n = arr.length;
    const result: number[] = new Array(n);
    let pos = 0, neg = 1;
    for (let 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;
        }
    }
    return result;
}

const arr: number[] = [1, 2, 3, -4, -1, 4];
console.log("Rearranged Array:", rearrangeAlternatingOptimal(arr));

Time complexity

Space complexity

O(n)

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.