GFG Rearrange array in alternating positive & negative items with O(1) extra space

Problem Statement #2 - Unordereed

InPlace O(1) space

Pattern:

---

Solution

public int[] rearrangeUnordered(int[] nums) {
	int ni = 0; // negative index
	for (int i = 0; i < nums.length && ni < nums.length; i++) {
		if (nums[i] < 0) {
			swap(nums, i, ni);
			ni +=2;
		}
	}
	return nums;
}

Time Complexity: O(n)

Notes

• Will not maintain relative order of elements: not stable

Problem Statement #1 - Ordered

Rearrange array in alternating positive & negative items with O(1) extra space | Set 1 - GeeksforGeeks

With O(n) space its easy :Alternate positive and negative numbers | Practice | GeeksforGeeks

void rearrange(int nums[], int n) {
	LinkedList<Integer> neg = new LinkedList<>(), pos = new LinkedList<>();
	
	// create pos and negative linked lists
	for(int num : nums)
		if(num < 0) neg.add(num);
		else pos.add(num);
	
	// merge both
	int index = 0;
	while(!pos.isEmpty() && !neg.isEmpty()) {
		nums[index++] = pos.remove();
		nums[index++] = neg.remove();
	}
	
	// copy leftover
	while(!pos.isEmpty())nums[index++] = pos.remove();
	while(!neg.isEmpty())nums[index++] = neg.remove() ;
	
	return;
}

The only way this can be solved in O(1) space is if time complexity is O(n^2), which is the solution given at gfg