Problem

Given an array nums[] containing negative and positive elements, rearrange the array such that positive and negative elements occupy alternate positions. If there are extra positive or negative elements, append them to the end of the array.

Examples

Example 1:

1
2

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

Example 2:

1
2

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

Similar Problem

This problem is similar to Rearrange Array Elements by Sign, but here we have to do in-place, and there we can return a newly created array as output.

Solution

Method 1 - Naive

  1. Create two lists: one for positive elements and one for negative elements.
  2. Use a loop to alternate between positive and negative elements, appending any remaining elements at the end.

Complexity

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

Method 2 - Quicksort Partition

Here is the approach:

  1. Partitioning:
    • Use the QuickSort partition logic with pivot as 0 to partition the array into two halves: all negative numbers on the left side and all positive numbers on the right side.
  2. Merging in Alternating Order:
    • After partitioning, merge the two halves by interleaving one negative and one positive element. Append the remaining elements if any side has more elements.

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
40
41
42
43
44
45
46
47
48

public class Solution {
    public void rearrangeArray(int[] nums) {
        int n = nums.length;
        
        // Partition into negative and positive halves
        int index = partition(nums);
        
        int posIndex = index, negIndex = 0;
        
        // Interleave positive and negative elements
        while (negIndex < index && posIndex < n && nums[negIndex] < 0) {
            swap(nums, negIndex, posIndex);
            posIndex++;
            negIndex += 2;
        }
        
        System.out.println("Rearranged array: " + Arrays.toString(nums));
    }

    private int partition(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            if (nums[left] < 0) {
                left++;
            } else if (nums[right] >= 0) {
                right--;
            } else {
                swap(nums, left, right);
            }
        }
        return left;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums1 = {1, -1, 3, -2, -3, 5};
        sol.rearrangeArray(nums1);  // Expected output: [1, -1, 3, -2, 5, -3]

        int[] nums2 = {-1, 2, -3, 4, -5, 6, -7};
        sol.rearrangeArray(nums2);  // Expected output: [2, -1, 4, -3, 6, -5, -7]
    }
}
 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

class Solution:
    def rearrangeArray(self, nums: List[int]) -> None:
        n = len(nums)
        
        # Partition into negative and positive halves
        index = self.partition(nums)
        
        pos_index = index
        neg_index = 0
        
        # Interleave positive and negative elements
        while neg_index < index and pos_index < n and nums[neg_index] < 0:
            self.swap(nums, neg_index, pos_index)
            pos_index += 1
            neg_index += 2
        
        print("Rearranged array:", nums)
    
    def partition(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            if nums[left] < 0:
                left += 1
            elif nums[right] >= 0:
                right -= 1
            else:
                self.swap(nums, left, right)
        return left
    
    def swap(self, nums: List[int], i: int, j: int) -> None:
        nums[i], nums[j] = nums[j], nums[i]

# Example usage
sol = Solution()
nums1 = [1, -1, 3, -2, -3, 5]
sol.rearrangeArray(nums1)  # Expected output: [1, -1, 3, -2, 5, -3]

nums2 = [-1, 2, -3, 4, -5, 6, -7]
sol.rearrangeArray(nums2)  # Expected output: [2, -1, 4, -3, 6, -5, -7]

Complexity

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