Problem

Given an array, rearrange it so that all positive numbers are on one side and all negative numbers are on the other side, without changing the relative order of the positive and negative numbers.

Examples

Example 1:

1
2

Input: nums = [1, -2, 3, -4, -1, 4]
Output: [1, 3, 4, -2, -4, -1]

Example 2:

1
2

Input: nums = [-5, 2, -3, 1, -8, 6]
Output: [2, 1, 6, -5, -3, -8]

Solution

Method 1 - Use positive and negative lists

Here is the approach:

  1. Two-pass Algorithm:
    • Perform the rearrangement in two passes.
  2. Separate Positive and Negative Numbers:
    • Use two arrays or lists to separately store the positive and negative numbers during the first pass.
  3. Combine Arrays:
    • In the second pass, combine both arrays by appending all positive numbers first, followed by all negative numbers

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

public class Solution {
    public int[] rearrangePosNeg(int[] nums) {
        List<Integer> positives = new ArrayList<>();
        List<Integer> negatives = new ArrayList<>();

        // Separate positive and negative numbers
        for (int num : nums) {
            if (num >= 0) {
                positives.add(num);
            } else {
                negatives.add(num);
            }
        }

        // Combine positive and negative numbers, maintaining order
        int index = 0;
        for (int pos : positives) {
            nums[index++] = pos;
        }
        for (int neg : negatives) {
            nums[index++] = neg;
        }

        return nums;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums1 = {1, -2, 3, -4, -1, 4};
        int[] result1 = sol.rearrangePosNeg(nums1);
        System.out.println("Rearranged array: " + Arrays.toString(result1));  // Expected output: [1, 3, 4, -2, -4, -1]

        int[] nums2 = {-5, 2, -3, 1, -8, 6};
        int[] result2 = sol.rearrangePosNeg(nums2);
        System.out.println("Rearranged array: " + Arrays.toString(result2));  // Expected output: [2, 1, 6, -5, -3, -8]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

from typing import List

class Solution:
    def rearrangePosNeg(self, nums: List[int]) -> List[int]:
        positives = []
        negatives = []

        # Separate positive and negative numbers
        for num in nums:
            if num >= 0:
                positives.append(num)
            else:
                negatives.append(num)

        # Combine positive and negative numbers, maintaining order
        result = positives + negatives
        return result

# Example usage
sol = Solution()
nums1 = [1, -2, 3, -4, -1, 4]
result1 = sol.rearrangePosNeg(nums1)
print("Rearranged array:", result1)  # Expected output: [1, 3, 4, -2, -4, -1]

nums2 = [-5, 2, -3, 1, -8, 6]
result2 = sol.rearrangePosNeg(nums2)
print("Rearranged array:", result2)  # Expected output: [2, 1, 6, -5, -3, -8]

Complexity

  • ⏰ Time complexity: O(n), where n is the number of elements in the array, since we traverse the array two times.
  • 🧺 Space complexity: O(n), for storing the separated positive and negative numbers in auxiliary arrays or lists.

Method 2 - Divide and Conquer

This approach resembles merge sort. Divide the array into two halves, solve each half individually, and then merge them. The merging step is tricky. Here’s the logic for merging (negative numbers on the left and positives on the right):

  • Traverse the left half of the array until you find a positive integer, then reverse the array after that point (calling this part ‘A’).
  • Traverse the right half of the array until you find a positive integer, then reverse the array before that point (calling this part ‘B’).
  • Finally, reverse both parts ‘A’ and ‘B’. Refer to the example for a better understanding.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

public class Solution {

    public void rearrangePosNeg(int[] nums) {
        rearrange(nums, 0, nums.length - 1);
    }

    private void rearrange(int[] nums, int left, int right) {
        if (left >= right) return;
        
        int mid = left + (right - left) / 2;

        rearrange(nums, left, mid);
        rearrange(nums, mid + 1, right);

        merge(nums, left, mid, right);
    }

    private void merge(int[] nums, int left, int mid, int right) {
        int i = left;
        while (i <= mid && nums[i] < 0) i++;
        
        int j = mid + 1;
        while (j <= right && nums[j] < 0) j++;
        
        reverse(nums, i, mid);
        reverse(nums, mid + 1, j - 1);
        reverse(nums, i, j - 1);
    }

    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution:
    def rearrangePosNeg(self, nums: List[int]) -> None:
        self.rearrange(nums, 0, len(nums) - 1)

    def rearrange(self, nums: List[int], left: int, right: int) -> None:
        if left >= right:
            return

        mid = left + (right - left) // 2

        self.rearrange(nums, left, mid)
        self.rearrange(nums, mid + 1, right)

        self.merge(nums, left, mid, right)

    def merge(self, nums: List[int], left: int, mid: int, right: int) -> None:
        i = left
        while i <= mid and nums[i] < 0:
            i += 1

        j = mid + 1
        while j <= right and nums[j] < 0:
            j += 1

        self.reverse(nums, i, mid)
        self.reverse(nums, mid + 1, j - 1)
        self.reverse(nums, i, j - 1)

    def reverse(self, nums: List[int], left: int, right: int) -> None:
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

Method 3 - Quicksort Partition

Here is the approach:

  1. Partition the array: Use a partitioning method similar to QuickSort to move all negative numbers to the left and all positive numbers to the right while maintaining their relative order.
  2. Merging in Alternating Order: After partitioning, the array will have all negative elements on one side and all positive elements on the other side.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

public class Solution {

    public void rearrangePosNeg(int[] nums) {
        partition(nums);
    }

    private void partition(int[] nums) {
        int n = nums.length;
        int[] temp = new int[n];
        int posCount = 0;
        int negCount = 0;

        // Counting positive and negative numbers
        for (int num : nums) {
            if (num >= 0) {
                posCount++;
            } else {
                negCount++;
            }
        }

        int posIndex = 0;
        int negIndex = posCount;

        // Separating positive and negative numbers
        for (int num : nums) {
            if (num >= 0) {
                temp[posIndex++] = num;
            } else {
                temp[negIndex++] = num;
            }
        }

        // Copying back to original array
        System.arraycopy(temp, 0, nums, 0, n);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution:
    def rearrangePosNeg(self, nums: List[int]) -> None:
        self.partition(nums)
    
    def partition(self, nums: List[int]) -> None:
        n = len(nums)
        temp = [0] * n
        pos_count = 0
        neg_count = 0

        # Counting positive and negative numbers
        for num in nums:
            if num >= 0:
                pos_count += 1
            else:
                neg_count += 1

        pos_index = 0
        neg_index = pos_count

        # Separating positive and negative numbers
        for num in nums:
            if num >= 0:
                temp[pos_index] = num
                pos_index += 1
            else:
                temp[neg_index] = num
                neg_index += 1

        # Copying back to original array
        for i in range(n):
            nums[i] = temp[i]

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)