Alternating +ve & -ve in array in O(1) time (maintaining order)

Posted by N.K. Chauhan on Mar 31, 2024

Given an array arr[] of length n, containing positive and negative numbers.

The task is to arrange the numbers in an alternate fashion such that every positive number is followed by a negative and vice-versa, maintaining the order of appearance.

The number of positive and negative numbers need not be equal.

If there are more positive numbers, they appear at the end of the array.

If there are more negative numbers, they too appear at the end of the array.

Input: arr[] = {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8}, n=10
Output: -5,5,-2,2,-8,4,7,1,8,0

Input: arr[] = {-4,1,-1,2,3,4}, n=6
Output: -4,1,-1,2,3,4


Solutions

Method 1: In O(n) time and O(n) space

In this approach, we use an auxiliary array, tmp[] and iterate the input array twice.

In the first iteration, store all negatives at the start of tmp[] and all positives at the end of tmp[].

In the second iteration, keep track of -ve and +ve elements in the tmp[] array and fill alternatively in the original array arr[].

Complexity

The time complexity of this solution is O(n) and space complexity is O(n).

Method 2: In O(n^2) time and O(1) space

In this approach, we iterate the array and keep track of the wrongIndex (-ve in the odd index and +ve in the even index).

If the wrongIndex is greater than -1, we attempt to find the next opposite sign element to the one present on the incorrect index.

Once the opposite sign element is found, we rotate the array from "wrongIndex" to "i".

Also, if the difference between "wrongIndex" and "i" is greater than two, we assign wrongIndex = wrongIndex+2 (more than one wrongIndex is skipped), and if not, wrongIndex = -1.

Complexity

The time complexity of this solution is O(n^2) and space complexity is O(1).

Related


Minimize the difference between the heights of smallest and highest tower

Program to right rotate an array by 'k' elements

Move all negative numbers to beginning of the array

Segregate 0s, 1s and 2s in an array (Sort an array of 0s, 1s and 2s)

Segregate 0s and 1s in an array (Sort an array of 0s and 1s)

Find largest sum contiguous sub-array (Kadane's Algorithm)

Find duplicates in O(n) time and O(1) extra space

Maximum Product Subarray (Modified Kadane's Algorithm)

Find maximum and minimum element of an array

Find duplicates in O(n) time and O(n) extra space.