Alternate Positive and Negative
You are given an array ‘arr’ that contains an equal number of positive and negative elements. Rearrange the given array such that positive and negative numbers are arranged alternatively. Also, the respective relative order of positive and negative should be maintained.

For example:

For the given arr[ ] = { -1, 3, 5, 0, -2, -5 } arr[ ] = {3, -1, 5, -2, 0, -5 } is valid rearrangement. arr[ ] = {3, -1, 0, -2, 5, -5 } is invalid rearrangement; order of 0 and 5 is changed. arr[ ] = {3, -1, 5, 0, -2, -5 } is invalid rearrangement; positive and negative elements are not alternative.

Note:

Make changes in the same array and no returning or printing is needed. Consider zero(0) as a positive element for this question. It is guaranteed that an answer always exists.

Input Format:

The first line of input contains an integer ‘T’, denoting the number of test cases. Then each test case follows. The first line of each test case contains the Integer ‘N’ denoting the number of elements in the array. The second and the last line of each test case contains ‘N’ single space-separated integers representing the elements of the array.

Output Format:

For each test case, print a single line containing ‘N’ single space-separated integers such that positive and negative numbers are arranged alternatively. Output of each test case will be printed on a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Alternate Positive and Negative

You are given an array ‘arr’ that contains an equal number of positive and negative elements. Rearrange the given array such that positive and negative numbers are arranged alternatively. Also, the respective relative order of positive and negative should be maintained.

For example:

For the given arr[ ] = { -1, 3, 5, 0, -2, -5 } 
arr[ ] = {3, -1, 5, -2, 0, -5 } is valid rearrangement.
arr[ ] = {3, -1, 0, -2, 5, -5 } is invalid rearrangement; order of 0 and 5 is changed. 
arr[ ] = {3, -1, 5, 0, -2, -5 } is invalid rearrangement; positive and negative elements are not alternative.

Note:

Make changes in the same array and no returning or printing is needed.
Consider zero(0) as a positive element for this question.
It is guaranteed that an answer always exists.

Input Format:

The first line of input contains an integer ‘T’, denoting the number of test cases. Then each test case follows.

The first line of each test case contains the Integer ‘N’ denoting the number of elements in the array.

The second and the last line of each test case contains ‘N’ single space-separated integers representing the elements of the array.

Output Format:

For each test case, print a single line containing ‘N’ single space-separated integers such that positive and negative numbers are arranged alternatively.

Output of each test case will be printed on a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 5 * 10 ^ 3
-10 ^ 9 <= arr[i] <= 10 ^ 9

Time Limit: 1 sec.

Accepted Answer

Key idea: Find suitable number for current position on right and swap

Approach : if current idx is even find +ve number on right and if idx is odd find -ve number on right and swap with current position

S1 : Iterate over the array
S2 : If current index is even find next positive number on right
S3 : If current index is odd find the next negative number on right
S4 : Swap with the current position with found number

Accepted Answer

Brute Force

The idea is to rearrange the elements at their correct position one by one from left to right.

Find the first element which is not at its correct position.
- A positive number is not at its correct position if it occurs at odd indexes.
- Similarly, a negative number is not at its correct position, if it occurs at even indexes.
Then find the first element after it with the opposite sign.
Rotate the subarray between the above two positions (inclusive)

Algorithm :

Take a counter say ‘i’, run a loop from 0 to ‘N’ ( number of elements in a given array ).
For each index ‘i’, check
- If the array element is positive and ‘i’ is odd then
  - find the first element index, let's say ‘idx’ after ‘i’ with the negative sign.
  - Now right rotate the subarray from index ‘i’ to ‘idx’ by 1.
  - increment ‘i’ by 1.
- If the array element is negative and ‘i’ is even then
  - find the first element index, let's say ‘idx’ after ‘i’ with the positive sign.
  - Now rotate the subarray from index ‘i’ to ‘idx’ by 1.
  - increment ‘i’ by 1.

Space Complexity: O(1)Explanation:

O(1)

We are rearranging the elements in place, not using any extra space.

Time Complexity: O(n^2)Explanation:

O(N ^ 2) where ‘N’ is the number of elements in a given array.

In the worst case, every 2nd element is not at its correct position, then for each we need to calculate the next element with opposite sign that takes O( ‘N’ ) and rotate the subarray takes O( ‘N’ ), So overall time complexity is O(N ) * O( 2 * N ) = O( N ^ 2 ).

Java (SE 1.8)


/*
	Time Complexity: O(N^2)
	Space Complexity: O(1)
	
	Where 'N' is the number of elements in the array.
*/
public class Solution {

	// Utility function that return the index of the opposite sign element to the
	// right of index 'i'.
	public static int findIdx(int[] arr, int i, boolean isPos) {

		// Calculate the size of array
		int n = arr.length;

		// Run a loop from 'i' to n-1
		for (int j = i; j < n; j++) {

			// If required element is positive and element is positive
			if (isPos && arr[j] >= 0) {

				// Return index j
				return j;
			}

			// If required element is negative and element is negative
			if (!isPos && arr[j] < 0) {

				// Return index j
				return j;
			}
		}
		return -1;

	}

	// Utility function to rotate the subarray array[i...idx] right by one
	public static void rotateRight(int[] arr, int i, int idx) {

		// Calculate the size of array
		int n = arr.length;

		// Store the 'idx' element
		int temp = arr[idx];

		// Run a loop from 'idx' to 'i'+1 and shift each element by 1 to right
		for (int j = idx; j > i; j--) {
			arr[j] = arr[j - 1];
		}

		// Store the element of index 'idx' at 'i'
		arr[i] = temp;

		// Return
		return;
	}

	public static void posAndNeg(int[] arr) {

		// Store the size of vector array 'arr'
		int n = arr.length;

		// Run a loop from 0 to 'n'-1
		for (int i = 0; i < n; i++) {

			int oddPosition = i & 1;

			// If element is positive and at odd position
			if (arr[i] >= 0 && (oddPosition == 1)) {

				// Find the index of first opposite sign element right to 'i'
				int idx = findIdx(arr, i, false);

				// Rotate the subarray arr[i...idx] by one to right
				rotateRight(arr, i, idx);

				// Increament i by 1
				i++;
			}
			// If element is negative and at even position
			else if (arr[i] < 0 && (i % 2 == 0)) {

				// Find the index of first opposite sign element, right to 'i'
				int idx = findIdx(arr, i, true);

				// Rotate the subarray arr[i...idx] by one to right
				rotateRight(arr, i, idx);

				// Increament i by 1
				i++;
			}
		}

	}
}

Python (3.5)

'''

    Time Complexity: O(N^2)

    Space Complexity: O(1)



    Where 'N' is the number of elements in the array.

'''



# Utility function that return the index of the opposite sign element to the right of index 'i'. 

def findIdx(arr, i, isPos):

	

	# Calculate the size of array

	n = len(arr)

	

	# Run a loop from 'i' to n-1



	for j in range(i, n):

		

		# If required element is positive and element is positive

		if(isPos and arr[j] >= 0):

			

			# Return index j

			return j

			

		# If required element is negative and element is negative

		if(isPos == False and arr[j] < 0):

			

			# Return index j

			return j



# Utility function to rotate the subarray array[i...idx] right by one

def rotateRight(arr, i, idx):

	

	# Calculate the size of array

	n = len(arr)

	

	# Store the 'idx' element 

	temp = arr[idx]

	

	# Run a loop from 'idx' to 'i'+1 and shift each element by 1 to right

	

	j = idx

	while(j > i):

		arr[j] = arr[j-1]

		j -= 1

		

	# Store the element of index 'idx' at 'i'

	arr[i] = temp

	

	# Return 

	return



# Function to rearrange the array elements in alternative positive and negative fashion.

def posAndNeg(arr):

	

	# Store the size of vector array 'arr'.

	n = len(arr)

	

	# Run a loop from 0 to 'n'-1.



	for i in range(n):



		# If element is positive and at odd position

		if(arr[i] >= 0 and (i & 1) == True):

			

			# Find the index of first opposite sign element right to 'i'

			idx = findIdx(arr, i, False)

			

			# Rotate the subarray arr[i...idx] by one to right

			rotateRight(arr, i, idx)

			

			# Increament i by 1

			i += 1

			

		# If element is negative and at even position

		elif(arr[i] < 0 and (i % 2 == 0)):

			

			# Find the index of first opposite sign element, right to 'i'

			idx = findIdx(arr, i, True)

			

			# Rotate the subarray arr[i...idx] by one to right

			rotateRight(arr, i, idx)

			

			# Increament i by 1

			i += 1

C++ (g++ 5.4)

/*

    Time Complexity: O(N^2)

    Space Complexity: O(1)



    Where 'N' is the number of elements in the array.

*/ 



// Utility function that return the index of the opposite sign element to the right of index 'i'. 

int findIdx(vector &arr, int i, bool isPos){



    // Calculate the size of array

    int n = arr.size();



    // Run a loop from 'i' to n-1

    for(int j = i; j < n; j++){



        // If required element is positive and element is positive

        if(isPos && arr[j] >= 0)

        {

            // Return index j

            return j;

        }



        // If required element is negative and element is negative

        if(! isPos && arr[j] < 0)

        {

            // Return index j

            return j;

        }

    }



}



// Utility function to rotate the subarray array[i...idx] right by one

void rotateRight(vector &arr, int i, int idx){



    // Calculate the size of array

    int n = arr.size();

    

    // Store the 'idx' element 

    int temp = arr[idx];

    

    // Run a loop from 'idx' to 'i'+1 and shift each element by 1 to right

    for(int j = idx; j > i; j--)

    {

        arr[j] = arr[j-1];

    }



    // Store the element of index 'idx' at 'i'

    arr[i] = temp;

    

    // Return 

    return;

}



// Function to rearrange the array elements in alternative positive and negative fashion.

void posAndNeg(vector &arr){



    // Store the size of vector array 'arr'

    int n = arr.size();



    // Run a loop from 0 to 'n'-1

    for(int i = 0; i < n; i++)

    {

        // If element is positive and at odd position

        if(arr[i] >= 0 && (i & 1))

        {

            // Find the index of first opposite sign element right to 'i'

            int idx = findIdx(arr, i, false);

           

           // Rotate the subarray arr[i...idx] by one to right

            rotateRight(arr, i, idx);



            // Increament i by 1

            i++;

        }

        // If element is negative and at even position

        else if(arr[i] < 0 && (i % 2 == 0))

        {

            // Find the index of first opposite sign element, right to 'i'

            int idx = findIdx(arr, i, true);

            

            // Rotate the subarray arr[i...idx] by one to right

            rotateRight(arr, i, idx);

            

            // Increament i by 1

            i++;

        }

    }



    return ;

}

Accepted Answer

Using Extra Space

The idea is to use two pointers one for the positive numbers and one for the negative number and a temp array. we can iterate the given array and if the current element is positive then we can add this number in 'temp' array at the positive pointer, and vice versa.

Algorithm :

Let’s take a temporary array say ‘temp’ of size ‘N’, a pointer ‘pos’ pointing to positive elements index (even index), initialize it to 0 and a pointer ‘neg’ pointing to negative elements index (odd index) initialize it to 1.
Run a loop from 0 to ‘N’ and for each element check
- If the element is positive or zero.
  - then store the current element at position ‘pos’ in the ‘temp’ array.
  - increment ‘pos’ by 2.
- Else
  - store the current element at position ‘neg’ in the ‘temp’ array.
  - increment ‘neg’ by 2.
Take a counter ‘i’, and run a loop from 0 to ‘N,
- Store the value of ’temp’ at index’ to ‘arr’ at index ‘i’ i.e do arr[i] = temp[i].

Space Complexity: O(n)Explanation:

O(‘N’), where ‘N’ is the number of elements in a given array.

Our algorithm uses an extra temporary array ‘temp’ of size ‘N’ to rearrange the elements. Hence space complexity is O(‘N’).

Time Complexity: O(n)Explanation:

O( ‘N’ ), where ‘N’ is the number of elements in a given array.

Our algorithm uses two simple for loops, one to store the elements in array ‘temp’ and the second to store the rearranged elements back in the original array ‘arr’. Hence time complexity is O(2 * ‘N’) = O(‘N’).

Java (SE 1.8)


/*
	Time Complexity: O(N)
	Space Complexity: O(N)
	
	Where 'N' is the number of elements in the array.
*/

public class Solution {

	public static void posAndNeg(int[] arr) {
		 // Store the size of vector array 'arr'
	    int n = arr.length;

	    // Take a temporary array 'temp' of size 'n' which stores the rearranged elements
	    int temp[]= new int[n];
	    
	    // Pointer to point the indexes of positive number in 'temp'
	    int pos = 0;
	    
	    // Pointer to point the indexes of negative number in 'temp'
	    int neg = 1;

	    // Run a loop from 0 to 'n'
	    for(int i = 0; i < n; i++){

	        // If element is positive or zero (0)
	        if(arr[i] >= 0)
	        {
	            // Store positive element of 'arr' at index 'i' to 'temp' at index 'pos'
	            temp[pos] = arr[i];

	            // Increament the 'pos' by 2
	            pos += 2;
	        }
	        else
	        {
	            // Store negative element of 'arr' at index 'i' to 'temp' at index 'neg'
	            temp[neg] = arr[i];

	            // Increament the 'neg' by 2
	            neg += 2;
	        }
	    }

	    // Copy the value of 'temp' array to original array 'arr'
	    for(int i = 0; i < n; i++)
	    {
	        arr[i] = temp[i];
	    }

	    // Return
	    							
	    return;

	}

}

Python (3.5)

'''

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where 'N' is the number of elements in the array.

'''



# Function to rearrange the array elements in alternative positive and negative fashion.

def posAndNeg(arr):

	

	# Store the size of 'arr'

	n = len(arr)

	

	# Take a temporary array 'temp' of size 'n' which stores the rearranged elements

	temp = [None for i in range(n)]

	

	# Pointer to point the indexes of positive number in 'temp'

	pos = 0

	

	# Pointer to point the indexes of negative number in 'temp'

	neg = 1

	

	# Run a loop from 0 to 'n'.



	for i in range(n):



		# If element is positive or zero (0)

		if(arr[i] >= 0):

			

			# Store positive element of 'arr' at index 'i' to 'temp' at index 'pos'.

			temp[pos] = arr[i]

			

			# Increament the 'pos' by 2.

			pos += 2

			

		else:

			

			# Store negative element of 'arr' at index 'i' to 'temp' at index 'neg'.

			temp[neg] = arr[i]

			

			# Increament the 'neg' by 2

			neg += 2

			

	# Copy the value of 'temp' array to original array 'arr'



	for i in range(n):

		arr[i] = temp[i]

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(N)



    Where 'N' is the number of elements in the array.

*/



// Function to find the square root of 'N'

void posAndNeg(vector &arr){



    // Store the size of vector array 'arr'

    int n = arr.size();



    // Take a temporary array 'temp' of size 'n' which stores the rearranged elements

    int temp[n];

    

    // Pointer to point the indexes of positive number in 'temp'

    int pos = 0;

    

    // Pointer to point the indexes of negative number in 'temp'

    int neg = 1;



    // Run a loop from 0 to 'n'

    for(int i = 0; i < n; i++){



        // If element is positive or zero (0)

        if(arr[i] >= 0)

        {

            // Store positive element of 'arr' at index 'i' to 'temp' at index 'pos'

            temp[pos] = arr[i];



            // Increament the 'pos' by 2

            pos += 2;

        }

        else

        {

            // Store negative element of 'arr' at index 'i' to 'temp' at index 'ne'

            temp[neg] = arr[i];



            // Increament the 'neg' by 2

            neg += 2;

        }

    }



    // Copy the value of 'temp' array to original array 'arr'

    for(int i = 0; i < n; i++)

    {

        arr[i] = temp[i];

    }



    // Return

    return;

}

You are given an array ‘arr’ that contains an equal number of positive and negative elements. Rearrange the given array such that positive and negative numbers are arranged alternatively. Also, the respective relative order of positive and negative should be maintained.

For example:

Note:

Input Format:

Output Format:

Note:

Constraints:

Top PayU Payments Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in PayU Payments Software Engineer