CareerCup

Isn't it the memory/complexity tradeoff problem? Can't see how can it be done meeting the requirements.

I believe this question is not possible. The interviewee must have gotten confused with the interview question.

I believe the interviewer must have asked "How do we do this problem?" The problem is certainly doable. We can divide the initial array into a positive array and a negative array, and then weave the arrays. This would work in linear time, but also has linear space requirement.

Then, as a follow up question, I imagine the interviewer must have asked "So, what is the time complexity of this problem?"
Interviewee: "It is O(N)."
Interviewer: "Good. Now, what if we find we need to constrain the space to O(1) since we are dealing with humongo data sets like we tend to do at Amazon. How would you change the algorithm?"
Interviewee: "Here is a different algorithm where we maintain several pointers into the array, a temporary value for shifts, and do some shifting within the array. The space requirement is now O(1)."

The thing is, to get the space requirement down to O(1), we have blown up the time requirement to O(N^2), I believe.

My intuition will go as follows.

Create an array A of length N with N=a power of 2. For clarity use this example A =
[1, 2, 3, ... 512, -1, -2, -3, ... -512].

To maintain ordering, I believe we need to do a series of shifts.

Like, we will shift value -1 from index 512 to index 1 (so, 511 shifts).
We will shift value -2 from index 513 to index 3 (so, 510 shifts).
...
Shift value -511 from index 1023 to 1022 (1 shift).
Value -512 starts in index 1024 and remains there (0 shifts).

This would involve a sum
sum(i) from i=1 to 511
= (511+1) + (510+2) + (509+3) ... = ~512*(512/2) = N*N/2 = O(N^2)

Of course, that is the time complexity for the shifting-based algorithm. There may be a better solution. I will think about it more later today, but anyone interested in collaborating here please do consider that example array I gave.

Another idea to consider proceeding with is doing multiple loops through the array. e.g. you can do a loop through to count the number of positive integers and negative integers, and then do a processing loop after that. The problem is maintaining order of positives and negatives within the resultant array seems like it must involve shifting.

I could also imagine an idea like this, though...
[1,2,3,4,-1,-2,-3,-4]
count 4 pos values, 4 neg values in loop 1
loop to find first neg value at index 4, calculate its end position (which is index 1), then stick it in position 1, and lift up value 2,
[1,-1,3,4,null,-2,-3,-4]
tmpval=2
tmpidx=1
and calculate 2's rightful end position, which would be index 2
[1,-1,2,4,null,-2,-3,-4]
tmpval=3
tmpidx=2
now we need to place value 3 back into the array
[1,-1,2,4,3,-2,-3,-4]
tmpval=-1
tmpidx=4

So, at this point, we have done a few switches of variables, and now shifting (like my previous algorithm). I think this method has a chance of working. I may have made some mistakes since I am underslept today, but I believe this general approach will work. Props to anyone who makes this one work.

--Tom

Algorithm :
- Divide array into two parts : -ve and +ve numbers assuming 0 as a modified version of quicksort .
- Now we have all the positive numbers at the end of the array and all the negative numbers at the start of the array
- have 2 pointers , one pointing to the first number in the array which is a negative number and the other one to be pointing to the first positive number in the array.
- Swap the two elements. Increment positive counter by 1 and negative counter by 2. repeat
- If there are more positive numbers or more negative numbers than they will appear at the end of the array.

Java code:

void rearrange(int arr[]) 
	int len = arr.length;
	int i = -1;
	
	for(int j =0;j<len;j++) 
	{
		if(arr[j] < 0)
		{
			i++;
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}

	int pos = i+1;
	int neg = 0;
	
	while (pos < n && neg < pos && arr[neg] < 0)
    	{
        	int temp = arr[neg];
		arr[neg] = arr[pos];
		arr[pos] = temp;
        	pos++;
        	neg += 2;
    	}

Taken from : http://www.geeksforgeeks.org/rearrange-positive-and-negative-numbers-publish/

After thinking a bit more about this problem, I think the only way this can be done in-place (no extra memory) and with linear time is to consider the comparison operation as the function to evaluate. If it's comparisons what we care about, the code below is an O( n ) solution. Now, this makes O (n^2) memory swaps to maintain the constant space constraint.

inline bool RightSign(int x, bool pos)
{
    return pos ? x >= 0 : x < 0;
}

void Alternate(int* a, size_t n)
{
    assert(n > 0);
    size_t wrong = 0;
    size_t candidate = 0;
    bool pos = false;
    while (wrong < n)
    {
        while (RightSign(a[wrong], pos))
        {
            pos = !pos;
            ++wrong;
        }
        candidate = candidate <= wrong ? wrong + 1 : candidate;
        while (candidate < n && !RightSign(a[candidate], pos))
        {
            ++candidate;
        }
        if (candidate >= n) return;
        for (size_t i = candidate; i > wrong; --i)
        {
            assert(i < n);
            std::swap(a[i], a[i - 1]);
        }
        wrong += 2;
    }
}

It seems to me that there are some questions that need to be asked:

1. When you say "the order should be same as previous array", what do you mean? By switching positive and negative numbers you are, in essence, changing the order of the array.

1a. Do you mean: If there are multiple positives or negatives in a row, they should maintain their order?

2. What is the expected result if the array has only 1 negative number? e.g., [1, 2, 3, 4, 5, 6, 7, -8, 9]?

2a. Is the expected result from 2 the same if the array has only 1 positive number?

3. My initial thought was that this was a contrived question to get you to in-place sort pairs of numbers ensuring that they are in positive, negative,... order.

My solution works for most cases except the ones I listed above. My solution, though it fits the question, is ambiguous and depends on what the interviewer is looking for.

If You carefully observer then we will get following pattern :
Count the -ve and +ve.. Which one is lesser that has to be in the middle for i-1, i, i+1 ...

I am taking only one case : -ve are lesser than +ve... but this sol will easily work for other case also.

1) If left(i-1) is negative and mid (i) is also negative : shift the mid val to right to nextOpposite flag. If nothing is found then break. then swap left and mid.

2) if left (i-1) is negative and mid is positive : swap the i-1 and i;
3) If both are positive : shift i the next possible opposite flag.

i+=2;


Code will look like this way (There needs some modification for second case but it will work I assume):

public static void sol2(int[] arr)
{
int i = 1;

while (i < arr.length)
{
int left = arr[i - 1];
int mid = arr[i];

if (left < 0 && mid < 0)
{
boolean found = shiftMiddleToNextOppositeFlag(arr, i);
if (!found)
break;
swap(arr, i, i - 1);
}
else if (left < 0)
swap(arr, i, i - 1);
else if (left > 0 && mid > 0)
{
boolean found = shiftMiddleToNextOppositeFlag(arr, i);
if (!found)
break;
}
i += 2;
}
}

private static boolean shiftMiddleToNextOppositeFlag(int[] arr, int i)
{
int temp = arr[i], idx = -1;
boolean isMidPositive = temp > 0;
for (int j = i+1; j < arr.length; j++)
{
boolean isCurrPositive = arr[j] > 0;
if (isMidPositive ^ isCurrPositive)
{
idx = j;
break;
}

}
if (idx == -1)
return false;

int high = arr[idx];

shiftRight(arr, i, idx);

arr[i] = high;

return true;
}

private static void shiftRight(int[] arr, int low, int high)
{
for (int i = high; i > low; i--)
{
arr[i] = arr[i - 1];
}
}


private static void swap(int[] arr, int i1, int i2)
{
int temp = arr[i1];
arr[i1] = arr[i2];
arr[i2] = temp;
}


public static void main(String args[])
{
int[] arr = {-2, 3, 4, 5, -1, -6, 7, 9, 1};

sol2(arr);

for (int i : arr)
System.out.print(i + " ");


}

how abt this??? first scan entire array , and get total count of positives and negatives. now in that array , lets take 2 pointers , one starts at start and other at the start + count of positives. now seperate positives and negatives in following manner. keep on incrementing first index , till u get negative value. once u get , swap with that the value of second index and increment second index.
now we have both posittives and negatives seperated.
now again take 2 pointers and swap alternative numbers .
total time ocmplexity is similar to o(n) , space is o(1)

void swap(int* array, int i, int j)
{
    int tmp = array[i];
	array[i] = array[j];
	array[j] = tmp;
}

int next(int* array, int n, int x, bool isPositive)
{
	for (int i = x+1; i < n; i++)
	{
		if (isPositive && array[i] >= 0) return i;
		else if (!isPositive && array[i] < 0) return i;
	}
	
	return n;
}

void alternatePositiveAndNegative(int* array, int n)
{
    //invariant -> all elements before nexP are ordered or negatives
	int nextP = next(array, n, -1, true);
    swap(array, 0, nextP);
    
    //invariant -> all elements before nexN are ordered or positives
    int nextN = -1;
	
    //invariant -> all elements before i are ordered
	for (int i = 1; i < n; i++)
	{
        if (i%2==0) {
    		nextP = next(array, n, max(i-1, nextP), true);
    		if (nextP < n) swap(array, i, nextP);
        }else {
		    nextN = next(array, n, max(i-1, nextN), false);
        	if (nextN < n) swap(array, i, nextN);
		}
	}

}

Worst case : O(n^2)

public class AlternatePosNeg {

	public static void main(String[] args) {
		int []arr = {-1,-2,3,5,-3,-4,6,12,-41,13};
		int len = arr.length;
		int nextNeg = -1, nextPos = -1;
		boolean nextPostive = true;
		for(int pivot=0;pivot<len;pivot++){
			System.out.print(" "+arr[pivot]);
		}
		System.out.println("");
		for(int pivot=0;pivot<len-1;pivot++){
			if(nextPostive){ //need to fill with +ve
				if (arr[pivot] < 0)	{			
					nextPos = pivot+1;
					while(nextPos < len && arr[nextPos++] < 0);
					int temp = arr[--nextPos];
					while(temp > 0 && nextPos > 0 && nextPos > pivot){
						arr[nextPos] = arr[nextPos-1];
						nextPos--;
					}
					if(temp > 0)
						arr[pivot] = temp;
				}
				nextPostive = !nextPostive;
			}else{//need to fill with -ve
				if (arr[pivot] > 0)
				{
					nextNeg = pivot+1;
					while(nextNeg < len && arr[nextNeg++] > 0);
					int temp = arr[--nextPos];
					while(temp < 0 && nextPos > 0 && nextPos > pivot){
						arr[nextPos] = arr[nextPos-1];
						nextPos--;
					}
					if(temp < 0)
						arr[pivot] = temp;
				}
				nextPostive = !nextPostive;
			}
		}
		for(int pivot=0;pivot<len;pivot++){
			System.out.print(" "+arr[pivot]);
		}
	}

}

average case O(n), but worst case O(n^2)

public class AlternatePosNeg {

	public static void main(String[] args) {
		int []arr = {-1,-2,3,5,-3,-4,6,12,-41,13};
		int len = arr.length;
		int nextNeg = -1, nextPos = -1;
		boolean nextPostive = true;
		for(int pivot=0;pivot<len;pivot++){
			System.out.print(" "+arr[pivot]);
		}
		System.out.println("");
		for(int pivot=0;pivot<len-1;pivot++){
			if(nextPostive){ //need to fill with +ve
				if (arr[pivot] < 0)	{			
					nextPos = pivot+1;
					while(nextPos < len && arr[nextPos++] < 0);
					int temp = arr[--nextPos];
					while(temp > 0 && nextPos > 0 && nextPos > pivot){
						arr[nextPos] = arr[nextPos-1];
						nextPos--;
					}
					if(temp > 0)
						arr[pivot] = temp;
				}
				nextPostive = !nextPostive;
			}else{//need to fill with -ve
				if (arr[pivot] > 0)
				{
					nextNeg = pivot+1;
					while(nextNeg < len && arr[nextNeg++] > 0);
					int temp = arr[--nextPos];
					while(temp < 0 && nextPos > 0 && nextPos > pivot){
						arr[nextPos] = arr[nextPos-1];
						nextPos--;
					}
					if(temp < 0)
						arr[pivot] = temp;
				}
				nextPostive = !nextPostive;
			}
		}
		for(int pivot=0;pivot<len;pivot++){
			System.out.print(" "+arr[pivot]);
		}
	}

}

Here is the C# Code with time complexity O(n-2).

public static void SetArray(int[] A)
        {
            int p = -1;
            for (int i = 1; i < A.Length-1; i++)
            {
                if (isnegative(A[i-1]) == isnegative(A[i]) && isnegative(A[i]) != isnegative(A[i+1]))
                {
                    int temp = A[i];
                    A[i] = A[i + 1];
                    A[i + 1] = temp;
                    p = i;
                }
                else if (isnegative(A[i]) == isnegative(A[i+1]) && isnegative(A[i+1]) != isnegative(A[i-1]))
                {
                    if (i - 1 != p)
                    {
                        int temp = A[i];
                        A[i] = A[i - 1];
                        A[i - 1] = temp;
                    }
                    p = i;
                }
                else if ( isnegative(A[i-1]) == isnegative(A[i]) && isnegative(A[i]) == isnegative(A[i+1]))
                {
                    break;
                }
                else
                {
                    p = ++i;
                }
            }
        }

        public static bool isnegative(int number)
        {
            return number < 0 ? true : false;
        }

// into empty duplicate array, copy positives in order from duplicate's start and negatives in reverse order from duplicate's end
// copy from duplicate array back to original array alternating as long as you can
// if positives are left, copy them back in order
// if negatives are left, copy them back in reverse order

import java.util.Arrays;

public class Alternate {
	
	public static int[] array = new int[] {-2, 3, 4, 5, -1, -6, 7, 9, 1};

	public static void main(String[] args) {
		System.out.println(Arrays.toString(array));
		
		int[] posNeg = new int[array.length];
		int pos = 0;
		int neg = array.length - 1;

		// put pos at start in order, neg at end in reverse order
		for (int x = 0; x < array.length; x++)
			if (array[x] >= 0)
				posNeg[pos++] = array[x];
			else
				posNeg[neg--] = array[x];

		pos = 0;
		neg = array.length - 1;
		int x = 0;

		// copy back to original array alternating 
		while (posNeg[pos] >= 0 && posNeg[neg] < 0 && x < array.length - 1) {
			array[x++] = posNeg[pos++];
			array[x++] = posNeg[neg--];			
		}
		
		// when done alternating, copy back the rest
		if (x < array.length) {
			if (posNeg[pos] >= 0) 
				while (x < array.length)
					array[x++] = posNeg[pos++];
			else
				while (x < array.length)
					array[x++] = posNeg[neg--];
		}
		System.out.println(Arrays.toString(array));
	}
}

static void Alternate(int[] numbers)
        {
            int p1 = 0;
            int p2 = 0;
            while (p2 < numbers.Length && p1 < numbers.Length -2)
            {
                if (IsPostive(numbers[p1]) != IsPostive(numbers[p1 + 1]))
                {
                    p1++;
                }
                else
                {
                    if(p2 < p1)
                    {
                        p2 = p1 + 2;
                    }
                    if (IsPostive(numbers[p2]) != IsPostive(numbers[p1]))
                    {
                        int temp = numbers[p2];
                        for (int i = p2; i > p1; i--)
                        {
                            numbers[i] = numbers[i-1];
                        }
                        numbers[p1 + 1] = temp;
                    }
                    p2++;
                }
            }
        }

        static bool IsPostive(int num)
        {
            return num > 0;
        }

#include<iostream>

int get_next_neg(int a[], int n, int p){
  for(int i=p+1; i<n; i++){
    if(a[i]<0)
      return i;
  }
  return n;
}

int get_next_pos(int a[], int n, int p){
  for(int i=p+1; i<n; i++){
    if(a[i]>0)
      return i;
  }
  return n;
}

int swap(int a[], int p, int next){
  int t = a[p]; 
  a[p]=next;
  return t;
}

void alternate(int a[], int n){
  int p_neg, p_pos;         //Positions of the last found positive and negative elements respectively
  int next_pos, next_neg;   //Next positive and negative elements
  
  p_neg = p_pos = -1;
  p_neg = get_next_neg(a,n,p_neg);
  p_pos = get_next_pos(a,n,p_pos);
  if(p_neg<n)
    next_neg = a[p_neg];
  if(p_pos<n)
    next_pos = a[p_pos];

  for(int i=0; i<n; i++){
    if( (i&1)==0 && p_neg<n ){
      p_neg = get_next_neg(a,n,p_neg);
      if(p_neg==i)
	next_neg = swap(a,p_neg,next_neg);
      else{
	a[i] = next_neg;
	if(p_neg<n)
	  next_neg = a[p_neg];
      }	
    }
    else if( p_pos < n ){
      p_pos = get_next_pos(a,n,p_pos);
      if(p_pos==i)
	next_pos = swap(a,p_pos,next_pos);
      else{
	a[i] = next_pos;
	if(p_pos<n)
	  next_pos = a[p_pos];
      }
    }
  }
}

int main(int argc, char**argv){
  int n;
  std::cout << "Enter n::";
  std::cin >> n;
  
  std::cout << "Enter the elements::\n" ;
  int a[n];
  for(int i=0; i<n; i++){
    std::cin >> a[i];
  }

  alternate(a,n);
  
  for(int i=0; i<n; i++){
    std::cout << a[i] << " ";
  }
}

public static int[] positiveNegativeAlt(int[] a) {
		int k = 0, i = 1;

		while (k < a.length) {
			// array should start with positive value;
			
			if ((a[k] < 0) && (k % 2 == 0)) {
				while (a[i] < 0 && i < a.length-1) {
					i++;
				}
				if (a[i] < 0)
					break;
				int temp = a[i];
				a[i] = a[k];
				a[k] = temp;
			} else if ((a[k] > 0) && (k % 2 == 1)) {
				while (a[i] > 0 && i < a.length-1) {
					i++;
				}
				if (a[i] > 0)
					break;
				int temp = a[i];
				a[i] = a[k];
				a[k] = temp;
			}

			k++;
			if (k < a.length)
				i = k + 1;
			else {
				break;
			}

		}

		for (int j = 0; j < a.length; j++) {
			System.out.print("\t" + a[j]);
		}
		return a;

	}

public static int[] positiveNegativeAlt(int[] a) {
		int k = 0, i = 1;

		while (k < a.length) {
			// array should start with positive value;
			if ((a[k] < 0) && (k % 2 == 0)) {
				while (a[i] < 0 && i < a.length-1) {
					i++;
				}
				if (a[i] < 0)
					break;
				int temp = a[i];
				a[i] = a[k];
				a[k] = temp;
			} else if ((a[k] > 0) && (k % 2 == 1)) {
				while (a[i] > 0 && i < a.length-1) {
					i++;
				}
				if (a[i] > 0)
					break;
				int temp = a[i];
				a[i] = a[k];
				a[k] = temp;
			}

			k++;
			if (k < a.length)
				i = k + 1;
			else {
				break;
			}

		}

		for (int j = 0; j < a.length; j++) {
			System.out.print("\t" + a[j]);
		}
		return a;

	}

O(1)-space but not sure O(N) time-complexity solution:

void sortNumbers(vector<long> &data)
{
	size_t j;
	long tmp;
	for (size_t i = 0; i < data.size(); i++) {
		if (data[i] < 0 && data[i + 1] < 0) {// Look for positive number
			for (j = i + 1; j < data.size() && data[j] < 0; j++);
			if (j == data.size())
				break;
			// Shift i+1 to j-1
			tmp = data[j];
			for (size_t k = j; k > i; k--)
				data[k] = data[k - 1];
			data[i + 1] = tmp;
		}  else if (data[i] > 0 && data[i + 1] > 0) {// Look for positive number
			for (j = i + 1; j < data.size() && data[j] > 0; j++);
			if (j == data.size())
				break;
			// Shift i+1 to j-1
			tmp = data[j];
			for (size_t k = j; k > i; k--)
				data[k] = data[k - 1];
			data[i + 1] = tmp;
		}
	}
}

class Sign
{
	Boolean sign;

	Boolean getsign(int num)
	{
		if (num > 0)
		{
			sign = true;
		}
		else
		{
			sign = false;
		}
		return sign;
	}
}

public class OrderOfNumbers
{
	public static void main(String[] args)
	{
		// TODO Auto-generated method stub
		int[] arr1 =
		{ 1, -1, 2, -2, -3, -4 };
		// int[] arr1 = {-2,2,3,-4,-5,-6};
		Sign obj = new Sign();
		Boolean signofnumber = obj.getsign(arr1[0]);
		int i = 1;
		int j = 1;
		int temp1 = i;
		int temp2 = i;
		int temp = 0;
		while (temp1 < arr1.length)
		{
			if (signofnumber != obj.getsign(arr1[temp2]))
			{
				temp1++;
				temp2 = temp1;
				signofnumber = !(signofnumber);
			}
			else
			{
				while (obj.getsign(arr1[temp2]) == ((signofnumber)))
				{
					temp2 = temp2 + 1;
					if (temp2 == arr1.length)
					{
						break;
					}
				}
				if (temp2 == arr1.length)
				{
					break;
				}
				temp = arr1[temp1];
				arr1[temp1] = arr1[temp2];
				arr1[temp2] = temp;
				temp1++;
				temp2 = temp1;
				signofnumber = !(signofnumber);
			}
		}
		for (i = 0; i < arr1.length; i++)
		{
			System.out.println(arr1[i]);
		}
	}
}

#!/usr/bin/env python

import sys

def comparator(val, positive):
    return True if val > 0 and positive else False

def alternate(vals, positive):
    if not vals:
        return
    skipped = []
    for i in range(len(vals)):
        if comparator(vals[i], positive):
            return [vals[i]] + alternate(skipped + vals[i+1:], not comparator)
        else:
            skipped.append(vals[i])
    return vals

if __name__ == '__main__':
    vals = [int(val.strip()) for val in sys.argv[1].split(',') if val.strip()]
    print ','.join([str(val) for val in alternate(vals, True)])

Test:

./negposalternate.py -2,3,4,5,-1,-6,7,9,1
3,-2,4,5,-1,-6,7,9,1

Insertion Sort uses O(1) auxiliary space, so we can use that as a base and do some modifications to suit for this problem.

int counter = 0
for (int j = 1; j < list.length; j ++) {
     if (counter%2 == 0 and list[j] > 0 and list[j-1] < 0) {
        value = list[j-1]
        list[j-1] = list[j]
        list[j] = value
    } else if (counter%2 == 1 and list[j] < 0 and list[j-1] > 0) {
        value = list[j-1]
        list[j-1] = list[j]
        list[j] = value
    }
    counter ++
}

-2,3,4,5,-1,-6,7,9,1
j = 1 -> counter = 0 even, 3 > 0 and -2 < 0, swap => 3,-2,4,5,-1,-6,7,9,1
j = 2 -> counter = 1 odd, 4 > 0 and -2 < 0, do nothing
j = 3 -> counter = 2 even, 5 > 0 and 4 > 0, do nothing
j = 4 -> counter = 3, odd, -1 < 0 and 5 > 0, swap => 3,-2,4,-1,5,-6,7,9,1
j = 5 -> counter = 4, even, -6 < 0 and 5 > 0, do nothing
j = 6 -> counter = 5, odd, 7 > 0 and -6 < 0, do nothing
j = 7 -> counter = 6, even, 9 > 0 and 7 > 0, do nothing
j = 8 -> counter = 7, odd, 1 > 0 and 9 > 0, do nothing
final result => 3, -2, 4, -1, 5, -6, 7, 9, 1

but your code more extra space

a = [1,2,45,45,6,878,7,96,87,8,-909,-7,-5,-5,-4,-4,6,-7,-5,-3,-3,6,7,-1, -1];
pi = 0;
ni = 0;
y = 0;
x = 0;

while (y < len(a)-1):
    for x in range(y,len(a)-1):
        if (a[x]>0) and (a[x+1])<0:
            x=x+2;
        else: 
            break;

    while (x >0) and (a[x]<0): x = x-1;
    pi = x;
    while (x < len(a)) and (a[x]>0): x = x+1;
    ni = x;
     
    print x, pi, ni
    if pi%2 == 0 :
        a = a[:pi+1] + [a[ni]] + a[pi+1:ni] + a[ni+1:];
    else :
        a = a[:pi] + [a[ni]] + a[pi:ni] + a[ni+1:];

    if(y == pi+2):
        break
    else:
        y = pi+2;

print a

a = [1,2,45,45,6,878,7,96,87,8,-909,-7,-5,-5,-4,-4,6,-7,-5,-3,-3,6,7,-1, -1];
pi = 0;
ni = 0;
y = 0;
x = 0;

while (y < len(a)-1):
    for x in range(y,len(a)-1):
        if (a[x]>0) and (a[x+1])<0:
            x=x+2;
        else: 
            break;

    while (x >0) and (a[x]<0): x = x-1;
    pi = x;
    while (x < len(a)) and (a[x]>0): x = x+1;
    ni = x;
     
    print x, pi, ni
    if pi%2 == 0 :
        a = a[:pi+1] + [a[ni]] + a[pi+1:ni] + a[ni+1:];
    else :
        a = a[:pi] + [a[ni]] + a[pi:ni] + a[ni+1:];

    if(y == pi+2):
        break
    else:
        y = pi+2;

print a

public static void main(String args[]){
int[] sat = {-2,3,4,5,-1,-6,7,9,1};


for(int i=0;i<sat.length-2;i=i+2){
int temp=0;
if(sat[i]<0 && sat[i+1]>0 && sat[i+2]>0){
temp = sat[i];
sat[i] = sat[i+1];
sat[i+1] = temp;

}else if(sat[i]>0 && sat[i+1]>0 && sat[i+2]<0){
temp = sat[i+1];
sat[i+1] = sat[i+2];
sat[i+2] = temp;
}
}

for(int j=0;j<sat.length;j++){
System.out.print(sat[j] + " ");
}

}

List<int> Alternate(List<int> input)
{
	int posPtr=0,negPtr=0;
	Pair<int,int> tempIndexValuePair;	
	for(int index=0;index < input.Length; input++)
	{
		if(index%2==0)
		{
			// If even index then find positive integer
			while(posPtr < input.Length)
			{ 
				if(tempIndexValuePair.Key == posPtr  && tempIndexValuePair.Value > 0)
				{
					int tempValue = input[index];
					input[Index] = tempIndexValuePair.Value;
					tempIndexValuePair = new Pair<int,int>(index, tempValue);
					break;
				}
				elseif(input[index] > 0)
				{
					tempIndexValuePair = new Pair<int,int>(index,input[index]);
					input[index] = input[posPtr];
					break;
				}
				posPtr++;
			 }
			if(posPtr > input.Length) break;

			
		}
		else
		{
			//find next negative integer
			Similar to above
		}
	}
	
	// Copy over the remaining array if there is excess of positive or negative  
}