Python – Rearrange an Array in Alternating Positive and Negative Order with O(1) Extra Space

This tutorial explains how to rearrange an array so that positive and negative numbers appear in alternating order using O(1) extra space. We will go through the problem statement, sample inputs/outputs, solution approach, and the complete Python program.

Problem Statement

Given an array containing both positive and negative integers, rearrange the array such that the elements appear in alternating positive and negative order. If extra positive or negative elements remain, they should appear at the end of the array. The rearrangement must be done in-place with O(1) extra space.

Sample Input and Output

Example 1:

</>
Copy
Input:  arr = [2, 3, -4, -1, 6, -9]
Output: [2, -4, 3, -1, 6, -9]

Example 2:

</>
Copy
Input:  arr = [1, -2, -3, 4, 5, 6, -7, -8]
Output: [1, -2, 4, -3, 5, -7, 6, -8]

Solution Approach

The problem can be solved in the following steps:

  1. Partition the Array: Rearrange the array so that all negative numbers are grouped together and all positive numbers are grouped together. This is similar to the partition step in QuickSort.
  2. Initialize Pointers: Let neg be the index starting from the first element and pos be the index where positive numbers start (after partitioning).
  3. Alternate Swap: Swap elements at the neg index with elements at the pos index to place them in alternating order. Increment neg by 2 (to skip to the next negative slot) and pos by 1 after each swap.
  4. Handle Extra Elements: If one type (positive or negative) exceeds the other, the remaining elements will stay at the end of the array.

Python Program

</>
Copy
def rearrange_alternating(arr):
    n = len(arr)
    
    # Step 1: Partition the array so that negatives are on the left and positives on the right.
    j = 0  # index for the position of the next negative element
    for i in range(n):
        if arr[i] < 0:
            arr[i], arr[j] = arr[j], arr[i]
            j += 1
    # At this point, arr[0:j] are negative and arr[j:] are positive.
    
    # Step 2: Initialize pointers for negative and positive elements.
    neg, pos = 0, j
    
    # Step 3: Swap elements to arrange them in alternating order.
    # Swap negative elements at even positions with positive elements.
    while pos < n and neg < pos and arr[neg] < 0:
        arr[neg], arr[pos] = arr[pos], arr[neg]
        pos += 1
        neg += 2  # move to the next position for a negative number
        
    return arr

# Testing the function with Example 1
arr1 = [2, 3, -4, -1, 6, -9]
print("Rearranged Array (Example 1):", rearrange_alternating(arr1))

# Testing the function with Example 2
arr2 = [1, -2, -3, 4, 5, 6, -7, -8]
print("Rearranged Array (Example 2):", rearrange_alternating(arr2))

Conclusion

In this tutorial, we learned how to rearrange an array in alternating positive and negative order using O(1) extra space. The solution involves partitioning the array, then swapping elements to achieve the alternating pattern. This in-place approach is efficient and a common topic in technical interviews.