Problem

You are given a 0-indexed integer array nums of even length consisting of an equal number of positive and negative integers.

You should rearrange the elements of nums such that the modified array follows the given conditions:

  1. Every consecutive pair of integers have opposite signs.
  2. For all integers with the same sign, the order in which they were present in nums is preserved.
  3. The rearranged array begins with a positive integer.

Return the modified array after rearranging the elements to satisfy the aforementioned conditions.

Examples

Example 1:

Input: nums = [3,1,-2,-5,2,-4]
Output: [3,-2,1,-5,2,-4]
Explanation:
The positive integers in nums are [3,1,2]. The negative integers are [-2,-5,-4].
The only possible way to rearrange them such that they satisfy all conditions is [3,-2,1,-5,2,-4].
Other ways such as [1,-2,2,-5,3,-4], [3,1,2,-2,-5,-4], [-2,3,-5,1,-4,2] are incorrect because they do not satisfy one or more conditions.

Example 2:

Input: nums = [-1,1]
Output: [1,-1]
Explanation:
1 is the only positive integer and -1 the only negative integer in nums.
So nums is rearranged to [1,-1].

Solution

Method 1 - Using Extra Space and 2 Pointers

  1. Create Aux array out and 2 pointers - j and k for positive and negative integers respectively
  2. Each time we see positive number, we set it in out[j] and increment j by 2
  3. Each time we see negative number, we set it in out[k] and increment k by 2
public int[] rearrangeArray(int[] nums) {
	int[] out = new int[nums.length];
	int j = 0; // positive
	int k = 1; // negative
	for(int i=0;i<nums.length;i++){
		if(nums[i] >= 0){
			out[j] = nums[i];
			j += 2;
		}else {
			out[k] = nums[i];
			k += 2;
		}
	}
	return out;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n), aux space complexity can be considered O(1) as we are returning arrays, and problem doesnt expect us to do it in place.

Method 2 - Generic Algorithm for 0/1 Sorting with O(n) Time and O(1) OR O(n^0.5) Space Complexity

Refer to this paper:

Generic Algorithm for 0/1-Sorting http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.4547&rep=rep1&type=pdf

The paper proposed an algorithm using O(n) time and O(1) space, but it’s too complicated to be implemented here, hence here’s my simplified O(n) time O(n^0.5) space solution.

Also, read a paper on similar topic:

STABLE MINIMUM SPACE PARTITIONINGIN LINEAR TIME http://hjemmesider.diku.dk/~jyrki/Paper/KP1992bJ.pdf

Read more - [3]