ArrayProblem 20 of 36

Rearrange the array in alternating positive and negative items with O(1) extra space

Brute Force
Time: O(n²)
Space: O(n)
Optimal
Time: O(n)
Space: O(1)

Problem Statement

Given an array containing both positive and negative integers, rearrange it so that positive and negative numbers are placed alternately. If there are more positive or negative numbers, place them at the end.

Example:

  • Input: [1, 2, 3, -4, -1, 4]
  • Output: [-4, 1, -1, 2, 3, 4] or [-1, 1, -4, 2, 3, 4]
  • Explanation: Negative and positive numbers alternate, extra positives at end

Approach 1: Using Extra Space

Intuition

Separate positive and negative numbers into different arrays, then merge them alternately.

Algorithm

  1. Separate positives and negatives into two arrays
  2. Merge them alternately into the result
  3. Append remaining elements
java
import java.util.*;

public class Solution {
    public int[] rearrangeWithExtraSpace(int[] arr) {
        List<Integer> positives = new ArrayList<>();
        List<Integer> negatives = new ArrayList<>();
        
        // Separate positives and negatives
        for (int num : arr) {
            if (num >= 0) {
                positives.add(num);
            } else {
                negatives.add(num);
            }
        }
        
        int[] result = new int[arr.length];
        int i = 0, j = 0, k = 0;
        boolean placeNegative = true;  // Start with negative
        
        // Alternate between negatives and positives
        while (i < negatives.size() && j < positives.size()) {
            if (placeNegative) {
                result[k++] = negatives.get(i++);
            } else {
                result[k++] = positives.get(j++);
            }
            placeNegative = !placeNegative;
        }
        
        // Append remaining elements
        while (i < negatives.size()) {
            result[k++] = negatives.get(i++);
        }
        while (j < positives.size()) {
            result[k++] = positives.get(j++);
        }
        
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Two passes through the array
  • Space Complexity: O(n) - Extra arrays for positives and negatives

Approach 2: In-Place with O(1) Extra Space (Optimal)

Intuition

Use rotation to place elements in their correct positions. For each wrong position, find the correct element and rotate the subarray.

Algorithm

  1. Traverse the array
  2. At each position, check if we need positive or negative
  3. If wrong element is present, find the next correct element and rotate
java
public class Solution {
    private void rightRotate(int[] arr, int start, int end) {
        int last = arr[end];
        for (int i = end; i > start; i--) {
            arr[i] = arr[i - 1];
        }
        arr[start] = last;
    }
    
    public void rearrangeInPlace(int[] arr) {
        int n = arr.length;
        
        for (int i = 0; i < n; i++) {
            // At even index, we want negative
            // At odd index, we want positive
            if (i % 2 == 0) {
                // Need negative at even index
                if (arr[i] >= 0) {
                    // Find next negative
                    int j = i + 1;
                    while (j < n && arr[j] >= 0) {
                        j++;
                    }
                    // If no negative found, all remaining are positive
                    if (j >= n) break;
                    // Rotate to bring negative to position i
                    rightRotate(arr, i, j);
                }
            } else {
                // Need positive at odd index
                if (arr[i] < 0) {
                    // Find next positive
                    int j = i + 1;
                    while (j < n && arr[j] < 0) {
                        j++;
                    }
                    // If no positive found, all remaining are negative
                    if (j >= n) break;
                    // Rotate to bring positive to position i
                    rightRotate(arr, i, j);
                }
            }
        }
    }
}

Complexity Analysis

  • Time Complexity: O(n²) - In worst case, rotation takes O(n) for each position
  • Space Complexity: O(1) - In-place rearrangement

Approach 3: Optimized In-Place (Using Quick Sort Partition)

Intuition

First partition the array so all negatives come before positives, then rearrange by swapping elements.

java
public class Solution {
    public void rearrangeOptimized(int[] arr) {
        int n = arr.length;
        
        // Step 1: Move all negative numbers to the beginning
        int negIndex = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] < 0) {
                int temp = arr[i];
                arr[i] = arr[negIndex];
                arr[negIndex] = temp;
                negIndex++;
            }
        }
        
        // Step 2: Swap alternate negatives with positives
        int pos = negIndex;  // First positive index
        int neg = 0;         // First negative index
        
        while (neg < pos && pos < n && neg % 2 == 0) {
            int temp = arr[neg];
            arr[neg] = arr[pos];
            arr[pos] = temp;
            neg += 2;
            pos++;
        }
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Two passes through the array
  • Space Complexity: O(1) - In-place operations

Key Takeaways

  1. Rotation-based approach maintains relative order but is O(n²)
  2. Partition + Swap is O(n) but may not maintain relative order
  3. Choose based on requirements: order preservation vs. efficiency
  4. The key insight is treating even indices for negatives, odd for positives
  5. Edge cases:
    • All positives or all negatives
    • More positives than negatives or vice versa
  6. Similar technique used in: Dutch National Flag, segregating 0s and 1s
Previous
Find common elements In 3 sorted arrays
Next
Find if there is any subarray with sum equal to 0