Google Interview Question
Country: United States
This may not be a google question, nevertheless it was interesting to solve.
The following is a solution in O(1) space and O(N) time
and maintaining the order of entries :-
int nextPos(int *list, int size) {
static int np = -1;
static int next = -1;
int retVal = -1;
if (np == -1) {
// initialize
np = 0;
while (np < size && list[np] < 0) {
np++;
}
if (np < size) {
next = list[np];
}
}
retVal = next;
np++;
while (np < size && list[np] < 0) {
np++;
}
next = (np < size) ? list[np] : -1;
return retVal;
}
int nextNeg(int *list, int size) {
static int nn = -1;
static int next = 1;
int retVal = 1;
if (nn == -1) {
// initialize
nn = 0;
while (nn < size && list[nn] >= 0) {
nn++;
}
if (nn < size) {
next = list[nn];
}
}
retVal = next;
nn++;
while (nn < size && list[nn] >= 0) {
nn++;
}
next = (nn < size) ? list[nn]: 1;
return retVal;
}
void makeAlternate(int *list, const NSUInteger size) {
// int list[] = {1, 2, 3, -4, -1, 4};
// int size = 6;
if (size < 1 || !list) {
return;
}
int np = nextPos(list, size);
int nn = nextNeg(list, size);
int pos = 0;
bool fillPos = (list[pos] < 0);
if (!fillPos) {
np = nextPos(list, size);
} else {
nn = nextNeg(list, size);
}
pos++;
while (pos < size && np != -1 && nn != 1) {
if (fillPos) {
list[pos] = np;
np = nextPos(list, size);
} else {
list[pos] = nn;
nn = nextNeg(list, size);
}
pos++;
fillPos = !fillPos;
}
// either arr finished or all negative or all positive
if (pos < size) {
if (nn == 1) {
while (pos < size) {
list[pos++] = np;
np = nextPos(list, size);
}
} else {
while (pos < size) {
list[pos++] = nn;
nn = nextNeg(list, size);
}
}
}
// print the arr
for (int i = 0; i < size; i++) {
printf("%i, ", list[i]);
}
}
I had trouble making this algo work. Here's where I am stuck up-
Consider the input --- 6, 5, 4, 3, 2, 1, -1, -2.
The algo correctly fills 6, -1, 5, -2 in the 0th to 3rd positions, respectively.
However consider the while loop in makeAlternate for
pos == 4 && fillPos == true && np == 4
(with
next == 3
in nextPos):
list[pos] = np;
np = nextPos(list, size);
The above code overwrites list[4] (ie. 2) with 4, before calling nextPos. nextPos will return 3, and start looking from index 4. list[4] now contains 4. So nextPos loses 2.
In fact, there can be no constant space complexity using the above algo. Each call to nextPos is associated with two overwrites to list. So nextPos must store two positive number for each call. However, only one positive number is used up in each call. So the positive numbers that need to be stored in nextPos build up according to the following recursion:
c(i) = c(i - 1) + 2
whose solution is not in O(n).
Any ideas on how to proceed?
Thank You.
I'm not sure that this is actually possible. The naïve solution yields a runtime of O(n^2). Essentially start from the beginning and have two "pointers" and as soon as you reach a number that shouldn't be at that index, shoot the second pointer forward to find your next number and swap/shift everything accordingly. If you wanted this in O(n) time, you could use the quicksort partition method to partition around a value of 0. Upon doing this you could take one number from the negatives an one from the positives and do some swapping and that'd be O(n) but that wouldn't maintain order. So I don't see a way to do this in O(n) while maintaining order.
It's not n^2. Since both pointers will need to iterate thru the array once. So it's O(2N)
Check this link:
geeksforgeeks.org/rearrange-array-alternating-positive-negative-items-o1-extra-space/
Edit: The following cases would probably break this, so it is back to being a gross mystery. I previously assumed that if the left-most pos/negIndex passed the rightMost, that it would swap with the overflowIndex instead, but it is more tricky than that- especially if you end up with the leftMost between the overflow and rightMost. This is an obnoxious question that is hopefully a fake. It would make sense if it was less constrained in the beginning and the last set of constraints was a hail-mary for discussion, but it is terrible.
When it breaks:
input = {1, 2, 3, 4, 5, 6, -1, -2, -3, 7, 8, -4}
or
input = {1, 2, 3, 4, 5, 6, -1, 7, -2, 8, -3, 9}
I believe that you can accomplish this by using a third pointer, but keeping track of everything is annoying. You are basically simulating three arrays in memory using one array- you will have a positive pointer, a negative pointer, an overflow pointer.
Pretend that you do not have a memory constraint: You can go through the input array and create two separate arrays- one for negative and one for positive numbers. You would then go through the input array again, filling in the even/odd positions with the next number from the appropriate array. Ex:
input[] = {1, 2, 3, -4, -1, 4}
pos[] = {1, 2, 3, 4}
neg[] = {-4, -1}
To solve the problem with the memory constraint, as you will iterate through the input array, keeping pointers to the next positive and next negative number. This won't work if you encounter a long series of positives or negatives, unless you want to constantly shuffle the values (n^2), which is why you need an overflow pointer. For the overflow pointer, you can assume that it will always be behind at least one of the other pointers, so its values should be same as the farthest pointer. Ex:
iterPos = 3
posIndex = 3
negIndex = 7
overflowIndex = 6 <- overflow value will be negative, so iterating through its values won't be confused with real positive values, then the end of the array will be bounded by the negIndex
// Iteration 2
input = {1, 2, 3, -4, -1, 4}
iterPos = 1 <- odd positions are negative numbers, even are positive
posIndex = 1
negIndex = 3
overflowIndex = -1
// Iteration 3
input = {1, -4, 3, -2, -1, 4}
iterPos = 2
posIndex = 2
negIndex = 4
overflowIndex= 3 <- should be favored over posIndex
// Iteration 4
input = {1, -4, 2, -3, -1, 4}
iterPos = 3
posIndex = 5 <- swapped old value to overflow
negIndex = 4
overflowIndex= 3 <- this does not really have a negative value, you can assume any negatives between here and negIndex are overflowed positive values
There are of course tons of edge cases to keep track of when dealing with 4 indices and even vs. odd positions, which is why I do not have code yet- this would be a terrible question to be asked if the interviewer expected code. You can run through this with bigger data sets as a proof of concept- that is another annoying thing, you need to have larger data sets to verify (it takes some effort to believe):
lotsOfNums = {1, 2, 3, 4, 5, 6, 7, -1, 12, -2, -3, -4, -5}
lotsOfPositives = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, -1}
This is not a Google question. They don't enforce such space/time restrictions.
Stop posting questions which you haven't experienced yourself.
I think the following code should work
public static void alternate(int[] a) {
int p = 1;
int n = 1;
boolean findPositive = false;
if (a[0] < 0) {
findPositive = true;
}
int t;
for (int i = 1; i < a.length && p < a.length && n < a.length; i++) {
if (findPositive) {
while (p < a.length && a[p] < 0) {
p++;
}
t = p++;
} else {
while (n < a.length && a[n] >= 0) {
n++;
}
t = n++;
}
if (t<a.length) {
swap(a, t, i);
findPositive = !findPositive;
}
}
}
@Jim: for {-1 -4 2 3 4 5 6 7 -1} input, this is returning {-1 2 -4 3 -1 5 6 7 4 } which is correct. Can you please point out the mistakes that you see.
@Vnikku: for {-1 -4 2 3 4 5 6 7 -1} input, this is returning {-1 2 -4 3 -1 5 6 7 4 } , which is incorrect, because it does not preserve the order of positive numbers. You see input 4 is before 5,6,7, but your output 4 is after those.
Consider input array in arr and the indices i (for insertion point), p (index of positive number) and n (index of negative number)
void solve(arr){
int p,n,i;
p=n=-1;
i=0;
// p Points to positive number
// q points to negative number
for(int j=0;j<arr.length;j++)
if(arr[j]=>0 && p < -1 )
p=j;
else if(arr[j]<0 && n < -1)
n=j;
while(p<arr.length && n<arr.length){
if(i%2==0){
// negative number to insert
if(arr[i] >= 0){
int tmp = arr[i];
arr[i] = arr[n];
i++;
shift(arr,i,n-1);
arr[i]=tmp;
++p; // shifted by one
}
// update n
for(;n<arr.length && arr[n]>0;n++)
}
else{
// to insert positive number
if(arr[i]<0){
int tmp = arr[i];
arr[i] = arr[p];
i++;
shift(arr,i,p-1);
arr[i] = tmp;
++n; // shifted by one
}
// update p
for(;p<arr.length && p>=0; p++)
}
}
}
void shift(int *arr,int first,int last){
// don't care about last+1;
for(int i=last; i>=first; i--)
arr[last + 1] = arr[last];
}
#!/usr/bin/env python
def arr_alt(arr):
pos_arr = [i for i in arr if i >= 0 ]
neg_arr = [i for i in arr if i < 0 ]
out_arr = []
if len(pos_arr) > len(neg_arr):
i = 0
while i < len(pos_arr):
if i < len(neg_arr):
out_arr.append(neg_arr[i])
out_arr.append(pos_arr[i])
i += 1
else:
i = 0
while i < len(neg_arr):
out_arr.append(neg_arr[i])
if i < len(pos_arr):
out_arr.append(pos_arr[i])
i += 1
return out_arr
if __name__ == '__main__':
print arr_alt([-5,-2,5,2,4,7,1,8,0,-8])
O(N) Since positive and negative only move forward and once one of them reach the end of array, break.
(function() {
'use strict';
var swap = function(inputAry, m, n) {
var tmp = inputAry[n];
inputAry[n] = inputAry[m];
inputAry[m] = tmp;
};
var npArray = function(inputAry) {
//index for positive and negative value.
var positive = 0;
var negative = 0;
var last = 0;
var i = 0;
var length = inputAry.length;
//loop through input array. O(N)
for (i = 0; i < length; i++) {
positive = positive < i ? i : positive;
negative = negative < i ? i : negative;
if (last >= 0 && inputAry[i] >= 0) {
while (negative < length && inputAry[negative] >= 0) {
negative++;
}
if (negative < length) {
swap(inputAry, negative, i);
negative--;
}
//end of loop. done.
if (negative === length) {
break;
}
}
if (last < 0 && inputAry[i] < 0) {
while (positive < length && inputAry[positive] < 0) {
positive++;
}
if (positive < length) {
swap(inputAry, positive, i);
positive--;
}
//end of loop. done.
if (positive === length) {
break;
}
}
last = inputAry[i];
}
return inputAry;
};
var inputAry = [1, 2, 3, -4, -1, 4];
console.log(npArray(inputAry));
inputAry = [-5, -2, 5, 2, 4, 7, 1, 8, 0, -8];
console.log(npArray(inputAry));
})();
Thanks zect. Modify the swap function to insert function.
(function() {
'use strict';
var arrayInsert = function(inputAry, m, n) {
var tmp = inputAry.splice(m, 1);
inputAry.splice(n, 0, tmp[0]);
};
var npArray = function(inputAry) {
//index for positive and negative value.
var positive = 0;
var negative = 0;
var last = 0;
var i = 0;
var length = inputAry.length;
//loop through input array. O(N)
for (i = 0; i < length; i++) {
positive = positive < i ? i : positive;
negative = negative < i ? i : negative;
if (last >= 0 && inputAry[i] >= 0) {
while (negative < length && inputAry[negative] >= 0) {
negative++;
}
if (negative < length) {
arrayInsert(inputAry, negative, i);
negative--;
}
//end of loop. done.
if (negative === length) {
break;
}
}
if (last < 0 && inputAry[i] < 0) {
while (positive < length && inputAry[positive] < 0) {
positive++;
}
if (positive < length) {
arrayInsert(inputAry, positive, i);
positive--;
}
//end of loop. done.
if (positive === length) {
break;
}
}
last = inputAry[i];
}
return inputAry;
};
var inputAry = [1, 2, 3, -4, -1, 4];
console.log(npArray(inputAry));
inputAry = [-5, -2, 5, 2, 4, 7, 1, 8, 0, -8];
console.log(npArray(inputAry));
})();
Similar to my algorithm. But similar to my solution too, the complexity is not strictly O(n). Look at the two statements:
positive = positive < i ? i : positive;
and
while (positive < length && inputAry[positive] < 0) {
positive++;
}
The positive (as well as the negative) index does not always move forward, because the first statement may reset it back to current index, thus the while loop may be executed several times. Refer my comments regarding time complexity below.
#include<iostream>
using namespace std;
void reorder(int a[],int size,int maximum)
{
int positive=0,negative=0,current;
while(a[positive]<0)
positive++;
while(a[negative]>0)
negative++;
for(current=0;current<size;current++)
{
if(current%2==0)
{
if(positive<current)
{
if(positive%2)
{
a[current]=a[current]*maximum+a[positive]/maximum+1;
}
else
a[current]=a[current]*maximum+a[positive]/maximum;
}
else
a[current]=a[current]*maximum+a[positive];
positive++;
while(a[positive]<0)
positive++;
}
else
{
if(negative<current)
{
if(negative%2)
{
a[current]=a[current]*maximum+a[negative]/maximum;
}
else
a[current]=a[current]*maximum+a[negative]/maximum-1;
}
else
a[current]=a[current]*maximum+a[negative];
//cout<<a[current];
negative++;
while(a[negative]>0)
negative++;
}
}
}
void maintain(int a[],int maximum, int size)
{
for(int i=0;i<size;i++)
{
if(i%2)
{
if(a[i]<0)
{
a[i]*=-1;
a[i]%=maximum;
a[i]*=-1;
}
else
{
a[i]%=maximum;
a[i]-=maximum;
}
}
else
{
if(a[i]<0)
{
a[i]*=-1;
a[i]%=maximum;
a[i]=maximum-a[i];
}
else
{
a[i]%=maximum;
}
}
}
}
int main()
{
int x, maximum=0;
cin>>x;
int a[x];
for(int i=0;i<x;i++)
cin>>a[i];
for(int j=0;j<x;j++) /*calculation for maximum*/
{
if(a[j]<0)
{
if(maximum<-1*a[j])
maximum=-1*a[j];
}
else{
if(maximum<a[j])
maximum=a[j];
}
}
maximum+=1;
reorder(a,x,maximum);
for(int i=0;i<x;i++)
cout<<a[i]<<" ";
cout<<endl;
maintain(a,maximum,x);
for(int i=0;i<x;i++)
cout<<a[i]<<" ";
}
import java.util.*;
public class HelloWorld{
public static void main(String []args){
int a[] = {9, 2, 3, -3, -1, 4};// if a[p]{p=q-1}*a[q]<0; continue; else,a[q]*a[q+1~last] until value<0, mark q+pos, make a[q+pos]=a[q+pos-...]until a[q];
int p=0;
int q=1;
int len=a.length;
if(a[0]>0)
{
int pointer =1;
while(pointer<len)
{
if(a[pointer]>0)
{pointer++;
continue;
}
else
{
int temp=a[pointer];
while(pointer>p)
{
a[pointer]=a[--pointer];
}
a[p]=temp;
break;
}
}
}
while(q<len)
{
if(a[p]*a[q]<0)
{
p++;
q++;
continue;
}else{
int pointer=q;
while(pointer<len)//to find first fitted point
{
if(a[q]*a[pointer]>0)
{
pointer++;
continue;
}else
{
int temp=a[pointer];
while(pointer>q)
{
a[pointer]=a[--pointer];
}
a[q]=temp;
break;
}
}
p++;
q++;
continue;
}
}
for(int t=0;t<a.length;t++)
{
System.out.print(a[t]);
}
}
}
import java.util.ArrayList;
public class Alternate
{
public static void main(String[] args)
{
int[] a = new int[] {-5, -2, 5, 2, 4, 7, 1, 0, 8, -8} ;
ArrayList<Integer> negative = new ArrayList<Integer>() ;
ArrayList<Integer> positive = new ArrayList<Integer>() ;
for(int x : a)
{
if(x < 0)
negative.add(x) ;
else
positive.add(x) ;
}
int nSize = negative.size() ;
int pSize = positive.size() ;
int[] b = new int[nSize+pSize] ;
int nCount = 0 , pCount = 0 ;
for(int i = 0 ; i < (nSize + pSize) || nCount < nSize || pCount < pSize ; i ++)
{
if(i % 2 == 0 && nCount != nSize)
b[i] = negative.get(nCount ++) ;
else if(i % 2 != 0 && pCount != pSize)
b[i] = positive.get(pCount ++) ;
else if(nCount == nSize && pCount != pSize)
b[i] = positive.get(pCount ++) ;
else if(pCount == pSize && nCount != nSize)
b[i] = negative.get(nCount ++) ;
}
for(int x : b)
System.out.print(x+" ");
}
}
Amortized time complexity O(n), worse case O(n^2). Space complexity O(1) using constant stack memory.
The idea is to alternately arrange the head of a sub sequence to desired positive or negative element then arrange the tail of the sub sequence. The desired head of the sub sequence maybe the head itself or the first element that meets the polar criterion in the tail. Searching for the desired head is expected to constant, but worse case can go linear.
The implementation in Scala
//Overall time complexity is O(n), worse case O(n^2). Space complexity is O(1) for recursion
def arrange(data:Array[Int], index:Int, negative:Boolean) { //the recursion alone is O(n)
if (data(index)<0^negative) { // data(index)<0 is false, positive leading, need swap
var next = index+1
while (next<data.length && (data(next)<0^negative)) next+=1 //average case O(1), worse case O(n)
if (next>=data.length) return //no more data to swap, finished
var temp = data(next)
data(next)=data(index)
for (i<-next-1 to index by -1) { //shift all positive numbers before the next negative number to the left
data(i+1)=data(i)
}
data(index) = temp
}
arrange(data, index+1, !negative)
}
The same implementation in Java, with a bug fix applicable to Scala version. Note in the worst case when search for the desired head reaches the end of array, the recursion will end. So the algorithm will run full array scan at most once.
public static void arrange(int[] data) {
arrange(data, 0, true);
}
public static void arrange(int[] data, int index, boolean negative) {
if (data[index]<0 ^ negative) { //data[index]<0 is false, ie, head is positive, need swap
int next = index+1;
while (next<data.length && (data[next]<0 ^ negative)) next++;
if (next>=data.length) return; //done. Search reaches the end, no more work to do
int temp = data[next]; //the new head
for (int i=next-1; i>=index; i--) data[i+1] = data[i]; //shift elements between index and next to the right
data[index] = temp;
}
if (index<data.length-1) arrange(data, index+1, !negative);
}
public class HelloWorld{
public static void main(String []args){
int[] array = {-1, -4, 2, 3, 5, 6, 7, -1};
int[] result = alt(array);
for(int i = 0; i < result.length; i++) {
System.out.print(result[i] + " ");
}
System.out.println();
}
public static int[] alt(int[] scram) {
int[] result = scram;
int[] neg = new int[scram.length];
int[] pos = new int[scram.length];
int iPos = 0;
int iNeg = 0;
int pLoc = 0;
int nLoc = 0;
for(int i = 1; i < scram.length; i++) {
if(scram[i] < 0) {
neg[iNeg] = scram[i];
iNeg++;
}
else {
pos[iPos] = scram[i];
iPos++;
}
}
for(int i = 1; i < scram.length; i++) {
if(result[i-1] < 0) {
if( pLoc < iPos ) {
result[i] = pos[pLoc];
pLoc++;
} else {
result[i] = neg[nLoc++];
}
}
else {
if(nLoc < iNeg){
result[i] = neg[nLoc];
nLoc++;
} else {
result[i] = pos[pLoc++];
}
}
}
return result;
}
}
#include<stdio.h>
#include<stdlib.h>
void algo2(int a[],int n)
{
int i=0,j=0,flag=0;
if(a[i]<0)
{
while(i<n && j<n)
{
if(flag==0)
{
if(a[i]<0)
{
printf("%2d ",a[i]);
i++;
flag=1;
}
else
i++;
}
if(flag==1)
{
if(a[j]>0)
{
printf("%2d ",a[j]);
j++;
flag=0;
}
else
j++;
}
}
if(i<n)
{
for(;i<n;i++)
{
if(a[i]<0)
printf("%2d ",a[i]);
}
}
else if(j<n)
{
for(;j<n;j++)
{
if(a[j]>0)
printf("%2d ",a[j]);
}
}
}
else if(a[i]>=0)
{
flag=0;i=0,j=0;
while(i<n && j<n)
{
if(flag==1)
{
if(a[i]<0)
{
printf("%2d ",a[i]);
i++;
flag=0;
}
else
i++;
}
if(flag==0)
{
if(a[j]>0)
{
printf("%2d ",a[j]);
j++;
flag=1;
}
else
j++;
}
}
if(i<n)
{
for(;i<n;i++)
{
if(a[i]<0)
printf("%2d ",a[i]);
}
}
else if(j<n)
{
for(;j<n;j++)
{
if(a[j]>0)
printf("%2d ",a[j]);
}
}
}
}
int main()
{
int *a,i,n,data;
printf("\nenter no. of element : ");
scanf("%d",&n);
a=(int*)malloc(sizeof(int)*n);
printf("\nenter %d positive or negative elements : ",n);
for(i=0;i<n;i++)
{
scanf("%d",&data);
a[i]=data;
}
printf("\n");
algo2(a,n);
}
I can't get 0(n) because the vector insert and erase involves manipulating the array however
{{
void move_from_to(vector<int>& a, int from, int to) {
int val = a[from];
a.erase(a.begin() + from);
a.insert(a.begin() + to, val);
}
void pos_neg(vector<int>& a) {
int nIdx = 0;
int pIdx = 1;
for ( int i = 0; i < a.size(); ++i ) {
if ( a[i] < 0 ) {
if ( nIdx < i ) {
move_from_to(a, i, nIdx);
}
nIdx += 2;
} else {
if (pIdx < i ) {
move_from_to(a, i, pIdx);
}
pIdx += 2;
}
}
}
}}
Not in O(1) space. But O(n) in time complexity... I guess so
class AlternateProg {
public static void main(String args[]) {
//int[] arr = {1, -22, -23, -4, 4,-2,-5,6,-7,7,-8,-9};
//int[] arr = {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8};
int[] arr = { 1 ,2 ,3,4,5,6 };
AlternateProg.printArray("Input Array", arr);
AlternateProg.printArray("Output Array", AlternateProg.getShufflePostive(arr));
AlternateProg.algo2(arr,arr.length);
}
public static void printArray(String type, int[] arr) {
System.out.println("\n"+type+" :");
for(int elem: arr) {
System.out.print(elem +" ");
}
}
public static int[] getShufflePostive(int[] arr) {
int neg = -1,temp = 0;
int[] arr2 = new int[arr.length];
for(int i = 0, last_index=arr.length-1 ; i < arr.length; i++) {
if( arr[i] < 0 )
arr2[++neg] = arr[i];
else
arr2[last_index--] = arr[i];
} // end of for loop
for(int i =0; i <= neg; i++) arr[i] = arr2[i];
for(int i =arr.length-1, j = neg+1; i > neg; )
arr[j++] = arr2[i--];
if(neg >= 0){
//move extra elements to the end of array
if( arr.length-neg > neg){ // more positive
for(int i = arr.length-1; i > neg * 2 ; i--){
arr2[i] = arr[i];
}
for(int neg_pos = 1, pos_pos=neg+1,i=1; neg_pos <= neg; neg_pos++, i +=2, pos_pos++ ) {
arr2[neg_pos*2] = arr[neg_pos];
arr2[i] = arr[pos_pos];
}
}else{ // more negative
for(int i=neg,pos = arr.length-1; i >= arr.length - neg; i--,pos--) {
arr2[pos] = arr[i];
}
for(int neg_pos = 1, pos_pos=neg+1,i=1; pos_pos <= arr.length-1; neg_pos++, i +=2, pos_pos++ ) {
arr2[neg_pos*2] = arr[neg_pos];
arr2[i] = arr[pos_pos];
}
}
}
return (neg >= 0)? arr2 : arr;
}
}
from itertools import zip_longest
def leapfrog(lst):
pos, neg, final = list(), list(), list()
[neg.append(y) if y < 0 else pos.append(y) for y in lst]
for pair in zip_longest(neg, pos):
x, y = pair
if x is not None and y is not None:
final.append(x)
final.append(y)
elif x is not None:
final.append(x)
elif y is not None:
final.append(y)
return final
Assume the test the array[], and we have a i loop from 0 to array.length-1.
My solution is to maintain an next_negative, which indicate the next negative element in the unsorted array, and next_positive, which indicate the next positive element in the unsorted array.
The both next_negative and next_positive only traverse the array one time.
Each time, test if the current i element is in right position or not. If it is right, check the next one.
If it is not in right position, we do following:
If the current position should be a negative, let next_negative traverse from its own position until it reach the first negative element in unsorted array. If next_negative is less than i, let next_negative be i+1.
If the current position should be a positive, let next_positve traverse from its own position until it reach the first positive element in un sorted array. If next_positive is less than i, let next_positive be i+1.
Now we have found the right position that we should put into the position array[i]. The critical matter here, is that we shouldnt simply do switch(a[i], a[next_negative]) or switch(a[i], a[next_positive]), because this would lose the original sort. Instead, we should do rotate.
For example, -1 (-2) -3 -4 (1) 2 3 4 5 6 7 8
We found the -2 is not in right position. After we traverse the next_positive, we found 1 should be there, since 1 is the first positive number in the unsorted array. So we should do rotate like this:
-1 (1 -2 -3 -4) 2 3 4 5 6 7 8
Then, it would be like this:
-1 1 (-2) -3 -4 2 3 4 5 6 7 8
-1 1 -2 (-3) -4 2 3 4 5 6 7 8
-1 1 -2 (-3) -4 (2) 3 4 5 6 7 8
-1 1 -2 (2 -3 -4) 3 4 5 6 7 8
Here, we can see we did the rotate, which helps to maintain the original sort.
Ok, now, I want to say, it won't be solved in O(n) time by this.
But we want an O(n) time, my answer is that if the array is given by form of linkedList, it can be solved in O(n) time.
O(n) solution, O(1) space, order not maintained.
void alt_reorder(int* a, int n)
{
int* p = std::partition(a, a + n, [](int i) { return i < 0; });
if (p - a <= n / 2) std::reverse(a, a + n);
int count = std::min(p - a, n - (p - a)), si = ((a[0] < 0) ? 1 : 0);
for (int i = n - count; i < n; ++i, si += 2) std::swap(a[i], a[si]);
}
Based on description , for the Input: arr[] = {1, 2, 3, -4, -1, 4} , output should be as follows
- faiz August 28, 2014Output: arr[] = {1,-4, 2, -1, 3, 4} since we have to maintain the order of appearance.
Am i right ?