Rearrange Positive and Negative Numbers Alternatively

📚 In this tutorial, you will learn:

What is alternating positive and negative array rearrangement
Different approaches to rearrange numbers
Using two-pointer technique
In-place rearrangement with O(1) extra space
Time and space complexity analysis

Introduction to Alternating Arrangement

The alternating positive and negative numbers problem requires rearranging an array so that positive and negative numbers appear in alternating order, starting with either positive or negative. For example, [-1, 2, -3, 4, -5, 6] is an alternating arrangement.

Key characteristics:

Alternating pattern: Positive, Negative, Positive, Negative, ...
Order preservation: May or may not preserve original order
Extra space: Can be done with or without extra memory
Applications: Signal processing, data organization, algorithm design

💡 Example: For array [1, -2, 3, -4, 5, -6], the arrangement is already alternating. For [-1, 2, -3, 4, -5, 6], it's also alternating starting with negative.

C Program to Rearrange Numbers Alternatively

#include <stdio.h>
#include <stdlib.h>

// Function to swap two elements
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Approach 1: Using separate arrays (extra space)
void rearrangeWithExtraSpace(int arr[], int n) {
    int *positive = (int *)malloc(n * sizeof(int));
    int *negative = (int *)malloc(n * sizeof(int));
    int posCount = 0, negCount = 0;
    
    // Separate positive and negative numbers
    for (int i = 0; i < n; i++) {
        if (arr[i] >= 0) {
            positive[posCount++] = arr[i];
        } else {
            negative[negCount++] = arr[i];
        }
    }
    
    // Merge alternatively starting with positive
    int i = 0, j = 0, k = 0;
    while (i < posCount && j < negCount) {
        arr[k++] = positive[i++];
        arr[k++] = negative[j++];
    }
    
    // Copy remaining elements if any
    while (i < posCount) {
        arr[k++] = positive[i++];
    }
    while (j < negCount) {
        arr[k++] = negative[j++];
    }
    
    free(positive);
    free(negative);
}

// Approach 2: In-place rearrangement using two-pointer technique
void rearrangeInPlace(int arr[], int n) {
    // First, separate positive and negative numbers
    int j = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] < 0) {
            if (i != j) {
                swap(&arr[i], &arr[j]);
            }
            j++;
        }
    }
    
    // j is the index where negative numbers end
    int negPos = 0;
    int posPos = j;
    
    // Swap positive and negative alternately
    while (negPos < j && posPos < n && arr[negPos] < 0) {
        swap(&arr[negPos], &arr[posPos]);
        negPos += 2;
        posPos++;
    }
}

// Approach 3: Using rotation technique (preserves order)
void rotateArray(int arr[], int start, int end) {
    int temp = arr[end];
    for (int i = end; i > start; i--) {
        arr[i] = arr[i - 1];
    }
    arr[start] = temp;
}

void rearrangePreservingOrder(int arr[], int n) {
    // Strategy: For each position, find the right element and rotate
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            // Even index: should be positive
            if (arr[i] < 0) {
                // Find next positive element
                int j = i + 1;
                while (j < n && arr[j] < 0) {
                    j++;
                }
                if (j < n) {
                    rotateArray(arr, i, j);
                }
            }
        } else {
            // Odd index: should be negative
            if (arr[i] >= 0) {
                // Find next negative element
                int j = i + 1;
                while (j < n && arr[j] >= 0) {
                    j++;
                }
                if (j < n) {
                    rotateArray(arr, i, j);
                }
            }
        }
    }
}

// Function to print the array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Function to check if arrangement is alternating
int isAlternating(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        if ((arr[i] >= 0 && arr[i + 1] >= 0) || (arr[i] < 0 && arr[i + 1] < 0)) {
            return 0;
        }
    }
    return 1;
}

// Driver program to test rearrangement
int main() {
    int arr1[] = {1, 2, 3, -4, -5, -6, 7, -8, 9, -10};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    
    printf("Original array: ");
    printArray(arr1, n1);
    
    // Test Approach 1: Extra space
    int *arr1Copy1 = (int *)malloc(n1 * sizeof(int));
    for (int i = 0; i < n1; i++) arr1Copy1[i] = arr1[i];
    rearrangeWithExtraSpace(arr1Copy1, n1);
    printf("Using extra space: ");
    printArray(arr1Copy1, n1);
    printf("Alternating? %s\n\n", isAlternating(arr1Copy1, n1) ? "Yes" : "No");
    free(arr1Copy1);
    
    // Test Approach 2: In-place
    int *arr1Copy2 = (int *)malloc(n1 * sizeof(int));
    for (int i = 0; i < n1; i++) arr1Copy2[i] = arr1[i];
    rearrangeInPlace(arr1Copy2, n1);
    printf("In-place (no order preservation): ");
    printArray(arr1Copy2, n1);
    printf("Alternating? %s\n\n", isAlternating(arr1Copy2, n1) ? "Yes" : "No");
    free(arr1Copy2);
    
    // Test Approach 3: Preserving order
    int *arr1Copy3 = (int *)malloc(n1 * sizeof(int));
    for (int i = 0; i < n1; i++) arr1Copy3[i] = arr1[i];
    rearrangePreservingOrder(arr1Copy3, n1);
    printf("Preserving order (using rotation): ");
    printArray(arr1Copy3, n1);
    printf("Alternating? %s\n\n", isAlternating(arr1Copy3, n1) ? "Yes" : "No");
    free(arr1Copy3);
    
    // Test with equal positives and negatives
    int arr2[] = {-1, 2, -3, 4, -5, 6};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    printf("Original: ");
    printArray(arr2, n2);
    
    int *arr2Copy = (int *)malloc(n2 * sizeof(int));
    for (int i = 0; i < n2; i++) arr2Copy[i] = arr2[i];
    rearrangeInPlace(arr2Copy, n2);
    printf("After in-place: ");
    printArray(arr2Copy, n2);
    free(arr2Copy);
    
    // Test with all positives or all negatives
    int arr3[] = {1, 2, 3, 4, 5};
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
    printf("\nArray with all positives: ");
    printArray(arr3, n3);
    
    int *arr3Copy = (int *)malloc(n3 * sizeof(int));
    for (int i = 0; i < n3; i++) arr3Copy[i] = arr3[i];
    rearrangeInPlace(arr3Copy, n3);
    printf("After rearrangement: ");
    printArray(arr3Copy, n3);
    free(arr3Copy);
    
    return 0;
}

Sample Output

Original array: 1 2 3 -4 -5 -6 7 -8 9 -10 
Using extra space: 1 -4 2 -5 3 -6 7 -8 9 -10 
Alternating? Yes

In-place (no order preservation): -4 -5 -6 1 2 3 7 -8 9 -10 
Alternating? No

Preserving order (using rotation): 1 -4 2 -5 3 -6 7 -8 9 -10 
Alternating? Yes

Original: -1 2 -3 4 -5 6 
After in-place: -1 2 -3 4 -5 6 

Array with all positives: 1 2 3 4 5 
After rearrangement: 1 2 3 4 5

Program Explanation

The program demonstrates three different approaches:

Using Extra Space (O(n) time, O(n) space):
- Separates positive and negative numbers into two arrays
- Merges them alternatively
- Preserves original order within each group
- Simple but uses extra memory
In-place Using Two-Pointer (O(n) time, O(1) space):
- First separates positives and negatives in the array
- Then swaps elements to create alternating pattern
- Does not preserve original order
- Most memory efficient
Using Rotation Technique (O(n²) time, O(1) space):
- Finds the right element for each position and rotates
- Preserves the original order of elements
- Less efficient but maintains order

Step-by-Step Approach for In-Place Rearrangement

Step	Action	Explanation
1	Separate	Move all negative numbers to the left side
2	Two Pointers	Set negPos at start and posPos at first positive
3	Swap Alternately	Swap elements to create alternating pattern
4	Repeat	Continue until all elements are processed

Algorithm for In-Place Rearrangement

Separate: Move all negative numbers to the left of the array
Initialize: Set negPos = 0, posPos = index of first positive
Swap: While negPos < number of negatives and posPos < n:
- Swap arr[negPos] and arr[posPos]
- negPos += 2, posPos++
Done: Array is now alternating

Time & Space Complexity

Approach	Time Complexity	Space Complexity	Order Preserved
Extra Space	O(n)	O(n)	✅ Yes
In-place	O(n)	O(1)	❌ No
Rotation	O(n²)	O(1)	✅ Yes

📊 Recommendation:

If order doesn't matter: Use the two-pointer in-place approach (O(n) time, O(1) space)
If order matters: Use the extra space approach (O(n) time, O(n) space)
If memory is a constraint and order matters: Use the rotation approach (O(n²) time, O(1) space)

💻 Practice Exercise

Challenge 1: Modify the program to rearrange numbers starting with a negative number.

Challenge 2: Implement an O(n) solution that preserves the original order of numbers.

Challenge 3: Rearrange the array so that all negative numbers come before positives (segregation) first.

🔍 Click to Show Solution for Challenge 1

// To start with negative, swap the merge order
void rearrangeStartNegative(int arr[], int n) {
    int *positive = (int *)malloc(n * sizeof(int));
    int *negative = (int *)malloc(n * sizeof(int));
    int posCount = 0, negCount = 0;
    
    for (int i = 0; i < n; i++) {
        if (arr[i] >= 0) positive[posCount++] = arr[i];
        else negative[negCount++] = arr[i];
    }
    
    int i = 0, j = 0, k = 0;
    // Start with negative
    while (i < posCount && j < negCount) {
        arr[k++] = negative[j++];
        arr[k++] = positive[i++];
    }
    
    while (i < posCount) arr[k++] = positive[i++];
    while (j < negCount) arr[k++] = negative[j++];
    
    free(positive);
    free(negative);
}

Frequently Asked Questions

1. What happens if there are unequal numbers of positive and negative elements?

If counts are unequal, the extra elements are appended at the end. For example, if there are more positives than negatives, the remaining positives are placed after the alternating pattern.

2. Does this algorithm preserve the original order?

The extra space approach preserves order, and the rotation approach also preserves order. However, the simple two-pointer in-place approach does not preserve the original order of elements.

3. What is the most efficient approach?

The two-pointer approach (O(n) time, O(1) space) is most efficient in terms of space, but it doesn't preserve order. If order preservation is required, the extra space approach (O(n) time, O(n) space) is the best choice.

4. Can this algorithm handle zero?

Yes, in this implementation, zero is treated as positive (arr[i] >= 0). You can change this behavior by using arr[i] > 0 for strictly positive numbers.

5. What are the real-world applications of this problem?

This problem is used in signal processing (alternating signals), data organization (separating different types of data), and algorithm design (partitioning problems).

💡 Pro Tip: This problem is a classic interview question that tests your understanding of array manipulation, in-place algorithms, and partition techniques.

📖 Related Array Assignments

💡 Tip: Practice these assignments in order, starting from basic to advanced. Each problem builds upon concepts from previous ones.

Previous Topic: -->> Delete Duplicate Elements in C || Next topic: -->> Equilibrium Index in C

38. Rearrange Positive and Negative Numbers Alternatively in C