Array Problem

general
1

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 .

2

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 :slight_smile:

3

What you need is a compare function with std::sort

#include

#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[5]={-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
4

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
5

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 .

6

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 :slight_smile:

7

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

1 Like
8

You said that

O(1) space complexity is required .

So I went with O(1) approach :confused:

1 Like
9

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

10

Nopes. But in interview they will ask you to do that in O(1) without arrays we well, cant they? :slight_smile:

You just have to replace the print statement with Ans[index++]=arr[i] anyways.

1 Like
11

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

1 Like
12

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

13

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