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

Posted by N.K. Chauhan on Sep 24, 2022

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


Longest substring without repeating characters

Two Sum - return index of a pair of array elements with a given sum

Merge two sorted arrays in O(1) space

Find a triplet in an array that sums to a given number

Word Break Problem (Using HashMap and DP)

Print all Subsets (Power Set) of a given array

Program to print Union of two sorted arrays

Print all possible permutations of an Array in O(1) space

Count the number of inversions in an array - in O(n log n) time

Program to print Intersection of two sorted arrays

Rain water trapping problem - O(n) time & O(n) space