 # Array Problem

Give an array which has n integers,it has both positive and negative integers.Now you need sort this array in a special way.After that,the negative integers should in the front,and the positive integers should in the back.Also the relative position should not be changed.
eg. -1 1 3 -2 2 ans: -1 -2 1 3 2.

O(n)time complexity and O(1) space complexity is required .

What I tried so far …

``````public static void sortNegPosSwap(int[] arr)
{
int[] neg = new int[arr.length];
int numNeg = 0;
int currNeg = -1;
int numNegSoFar = 0;
for(int i = 0; i < arr.length; i++)
{
if(arr[i] < 0)
{
neg[numNeg++] = arr[i];
}
}
for(int i = arr.length - 1; i >= 0; i--)
{
if(numNegSoFar != 0 && arr[i] >= 0)
{
arr[i + numNegSoFar] = arr[i];
}
if(arr[i] < 0)
{
numNegSoFar++;
}
}
for(int i = 0; i < numNeg; i++)
{
arr[i] = neg[i];
}
}
``````

But the above code is of O(nlogn) complexity . Can someone suggest better ??
Thanks in advance What you need is a compare function with std::sort

#include

using namespace std;

bool compare(int i,int j)

{

``````if(i<0 && j<0)

return false;

else if(i>=0 && j>=0)

return false;

else

return i<j;
``````

}

int main() {

``````// your code goes here

int a={-1,1,3,-2,2};

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

cout<<a[i]<<" ";

cout<<"\n";

sort(a,a+5,compare);

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

cout<<a[i]<<" ";

return 0;
``````

}

EDIT

For your complexity constraints , you should point a variable to first positive and other to first negative . Whenever you face a positive and negative in unsorted position and move the pointers to next positive and next negative respectively.

1 Like

You say that relative order must be preserved, right? And just that negative numbers should come first and positive hereafter?

``````for(i=0;i<n;i++)
{
if(number is negative)
print(arr[i]);
}

for(i=0;i<n;i++)
{
if(number is positive)
print(arr[i]);
}
``````

Did you give this algo a try?

1 Like

I understand this but I need not print the answer directly I have to store it in an array and what I am looking for is an optimized approach of O(n) time complexity . I have reduced the code to O(nlogn) as mentioned above .

Thanks a ton man …I was not able to get this idea … of using modified sort function as I was asked to code it in Java .

Thanks a lot You are welcome . In my opinion , c++ can greatly help you in your logic development . It is your choice though .

1 Like

You said that

``````O(1) space complexity is required .
``````

So I went with O(1) approach 1 Like

Yeah that’s true but I want to store it in an array too BTW with storing in an array I don’t think we can reduce the space complexity to O(1) . Can we ?

Nopes. But in interview they will ask you to do that in O(1) without arrays we well, cant they? You just have to replace the print statement with `Ans[index++]=arr[i]` anyways.

1 Like

well vijju’s approach can be done in O(2n) whcih translates to O(n) . But it will take some extra space .

1 Like

I also feel the same that it will take some extra space . If not then could you please explain ?

Well cp is all about time-space tradeoff . You have to live with it //