Google Interview Question for Interns


Country: CHINA
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
16
of 28 vote

This can be done in O(nlogn) using divide and conquer scheme. Before starting the algorithm, please see the following observation:

Observation: given an array A, say [1, -2, ..., 4], with n elements, we can get the inverse of A, denoted as A’ (4, …, -2, 1), in \theta(n) time with O(1) space complexity.

The basic idea of the algorithm is as follows:
1. We recursively ‘sort’ two smaller arrays of size n/2 (here ‘sort’ is defined in the question)
2. Then we spend \theta(n) time merging the two sorted smaller arrays with O(1) space complexity.
How to merge?
Suppose the two sorted smaller array is A and B. A1 denotes the negative part of A, and A2 denotes positive part of A. Similarly, B1 denotes the negative part of B, and B2 denotes positive part of B.
2.1. Compute the inverse of A2 (i.e., A2’) in \theta(|A2|) time; compute the inverse of B1 (i.e., B1’) in \theta(|B1|) time. [See observation; the total time is \theta(n) and space is O(1)]
Thus the array AB (i.e., A1A2B1B2) becomes A1A2’B1’B2.
2.2. Compute the inverse of A2’B1’ (i.e., B1A2) in \theta(|A2|) time. [See observation; the total time is \theta(n) and space is O(1)]
Thus the array A1A2’B1’B2 becomes A1B1A2B2. We are done.

Time complexity analysis:
T(n) = 2T(n/2) + \theta(n) = O(nlogn)

- Jason Ding August 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
4
of 8 votes

Time: O(N), Space O(N)

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];
		}
	}

- allenliuzihao October 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@Jason, I like this. Simple and O(n log n). I researched web and nobody claims to have O(n) time and O(1) space algorithm.

- galli October 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
14
of 18 votes

Why O(nlogn) solution when you are using O(N) extra space?
If you are given O(N) extra space then you can do it in O(N) time.

1. Scan the input array and count no. of positive elements (countP) and negative elements (countN).
2. Populate output array (extra space) .
scan input array from left to right
for i = 0 to i = size-1.
3. if arr[i] > 0 then output[countN] = arr[i]; countN++
4. if arr[i] < 0 then output[countP] = arr[i]; countP++

Please take care of boundary cases when there are no -ve or +ve elements in the array.

- varun October 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Jason. I like your three-reversion solution.

- yaojingguo December 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
7
of 9 votes

Time O(N) and space O(1)

public class PosiNegSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int [] nums = {-1, 2, 4, -8, 10, 9, 100, -3, 2};
		for(int i : posiNegSort(nums))
			System.out.print(i + " ");
	}
	public static int[] posiNegSort(int [] nums){
		int p = 0; 
		int q = 0;
		while ( q < nums.length){
			while (nums[p] < 0)
				p++;
			q = p;
			while(q < nums.length && nums[q] > 0 )
				q++;
			if (q == nums.length)
				break;
			for(int i = q; i > p; i--){
				int t =nums[i-1];
				nums[i-1] = nums[i];
				nums[i] = t;				
			}
		}
		return nums;
	}
}

- Doug December 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
3
of 5 votes

@doug,
if you have an array like this {1, 2, 3, 4, 5, -5, -4, -3, -2, -1}

Time is (N^2) for worse case, but still a good solution.

- qxixp January 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

please let me know if this has any prob ?

/*
============================================================================
Author : novice_programmer

Description : Given an array which has n integers. It has both positive and negative integers.Now you need to sort this array in such a way that,the negative integers should be in the front,and the positive integers should at the back.Also the relative position should not be changed.
eg. -1 1 3 -2 2 ans: -1 -2 1 3 2.Required running time complexity is O(N) and the space complexity is O(1)
Created Date : 26-JAN-2014
===========================================================================
*/
#include<stdio.h>


void sort_array(int arr[],int n)
{
int count =0;
int temp1=0;
int pos_to_fill_with_positive_num=0;
int pos1=0;
int pos2=0;
int just_moved =0;
int num_remaining=0;

for(int i=0;i<n;i++)
{
if(arr[i]<;0)
{
count++;
}
}
pos1 = count;
num_remaining=count;
for(int i=0;i<n;i++)
{
if(arr[i]<;0)
{
temp1=arr[pos2];
arr[pos2]=arr[i];
arr[i]=temp1;
pos2++;
if(pos1>=i && i>count)
{pos1++;
just_moved=1;
}

num_remaining--;
}
else
{
if(pos2==count)
break;
else if((i>=count) && (i<pos1) &&(!just_moved))
continue;
else if(just_moved)
{
just_moved=0;
temp1=arr[i];
arr[i]=arr[pos2];
arr[pos2]=temp1;
}
else
{

if(i<count)
{
temp1=arr[pos1];
arr[pos1]=arr[i];
if((pos_to_fill_with_positive_num>=pos2)&&(pos_to_fill_with_positive_num<count))
arr[pos_to_fill_with_positive_num]=temp1;
else if(pos_to_fill_with_positive_num<count)
arr[++pos_to_fill_with_positive_num]=temp1;
else
{
pos_to_fill_with_positive_num=pos2;
arr[pos_to_fill_with_positive_num]=temp1;
}
pos_to_fill_with_positive_num++;
pos1++;
}
else
{
temp1=arr[pos1];
arr[pos1]=arr[pos_to_fill_with_positive_num];
arr[pos_to_fill_with_positive_num]=temp1;
pos_to_fill_with_positive_num++;
pos1++;
}
}
}

if(num_remaining==0)
break;
}
}

void main()
{
int n = 9;
int arr[9]={-1,1,3,4,6,-3,1,-2,2};
//int arr[7]={-1,3,-2,4,5,-5,9};
//int arr[5]={-1,1,3,-2,2};
printf("\input array:");
for(int i=0;i<n;i++)
printf(" %d ",arr[i]);
sort_array(arr,n);
printf("\noutput array");
for(int i=0;i<n;i++)
printf(" %d ",arr[i]);

}

- shekhar January 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

There is a paper showing O(n) time and O(1) space algorithm "Stable minimum space partitioning in linear time." This shouldn't be an interview question.

diku.dk/hjemmesider/ansatte/jyrki/Paper/KP92b.pdf

- lasthope February 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You shouldn't use recursion otherwise the required space won't be O(1). If you implement the same method iteratively it would be O(1) space though.

- Mona February 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@varun merge can be done in place, so this is a O(1) space solution if we do not consider function call stack.

- Jason Ding June 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

public int[] negSort(int[] data)
{
int negCount = 0;
int[] sorted = new int[data.Length];

for (int i = 0; i < data.Length; i++)
{
if (data[i] < 0)
{
sorted[negCount++] = data[i];
}
}

for(int i=0; i< data.Length; i++)
{
if (data[i] > 0) sorted[negCount++] = data[i];
}

return sorted;
}

- Anonymous September 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If there is no repetitions then binary search tree with pre-order traversal will deliver. Again space is the con.

- Orion arm, Laniakea October 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I really like your idea of divide and conquer. However, instead of your merging algorithm I used bubbling of positive integers from the left part to the right. I believe the space complexity is O(1), however, I really don't know the time complexity.

def lastNegIdx(arr,left,right):
    for x in reversed(xrange(left,right+1)):
        if arr[x]<0:
            return x
            
def _merge(array,lIdx,middle,rIdx):
    # no need to do anything if first part negative only or second only positive
    if array[middle] < 0 or array[middle+1] > 0:
        return
    lastPositiveIdx = middle
    lastNegativeIdx = lastNegIdx(array,middle+1,rIdx)
    while array[lastPositiveIdx] > 0:
        for x in range(lastPositiveIdx,lastNegativeIdx):
            array[x],array[x+1]=array[x+1],array[x]
        lastPositiveIdx-=1
        lastNegativeIdx-=1

def _sortNegFirst(array,lIdx,rIdx):
    if rIdx-lIdx <= 1:
        return
    middle = (rIdx+lIdx) / 2
    print middle
    _sortNegFirst(array,lIdx,middle)
    _sortNegFirst(array,middle+1,rIdx)
    _merge(array,lIdx,middle,rIdx)

def sortNegFirst(array):
    _sortNegFirst(array,0,len(array)-1)

- Pida November 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

package util;

public class SachinTest {
	private static Node head;

	public static void main(String[] args) {
		init();
		print();
		System.out.println("----------------");

		Node indexNode = head;
		Node temp = head;
		Node focusNode = null;
		while (temp != null) {
			focusNode = temp.next;
			if (temp.data > 0 && focusNode != null && focusNode.data < 0) {
				Node adjacentNode = indexNode.next;
				Node futureNode = focusNode.next;

				indexNode.next = focusNode;
				focusNode.next = adjacentNode;
				temp.next = futureNode;
				indexNode = focusNode;

				continue;
			}
			temp = temp.next;
		}

		print();
	}

	private static void init() {
		head = new Node(-1);
		Node element1 = new Node(2);
		Node element2 = new Node(-4);
		Node element3 = new Node(-8);
		Node element4 = new Node(3);
		Node element5 = new Node(-10);
		Node element6 = new Node(11);
		Node element7 = new Node(5);
		Node element8 = new Node(-21);
		Node element9 = new Node(-13);

		head.next = element1;
		element1.next = element2;
		element2.next = element3;
		element3.next = element4;
		element4.next = element5;
		element5.next = element6;
		element6.next = element7;
		element7.next = element8;
		element8.next = element9;
	}

	static void print() {
		Node temp = head;
		while (temp != null) {
			System.out.println(temp.data);
			temp = temp.next;
		}
	}

	static class Node {
		int data;
		Node next;

		Node(int data) {
			this.data = data;
		}
	}
}

- sachin.and3 October 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@varun, your solution does not work at all, it doesn't even address the problem.

Lets use the easiest example: [1,-1,2,-2] on your algo:
countP = 2, countN = 2
scanning input from left to right, 1 is > 0 so output[2] = 1. Increment countN for some reason. Next, -1 > 0 so output[2] = -1. Then increment countP for some reason. You already lost the first 1 in the input by overwriting it in your output.

- nphardon August 10, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

let input = [-1, 1, 3, -2, 2]
var finalOutput = [Int]()
var subOutput2 = [Int]()
for num in input {
if num < 0 {
finalOutput.append(num)
}
else {
finalOutput.append(num)
}
}
finalOutput.append(contentsOf:subOutput2)
print(finalOutput)

let input = [-1, 1, 3, -2, 2]
var finalOutput = [Int]()
var subOutput2 = [Int]()
for num in input {
if num < 0 {
finalOutput.append(num)
}
else {
finalOutput.append(num)
}
}
finalOutput.append(contentsOf:subOutput2)
print(finalOutput)

- Algorithm Analyst September 26, 2021 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

let input = [-1, 1, 3, -2, 2]
var finalOutput = [Int]()
var subOutput2 = [Int]()
for num in input {
    if num < 0 {
        finalOutput.append(num)
    }
    else {
        finalOutput.append(num)
    }
}
finalOutput.append(contentsOf:subOutput2)
print(finalOutput)

- Algorithm Analyst September 26, 2021 | Flag
Comment hidden because of low score. Click to expand.
3
of 5 vote

O(nlogn) average case time, O(1) space solution:

1. count negative numbers, let's say K
2. find the first negative with index k > K
3. keep 2 pointers i,j , i tracking positives from the start, j tracking negatives starting from k. swap A[i], A[j] and switch their signs (A[i] = -A[j], A[j] = -A[i])
4. repeat steps 1,2,3 for A[0:K] and A[K,N] seperately
5. fix all signs (we know that the K first should be negatives and the rest positives)

I didn't analyze it any further,
anyone with an idea about worst case complexity?

- uruk hai August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think it is o(nlogn) time.En...this solution is the best here.

- lxfuhuo August 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Worst case time complexity is O(n^2), where n is the input size.

- Epic_coder August 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

why the worst is o(n^2),Could you give a sample.

- lxfuhuo August 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can some one explain what does it mean "relative position should not be changed."? Please also can some one give multiple examples to show how the output should be since the Question is not very clear.

Thanks

- gadaakhil September 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

if NlogN, why not using variation of the merge sort?

- Rooky September 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@Rocky, or quicksort for that matter...

- Anonymous September 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

merge sort is an option, but how you do stable quicksort without additional space?

- uruk_hai September 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@uruk_hai: Stable in-place merge sort exists. Search the web.

- Anonymous September 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@anonymous: true, but I was referring to quicksort

- uruk_hai September 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

Unfortunately, the time complexity in worst case is O(n^2). The formula is:
T(n) = O(n) + T(k) + T(n - k), where k is the number of the negatives. So, if there is only one negative, the formula will change to T(n) = O(n) + T(n - 1) + O(1) = T(n -1) + O(n) = O(n^2).
eg. 1 2 3 4 5 6 -1

- mwxjmmyjfm September 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is O(nlogn). but it can be modified in such a way that one part of the recursive tree is already sorted and you have again repeat same algo for another part.
for better performance sort longest array(+ve or -ve ) and put in recurrence the other array.
eg.
if negative count is smaller
startSearch = 0;
i = first positive index
j = first positive index where it supposed to be
swap(a[i][, a[j]);
if(a[i] < 0){
startSearch = i+1
a[i] = -a[i];
}
i = next positive index;
j++;
if(i == first index positive supposed to){
i = startSearch;
}

after this code positive array will be stable in order with only +ve numbers.
repeat same for another array where only negative should be but still not in order. the number in this array is again -ve and +ve. use same algo.

thus only one tree computation is happening same as finding nth element in randomized partition.

- pankaj September 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The original uruk post doesn't make sense to me. Could someone explain why it works?

- Anonymous September 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

Method 1: O(n log(n)) for arrays
Too complicated to code but leads to O(n log n) for arrays
Start with an array A = [a1 b1 a2 b2 a3 b3 a4 b4 .... ak bk]
where ai and bi are subarrays of positive and negative numbers.
assume ni = len(ai) and mi = len(bi)
Observation:
[a1 b1] --> [b1 a1] in O(max(ni, mi)) which is obtained by repeatedly swaping the first, second, ... elements.
For ni = mi it is obvious. For ni > mi, do it for the first mi, then ignore the first mi since they are in place, do it [ni - mi, mi] positive ones and put them in order. Repeat until you finish after ni swaps.

So recursively do this:
Take [a1 b1 a2 b2] -> [b1 a1 a2 b2] -> [b1 b2 a1 a2]
this is done in max(n1, m1) + max(n1 + n2, m2) < 2n1 + n2 + m1 + m2
For k pairs of [ai bi], we find k / 2 new pairs pairs.
Reapeat the procedure. Note that in the second run, your new value of n1 is (n1 + n2) from previous step.
The same for m1.
For k pairs we need the time complexity T(k) = k / 2 * (2n1 + n2 + m1 + m2) + T(k / 2).
Put averages here: (E[ni] = E[mi] = n / k.
ET(k) = k / 2 * (5 n / k) + ET(k / 2) = 2.5 n + ET(k / 2).
For k / 2, the sizes of ni and mi are doubled. So we have
ET[k] = 2.5 n + 2.5 n + .... + 2.5 log2(k) times.
Then ET[k] = O(nlog(k)).
Finally, average over "k". Note that k is O(n) for random arrays. Therefore, the overall complexity = O(n log(n))
Repeat it for all the k / 2 pairs.

////////////////////

Method 2: For arrays, simple code O(n^2)

void special_sort(int* arr, int length)
{
	// Sweep from back to front
	// If a number is negative and its previous number is positive, swap them
	// continue sweeping until no swaps are made
	bool swapped = false;
	while(swapped)
	{
		swapped = true;
		for (int k = length - 1; k > -1; k--)
		{
			if (k > 0)
			{
				if (arr[k] < 0)
				{
					if (arr[k - 1] > 0)
					{
						int tmp = arr[k - 1];
						arr[k - 1] = arr[k];
						arr[k] = tmp;
						swapped = false;
					}
				}
			}
		}
	}
}

Method 3: Data stored in linked list O(n)

struct LinkedList {
	int value;
	LinkedList* next;
};
LinkedList* special_sort(LinkedList* arr)
{
	// If the first element is not negative, insert a negative number
	// Set pos_last_neg as pointer to the first elemnt of array
	// Sweep through the list (using pointer pos)
	// if the number is negative and pos != pos_last_neg->next, move the element at pos to pos_last_neg;	
	LinkedList* head = new LinkedList;
	head->value = -10000000;
	head->next = arr;
	LinkedList* last_neg = head;
	LinkedList* pos = head->next;
	LinkedList* prev = last_neg;
	while(pos != nullptr)
	{
		if (pos->value < 0)
		{
			if (prev != last_neg)
			{
				// There are some positive elements in between
				LinkedList *p1 = pos;							
				prev->next = pos->next;
				pos->next = last_neg->next;
				last_neg->next = pos;
				last_neg = pos;
				pos = prev->next;
				pos = prev->next;
				continue;
			}
		}
		prev = pos;
		pos = pos->next;
	}
	return head->next;
}

void main()
{
	LinkedList* head = GetLinkedListFromArray({......});
	PrintList(head);
	head = special_sort(head);
	PrintList(head);
}

- Ehsan August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

import java.util.Arrays;

public class NegativeAndPositive {

private static final int[] array = new int[] { 100, -1, 5, 4, -7, 11, 12, 0, -2, -1, -10, 11, -2 };

public static void main(String[] args) {

for (int i = 0, j = array.length - 1; i < j;) {

if (array[i] < 0) {
i++;
continue;
}

if (array[j] > 0) {
j--;
continue;
}

swap(i, j);

}

System.out.println(Arrays.toString(array));

}

private static void swap(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}

}

- encoded August 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

import java.util.Arrays;

public class NegativeAndPositive {

	private static final int[] array = new int[] { 100, -1, 5, 4, -7, 11, 12, 0, -2, -1, -10, 11, -2 };

	public static void main(String[] args) {

		for (int i = 0, j = array.length - 1; i < j;) {

			if (array[i] < 0) {
				i++;
				continue;
			}

			if (array[j] > 0) {
				j--;
				continue;
			}

			swap(i, j);

		}

		System.out.println(Arrays.toString(array));

	}

	private static void swap(int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}

}

- encoded August 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

wrong code.. for input array { -1, 1, 3, -2, 2 }, the result is [-1, -2, 3, 1, 2].
Expected result: [ -1, -2, 1, 3, 2, ]

- Anonymous August 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

How about do the "dividing" part of quicksort with the value 0 as the pivot. All values lesser than 0 will be on left and values greater than 0 will be on right.

Takes O(n) time.

Not sure about whether the relative positions are maintained.

- abyrupus September 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

So you only have to swap the last item in a run of positives or negatives. So you only have to keep an index of the last index of the previous signage run. The following code is O(N) and has O(1) space.

I don't handle the 0 case, because it is unclear what to do with that case.

int lastRunIndex = 0;
            
            while (array[lastRunIndex] < 0 && lastRunIndex < array.Length) { lastRunIndex++; };
            
            for (int i = lastRunIndex; i < array.Length; i++)
            {
                if (array[i] < 0 == array[lastRunIndex] < 0)
                    continue;
                else
                {
                    int temp = array[i];
                    array[i] = array[lastRunIndex];
                    array[lastRunIndex] = temp;
                    lastRunIndex++;
                }
            }

- tipbruley August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Doesn't work for { 11, 1, 3, -2, -5, 2 };
Original: [11, 1, 3, -2, -5, 2]
Output: [-2, -5, 3, 11, 1, 2]

- Jaffa August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

we need two arrays ary1, ary2 ; both size of n, for positive values and negative values

traverse the target array
    if current value is negative
        write it to ary1
    else  write it to ary2
rewrite target array first with ary1 then with ary2

The fact that ary1 and ary2 are built up as we read the target array from bgn to end guarantees that relative positions between values of the same sign would not change

- EthOmus August 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is time: O(n) and space O(n) - easy to implement and reason about

- pmorch August 13, 2018 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

O(n) and O(n)

void sort(int arr[], int n) {
    int dup[n];
    memcpy(dup, arr, sizeof(int) * n);

    int nextNonNeg = 0;
    int i = 0;
    for (i, nextNonNeg; i < n; i++, nextNonNeg++)
        if (arr[i] > 0)
            break;
    for (i; i < n; i++) {
        if (arr[i] < 0) {
            swap(arr, i, nextNonNeg);
            nextNonNeg++;
        }
    }

    int lastNeg = n-1;
    i = n-1;
    for (i, lastNeg; i >= 0; i--, lastNeg--)
        if (dup[i] < 0)
            break;
    for (i; i >= 0; i--) {
        if (dup[i] > 0) {
            swap(dup, i, lastNeg);
            lastNeg--;
        }
    }

    for (int i = 0; i < n; i++)
        if (arr[i] > 0)
            arr[i] = dup[i];
}

int main() {
    int arr[] = { -1, 1, 3, -2, 2, -3, -88, -5, 55, -9 };
    int n = 10;
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    sort(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

- pretonesio September 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice! This is quite possibly the best solution possible, as doing it with O(1) memory is impossible.

- pretobomba September 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Coding with O(n) space and O(n) time is too easy. Let's use A to the original array. Create a new array B.

1 Scan A and copy negative integers into B.
2 Scan A and copy positive integers into B.

- yaojingguo December 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public class SpecialSort {
	
	public static void main(String[] args) {
		int[] data = {-1, 1, 3, -2, 2};
		int length = data.length - 1;
		
		int[] specialSort = specialSort(data, length);
		for(int i=0; i<specialSort.length; i++){
			System.out.printf("%d ", specialSort[i]);
		}
	}

	private static int[] specialSort(int[] data, int length) {
		for(int i=0; i<length-1; i++){
			for(int k=0; k<length-i; k++){
				if(data[k] > 0 && data[k+1] < 0){
					int temp = data[k];
					data[k] = data[k+1];
					data[k+1] = temp; 
				}
			}
		}
		return data;
	}
}

- SuhyunJeon July 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Definitely there are O(n) time complexity and O(1) space complexity algorithms. At least there are two.
The first one uses cycle leader algorithm, check following links
geeksforgeeks.org/an-in-place-algorithm-for-string-transformation/

The second one is
geeksforgeeks.org/inplace-m-x-n-size-matrix-transpose/
For the second, the algorithm in link is O(N^2), but it's very easy to change is to O(N)

- buptyc December 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The n^2 solution would be:

Keep trace of a first met positive number = P. If you find a negative number = N, and P is set, then store P into T, insert value of N into positon P, shift the table right from P to N positon, insert T into P+1.

Can we really do it in O(n) without extra space?

- joe kidd August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

I thought rather bout a single variable.

- joe kidd August 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class NegativePositiveSort
{
    public static void main(String[] args) {
        int[] array = {-1,1,3,-2,2};
        int positiveIndex=-1;
        int negativeIndex=-1;
        // Find 1st positive index
        for(int i=0;i<array.length;i++) {
            if(array[i]>=0) { positiveIndex=i; break;}
        }
        
        // Find 1st negative index after positive index
        for(negativeIndex=positiveIndex+1;negativeIndex<array.length && array[negativeIndex]>=0;negativeIndex++);        
        
        while(positiveIndex>-1 && negativeIndex<array.length) {
            swap(array,positiveIndex,negativeIndex);
            positiveIndex++;
            for(negativeIndex=positiveIndex+1;negativeIndex<array.length && array[negativeIndex]>=0;negativeIndex++);        
        }
        
        for(int i=0;i<array.length;i++) System.out.print(array[i]+",");
    }
    public static void swap(int[] array, int tgt, int src) {
        while(src>tgt) {
            array[src-1] = array[src] ^ array[src-1];
            array[src]   = array[src] ^ array[src-1];
            array[src-1] = array[src] ^ array[src-1];
            src--;
        }
    }
}

- edlai August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It works fine, but This is n^2. consider the case when all +ve are at front and all -ve are at end

- nIx September 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This should work. how to compute the time complexity ?

void sortRelative(int[] m){
		int insertNegative = 0;
		
		for (int index = 0; index < m.length; index++){
			if (m[index] < 0 && m[insertNegative] >= 0){
				int temp = m[index];
				for (int k = index; k > insertNegative; k--){
					m[k] = m[k-1];
				}
				m[insertNegative++] = temp;
			} else {
				if (m[insertNegative] < 0){
					insertNegative++;
				}
			}
		}
	}

- fire August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That's O(n^2)

- uruk hai August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks. But can you please tell me how did you arrive at it ? I always struggle at it.

- fire August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Take this
[1, -1, 2, -2,...,k, -k]

In order to move the first negative to the first position you need to shift 1 positive to the right. Now you get
[-1, 1, 2, -2,...k, -k]

To move the second negative to the second postition you need to shift 2 positives to the right. Finally, to shift the kth negative to the kth position you need to shift k positives to the right.
In total that is 1 + 2 +... + k = k*(k-1)/2 = O(k^2) = O(n^2) (since k = n/2 ) operations.

- uruk hai August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

thanks

- fire August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@fire It's very easy for general cases.
If u have a single level loop in ur program then it is o(n). If there is a loop inside the loop(2 level), then its O(n^2). If inner loop executes only log n times(approx) then it is O(nlogn). If u hav loop inside loop inside loop then its O(n^3) and so on.

- ime.saurabh August 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Author : A.Nasimunni
#include<stdio.h>
main()
{
int n;
printf("\n\tEnter the length of the array : ");
scanf("%d",&n);
int a[n],b[n];
int i=0;
printf("\n\n\tEnter the elements into array \n");
for(i=0;i<n;i++)
{printf("\t\t Enter : ");
scanf("%d",&a[i]);
}
int k=0;
for(i=0;i<n;i++)
{
if(a[i]<0)
{
b[k]=a[i];k=k+1;
}
else
{k=k;}
}


for(i=0;i<n;i++)
{
if(a[i]>0){b[k]=a[i];k++;}else{k=k;}
}

for(i=0;i<k;i++)
{
printf(" %d",b[i]);
}
}

- A.Nasimunni August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Author : A.Nasimunni
#include<stdio.h>
main()
{
int n;
printf("\n\tEnter the length of the array : ");
scanf("%d",&n);
int a[n],b[n];
int i=0;
printf("\n\n\tEnter the elements into array \n");
for(i=0;i<n;i++)
{printf("\t\t Enter : ");
scanf("%d",&a[i]);
}
int k=0;
for(i=0;i<n;i++)
{
if(a[i]<0)
{
b[k]=a[i];k=k+1;
}
else
{k=k;}
}


for(i=0;i<n;i++)
{
if(a[i]>0){b[k]=a[i];k++;}else{k=k;}
}

for(i=0;i<k;i++)
{
printf(" %d",b[i]);
}
}

- A.Nasimunni August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;


class Test {


public static void main(String[] args){

int[] arr = {-1, 1, 3, -2, 2,5,-7,-6};
ArrayList<Integer> list = new ArrayList<Integer>();

for(int i=0;i<arr.length;i++){

if(arr[i]<0){

list.add(arr[i]);
}
}

for(int i=0;i<arr.length;i++){

if(arr[i]>0){

list.add(arr[i]);
}
}

System.out.println(list);
}
}

- Learner August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

space ??? you are using arraylist

- Anonymous August 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] sortInOrder(int[] data){

int pos=0;
int negPos=0;
for (pos=0;pos<data.length;) {

if(data[pos]>=0){
while(negPos<data.length && data[negPos]>=0 ){
negPos++;
}

if(negPos==data.length)
break;
while(negPos>pos){
int temp=data[negPos];
data[negPos]=data[negPos-1];
data[negPos-1] = temp;
negPos--;
}
}
negPos++;
pos++;

}

return data;
}

- avinash jha August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] sortInOrder(int[] data){
		
		int pos=0;
		int negPos=0;
		for (pos=0;pos<data.length;) {
			
			if(data[pos]>=0){
				while(negPos<data.length && data[negPos]>=0  ){
					negPos++;
				}
				
				if(negPos==data.length)
					break;
				while(negPos>pos){
					int temp=data[negPos];
					data[negPos]=data[negPos-1];
					data[negPos-1] = temp;
					negPos--;
				}
			}
				negPos++;
				pos++;
			
		}
		
		return data;
	}

- avinash jha August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] sortInOrder(int[] data){
		
		int pos=0;
		int negPos=0;
		for (pos=0;pos<data.length;) {
			
			if(data[pos]>=0){
				while(negPos<data.length && data[negPos]>=0  ){
					negPos++;
				}
				
				if(negPos==data.length)
					break;
				while(negPos>pos){
					int temp=data[negPos];
					data[negPos]=data[negPos-1];
					data[negPos-1] = temp;
					negPos--;
				}
			}
				negPos++;
				pos++;
			
		}
		
		return data;
	}

- avinash jha August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Works but O(n^2). You are swapping each negative value with all positives before it. So, potentially you will do it for all negatives in the input. So, worst case: O(n^2)

- Anonymous August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If 0 exists, partition around it..Otherwise, insert a 0 and then partition around it. Please confirm if it's possible to add a 0 to the array in O(1) space.

- alex August 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You don't need to physically add the zero. But it won't work. Remember that this is an array and insertion not possible. You can only swap.
Ex: {1 -1 2 -2} turns into {-1 -2 2 1}

- Ehsan August 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The conventional partition algorithm isn't stable, so you'll end up ruining the original order of elements, which is a necessary condition for solving this problem.
You can make partition stable by using an extra O(n) memory, but that also isn't permitted here.

- Epic_coder August 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Code on C#, I think this is O(n)

class Program
    {
        static void Main(string[] args)
        {
            int[] array = new int[] { -1, 1, 3, -2, 2 };

            SortPosNeg(array);
            Console.WriteLine();

            foreach (var i in array)
            {
                Console.Write(i + " ");
            }

            Console.ReadLine();
        }

        static void SortPosNeg(int[] array)
        {
            int totalNegatives = 0;

            foreach (var i in array)
            {
                if (i < 0)
                    totalNegatives++;
            }
	    
            //create arrays for neg and pos
            int[] negArray = new int[totalNegatives];
            int[] posArray = new int[array.Length - totalNegatives];

            int negHelper = 0;
            int posHelper = 0;

            for (int i = 0; i < array.Length; i++)
            {
                if (array[i] < 0)
                {
                    negArray[negHelper] = array[i];
                    negHelper++;
                }

                else
                {
                    posArray[posHelper] = array[i];
                    posHelper++;
                }
            }
           
	   //put all negatives from 0 though totalNegative - 1
            for(int i = 0; i < totalNegatives; i++)
            {
                array[i] = negArray[i];
            }

            for (int i = 0; i < posArray.Length - 1; i++)
            {
                array[totalNegatives + i] = posArray[i];
            }
        }
    }

- Spybreak August 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Last loop should be

for(int i = 0; i < posArray.Length; i++)

- Spybreak August 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Memory O(n), but O(1) was requested.

- Anonymous August 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int main() {
int arr[7] = {-1,-1,-3,-3,-2,-2,-8};
int size = sizeof(arr)/sizeof(*arr);
cout<<size<<endl;
int n=0;
for(int i=0;i<size;i++) {
if(arr[i]<0) {
int temp = arr[i];
int j=i;
while(j>n){
arr[j] = arr[j-1];
j--;}
arr[n++]= temp;}}
for(int i=0;i<size;i++) {
cout<<arr[i]<<" "; }

return 0;}

- kk August 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class array2 {
	public static void printarray(String name,int [] src)
	{
		System.out.println(name);
		for(int i=0;i<src.length;i++)
		{
			System.out.print(src[i]+" ");
		}
	}
	public static void main(String args[])
	{
		int src[]={-1,1,3,-2,2,6,9,7,4,-2,-7,-9,-10};
		printarray("Source",src);
		int i,j=0;
		int a[]=new int[src.length];
		for(i=0;i<src.length;i++)
		{
			if(src[i]<0)
			{
				a[j]=src[i];
				j++;
			}
		}
		for(i=0;i<src.length;i++)
		{
			if(src[i]>=0)
			{
				a[j]=src[i];
				j++;
			}
		}
		System.out.println();
		printarray("Final",a);
	}
}

- Anshul Singh August 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you are taking extra space O(n)

- nIx September 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class array2 {
	public static void printarray(String name,int [] src)
	{
		System.out.println(name);
		for(int i=0;i<src.length;i++)
		{
			System.out.print(src[i]+" ");
		}
	}
	public static void main(String args[])
	{
		int src[]={-1,1,3,-2,2,6,9,7,4,-2,-7,-9,-10};
		printarray("Source",src);
		int i,j=0;
		int a[]=new int[src.length];
		for(i=0;i<src.length;i++)
		{
			if(src[i]<0)
			{
				a[j]=src[i];
				j++;
			}
		}
		for(i=0;i<src.length;i++)
		{
			if(src[i]>=0)
			{
				a[j]=src[i];
				j++;
			}
		}
		System.out.println();
		printarray("Final",a);
	}
}

- Anshul Singh August 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The idea here is when we encounter a positive number in the slot we're examining, we find the next negative number, store it in a temp variable, then shuffle over all the positives. Finally, insert the saved negative number into the current slot.

i.e. if we had: [ -1, <1>, 2, 3, 4, -2, ..]

When we encounter the 1, we search forward til we find the index of the -2, and we store that value. We then copy between our current index and that index:

[ -1, <1>, 1, 2, 3, 4, ....]

Then finally insert the saved number into our current location.

[-1, <-2>, 1, 2, 3, 4, ...]

Then we move onto examining the next index.

<strike>This is O(n) in the worst case, because in [3,2,1,-3,-2,-1], we perform n/2 shuffles, where each shuffle swaps at most n/2 elements. n/2 * n/2 = O(n).</strike>

It's actually O(n^2), thanks for the correction lxduan.

def find_next_negative(i, arr):
    while i < len(arr):
        if arr[i] < 0:
            return i
        i = i + 1
    return None

def sort_relative(arr):
    next_negative_index = None
    for current_index in xrange(0, len(arr)):
        if arr[current_index] < 0:
            pass
        else:
            # find next negative 
            next_negative_index = find_next_negative(current_index+1, arr)
            if next_negative_index:
                # copy it to this location, and bump everything up
                value_to_copy = arr[next_negative_index]
                copy_index = next_negative_index - 1
                while copy_index >= current_index:
                    arr[copy_index+1] = arr[copy_index]
                    copy_index -= 1
                arr[current_index] = value_to_copy 
            else:
                break

    return arr

print sort_relative([3,2,1,-1]) == [-1, 3, 2, 1]
print sort_relative([11, 1, 3, -2, -5, 2]) == [-2, -5, 11, 1, 3, 2]
print sort_relative([3,2,1,-3,-2,-1]) == [-3,-2,-1,3,2,1]

- sarasaurus August 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

shouldn't it be O(n^2)?

- mintaka August 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yep you're right. It's O(n) if you store an extra array with all the indices of negative numbers, but then that's O(n) space. My bad.

- sarasaurus August 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Same as I thought, actually it can be optimized,
the current_index can jump directly to the next_negative_index previously found.
For example:
[ -1, <1>, 2, 3, 4, -2, -3, ..]
suppose after first iteration, we get:
[ -1, -2 , 1, 2, 3, 4, -3 ..]
then we can let current_index jump to <4> (the position of -2 before swap) directly instead of starting from <1> , and then repeat the iteration.

This is O(n) regardless of the swapping part...

- yingzhong.xu September 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1.arrange the first half as negative and second half as negative
2.then call quick sort for first half of the array check for abs(i) pos with abs(j)
3.then call quick sort for the second half of the array

the complexity is O(n) for arranging positive and negative numbers and O(nlogn)+O(nlogn) for sorting... still can we have better solution :)

- ram rs August 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In worst case quick sort takes o(n^2) time if the recurrence formulae is T(n) = T(n-1) + o(n) so the worst case timing is O(n^2) not O(nlogn)

- avikodak August 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class google {

public static void main(String[] args) {
int[] a={-1,1,3,-2,2};
int neg=0;
int pos=0;

for(int i=0;i<a.length;i++){
if(a[i]<0)
neg++;
else
pos++;
}

int countneg=0;
int i=0;
int j=1;
int k=0;
int temp=0;
while(countneg<neg){
if(a[i]<0){
countneg++;
i++;
}
else{
j=i;
k=i;
while(a[k]>0){
k++;
}
temp=a[j];
a[j]=a[k];
for(int z=k;z>j;z--){
a[z]=a[z-1];
}
a[j+1]=temp;
countneg++;
i++;
}
}

for(i=0;i<a.length;i++){
System.out.println(a[i]);
}
}

}

- Anshuman Dev Vyas (anshumandvyas@gmail.com) August 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 6 vote

// anshumandvyas@gmail.com


public class google {

	public static void main(String[] args) {
		int[] a={-1,1,3,-2,2};
		int neg=0;
		int pos=0;
		
		for(int i=0;i<a.length;i++){
			if(a[i]<0)
				neg++;
			else
				pos++;
		}
		
		int countneg=0;
		int i=0;
		int j=1;
		int k=0;
		int temp=0;
		while(countneg<neg){
			if(a[i]<0){
				countneg++;
				i++;
			}
			else{
				j=i;
				k=i;
				while(a[k]>0){
					k++;
				}
				temp=a[j];
				a[j]=a[k];
				for(int z=k;z>j;z--){
					a[z]=a[z-1];
				}
				a[j+1]=temp;
				countneg++;
				i++;
			}
		}

		for(i=0;i<a.length;i++){
			System.out.println(a[i]);
		}	
	}

}

- anshumandvyas August 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 votes

You are doing it in O(n^2) time!

- EOF August 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How is this O(n)? Please explain.

- alex August 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This takes O(n^2) time. You are shifting O(n) positive numbers for each of O(n) negative numbers.

- anotherguy September 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>

void swapT(int* a,int* b, int *c){
int temp=*c;
*c=*b;
*b=*a;
*a=temp;
}

#define N 5

int main(){
int i, pos, mid, neg = 0;
int a[] = {-1,1,3,-2,2};
for (i = 0; i < N; i++) printf (" %d ", a[i]);
printf ("\n");
int totNeg = 0;
for (i = 0; i < N; i++){
if (a[i] < 0) totNeg++;
}
mid = totNeg;
pos = totNeg;
while (totNeg > 0){
if (a[neg] < 0){
neg++;
totNeg--;
}
else {
while (a[pos] >= 0) pos++;
swapT(&a[neg], &a[mid], &a[pos]);
neg++;
pos++;
mid++;
totNeg--;
}
}

for (i = 0; i < N; i++) printf (" %d ", a[i]);
printf ("\n");

return 0;
}

- Itzik August 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>

void swap(int *, int *);
main()
{
	int array[6] = {
	1,2,3,4,-2,-3
	};
	int a = 0, b = 5;
	while (a <= b) {
		while (array[a] < 0)
			a++;
		while (array[b] > 0)
			b--;
		if (b -a > 1) {
			swap(&array[a], &array[b]);
			a++;
			b--;
		}
	}
	int i = 0;
	for (; i < 6; i++)
		printf("%d ", array[i]);
	printf("\n");
	return 0; 
}

void swap(int *a, int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
};

- iostreamin August 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My apology, previous code is not work for some special test data, so i edit and add the second one.

#include <stdio.h>

void swap(int *, int *);
main()
{
	int array[6] = {
	-1,1,3,-2,2,4
	};
	int a = 0, b = 5;
	while (b -a > 1) {
		while (array[a] < 0)
			a++;
		while (array[b] > 0)
			b--;
		swap(&array[a], &array[b]);
		a++;
		b--;
	}
	int i = 0;
	for (; i < 6; i++)
		printf("%d ", array[i]);
	printf("\n");
	return 0; 
}

void swap(int *a, int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
};

- iostreamin August 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void rearrange(vector <int> &nums)
{
    vector<int> temp;
    int start_pos = 0;
    for(int i=0;i<nums.size();++i)
    {
        if(nums[i] <0 )
             nums[start_pos++] = nums[i];
        else
            temp.push_back(nums[i]);
    }
    for(int i=0;i<temp.size();++i)
        nums[start_pos++] = temp[i];

}
It's O(N) time and (N) memory , i can't find solution with less memory.

- spik August 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void sortIntegers(int[] intarray)
{
for(int h=0;h<intarray.length;h++)
System.out.print(intarray[h]+ " ");

int lastnegative = 0;
for(int i=0; i< intarray.length;i++)
{
if(intarray[i]<0)
{
swap(intarray,lastnegative,i);
lastnegative = lastnegative+1;
}
}
System.out.println();
for(int m=0;m<intarray.length;m++)
System.out.print(intarray[m]+ " ");

}
void swap(int[] intarray, int lnegative, int j)
{
int temp = intarray[j];
for(int k = j-1;k>=lnegative;k--)
{
intarray[k+1] = intarray[k];
}
intarray[lnegative] = temp;
}

- anon August 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

we can also use queue data structure like this in Java
public class Sort {

public static void sortArray(int[] a)
{
int N = a.length;
Queue<Integer> q1 = new Queue<Integer>();
Queue<Integer> q2 = new Queue<Integer>();

for (int i = 0; i<N; i++)
{
if(a[i] < 0 ) q1.enqueue(a[i]);
else q2.enqueue(a[i]);
}
int i = 0;
while (!q1.isEmpty())
a[i++] = q1.dequeue();
while(!q2.isEmpty())
a[i++] = q2.dequeue();

}

public static void main(String[] args)
{
int[] a = {-1,1,3,-2,2};
sortArray(a);
for (int i =0; i<a.length;i++)
System.out.println(a[i]);
}


}

- neuron August 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

NOT possible in o(n)time complexity and o(1) space complexity

- KK August 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, if o(n) means small Oh of n, which completely different from O(n), BigOh of n.

If you did mean BigOh, whatever proof you have, is likely wrong.

There was a link to a paper which just does that, somewhere in the comments on this question.

- Anonymous August 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If this wasn't an array it would be doable!

if you had a linked list you could easily do this in one pass!

Just link the negative list together then link the last item with the first positive.

LinkedListNode current = list.root;
            LinkedListNode prevPos = null;
            LinkedListNode firstPos = null;
            LinkedListNode prevNeg = null;


            while (current != null && current.next != null)
            {
                if (current.val >= 0)
                {
                    if (prevPos == null)
                    {
                        firstPos = current;
                    }
                    else
                    {
                        prevPos.next = current;
                    }
                    prevPos = current;
                }
                else
                {

                    if (prevNeg == null)
                    {
                        list.root = current;
                    }
                    else
                    {
                        prevNeg.next = current;
                    }
                    prevNeg = current;
                }

                current = current.next;
            }

            if (prevNeg == null)
                list.root = firstPos;
            else
                prevNeg.next = firstPos;

            if (prevPos != null)
                prevPos.next = null;

Otherwise, I do not believe this problem is solvable.

- tipbruley August 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

[ o(1) space, by time complexity is not o(n) :( ]

private void start( int[] a ) {
        int n = -1, p = -1; // set positive and negative count

        for ( int i = 0; i < a.length; i++ ) {
            if ( a[i] < 0 ) {
                n = i;
                if ( n > p && p >= 0 ) {
                    move( a, p, n );

                    p++; // increment positive index which will be used for next negative value set.
                }
            } else if ( p <= 0 ) { // get first positive number index
                p = i;
            }
        }
        System.out.println( Arrays.toString( a ) );
    }

    /**
     * replace first positive number with negative number. and then move remaining positive numbers by 1 towards right.
     * For { -1, 1, 3, -2, 2 }, s=1, and e=3, replace a[s] with a[e], and set a[s+1] with a[s], increment s by 1. do it
     * until u reach end 'e'
     * 
     * @param s start index
     * @param e end index
     */
    private static void move( int[] a, int s, int e ) {
        int temp = a[s];
        a[s] = a[e];
        for ( int i = s + 1; i <= e; i++ ) {
            int t2 = a[i];
            a[i] = temp;
            temp = t2;
        }
    }

- juststarted August 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
- ime.saurabh August 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In O(n) time and O(1) space.

- ime.saurabh August 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
void swap(int*,int*);
void insert(int*, int*);
int main()
{
	int arr[5] = {-1,1,3,-2,-4};
	int negcount = 0, i, p;
	
	/*Counting negetive numbers*/
	for(i=0;i<5;i++)
		if(arr[i]<0)
			negcount++;
	/*p points to the next location to insert positive number */
	p = neg;
	
	/*Main algo part*/		
	for(i=0;i<neg;i++)
	{
		if(arr[i] >0)
		{
			printf("swapping\n");
			swap(&arr[i], &arr[p]);
			p++;
			if(arr[i] <= 0)
				insert(&arr[i], &arr[neg-1]);
			i--;	
		}		
	}
	
	/*Print The Result*/
	for(i=0;i<5;i++)
		printf("%d\t", arr[i]);
	printf("\n");
	
}

- ime.saurabh August 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It uses O(1) space but time used is O(m^2) where m is number of negetive integers there.

- ime.saurabh August 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is like merge sort with a twist. The best solution I can think of for an O(1) space complexity is O(nlogn) time complexity. The trick is to think in terms of merge sort and perform matrix rotation through reverse

public static int order(int[] x, int startidx, int endidx){
        if(startidx==endidx) return x[startidx] >= 0 ? 1 : 0;
        else{
            int p1 = order(x, startidx, (startidx+endidx)/2);
            int p2 = order(x, (startidx+endidx)/2 + 1, endidx);
            //order (only if the first half has positive items And second half has negative items)
            if(p1 != 0 && p2!= (endidx - (startidx + endidx)/2)){
                int fst_pidx_1;
                fst_pidx_1 = (startidx+endidx)/2 - p1 +1;
                int lst_nidx_2 = endidx - p2;
                //We basically want to perform a rotation operation for part of the array
                //This can be done in O(n) if we use the reverse function
                int shftVal =  endidx - (startidx+endidx)/2 - p2;
                reverse(x, fst_pidx_1, lst_nidx_2);
                reverse(x, fst_pidx_1, fst_pidx_1 + shftVal - 1);
                reverse(x, fst_pidx_1 + shftVal, lst_nidx_2);
            }
            //return p1 + p2
            return (p1 + p2);
        }
    }
    //This function reverses part of the array
    public static void reverse(int[] x, int begin, int end)
    {
        int lst = end;
        for(int i = begin; i <= (begin+end)/2; i++){
            int tmp =x[i];
            x[i] = x[lst];
            x[lst] = tmp;
            lst--;
        }
        
    }

T(n) = 2T(n/2)+o(n). o(n) being the rotation function. Then time complexity is O(nlogn). I dont really think any type of sorting can occur in O(n) but if someone come up with a solution, thatd be good.

- karimyehia10@gmail.com August 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Forgot to comment this on the code. The order function return the number of positive items in the array. So p1 is the positive items in the first half or the array. p2 is the positive items in the second half of the array.

- karimyehia10@gmail.com August 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def swap(list,idx1,idx2)
    t = list[idx1]
        list[idx1] = list[idx2]
        list[idx2] = t
        list
end
 
def separate(list)
        idx = list.length
        idx -= 1
        while(idx > 0) do
                iidx = idx
                if list[idx] < 0
                        pidx = idx - 1
                        while(pidx >= 0) do
                                if list[pidx] > 0
                                        list = swap(list,idx,pidx)
                                        if idx < iidx
                                                iidx += 1
                                        end
                                        break
                                else
                                        idx = pidx
                                end
                                pidx -= 1
                        end
                end
                idx = iidx - 1
        end
        list
end
 
list = [1,2,-3,4,6,-9,10]
puts separate(list).join(',')

- LazyCoder August 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

ideone.com/jYtdmD

- LazyCoder August 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class GoogleSort {
public static void main(String args[])  {
	int[] in = {-1,2,3,-2,4,-5}; //input array
	int temp;//space1
	for (int i = 0; i < in.length; ) {
		if(in[i]<0)	i++;
		else{
			temp=i;
			while(temp < in.length && in[temp]>0 )
				temp++;
			if(temp >= in.length)
				break;
			while(i < temp ){
				//XOR swap
				in[temp] ^= in[temp -1];
				in[temp-1] ^= in[temp];
				in[temp] ^= in[temp -1];
				temp --;
			}
			i = temp;			
		}
	}
	for (int i = 0; i < in.length; i++) {
		System.out.println(in[i]);
	}
  
}

}

- harsha August 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I believe its in O(n) time and definitely O(1) space, Can some analyze for a worst case to prove otherwise.

- harsha August 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I haven't figured out the O(N) solution given an array, but it'd be easy to do with a linked list. Then you could just keep track of pointers for the end of the positive and negative lists, and then connect them in the end, with O(1) space (all you'd need is three pointers, one for the current position, one for the start of the positive list and one for the start of the negative).

- Anonymous August 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is the best I got keeping the space on O(1) and O(n) without zeros
Wasn't sure by the description if the array has zeros in it so added code to handle but not without extra time

<script>
var arr = [100, -1, 5, 4, -7, 11, 12, 0, -2, -1, -10, 11, -2];
function sortNegative(arr) {
	var negPos=-1;
	var hasZero = false;
	i=0;
	while (i<arr.length) {
		if (arr[i] < 0) {
			tmp = arr[i];
			negPos++;
			//move all positives forward
			for (j=i; j>negPos; j--) {
				arr[j] = arr[j-1];
			}
			arr[negPos] = tmp;
		}
		if (arr[i] == 0)
			hasZero = true;
		i++;
	}
	
	if (hasZero) {
		i=negPos;
		while (i<arr.length) {
			if (arr[i] == 0) {
				tmp = arr[i];
				negPos++;
				//move all positives forward
				for (j=i; j>negPos; j--) {
					arr[j] = arr[j-1];
				}
				arr[negPos] = tmp;
			}
			i++;
		}
	}
	return arr;
}
document.write(arr + '<br>');
document.write(sortNegative(arr));
</script>

- lrafagnin August 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function for the solution is given below,it solves the problem in O(n) time:

int arrange_numbers(int *ARRAY,int no_of_elements)
{
int NEW_ARRAY[no_of_elements];
int i,j=0;
for(i=0;i<no_of_elements;i++)
{
if(*ARRAY <0 )
{
NEW_ARRAY[j] = *ARRAY;
j++;
}
ARRAY++;
}
// loop 1 ends,arrangin all negative numbers correctly;
}

for(i=0;i<number_of_elements;i++)
{
if(*ARRAY > 0)
{
NEWARRAY[j]=*A;
j++;
}
ARRAY++;
}
//loop 2 ends arranging all positive numbers correctly
return NEW_ARRAY;
}

- ayushsethi22031992 August 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
	Question ID: 5201559730257920
	
	Give you 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 perfect.
*/

public class sol5201559730257920{

	static int length;
	static int[] a;
	static int start;
	static int end;
	static int total_n;
	
	public static void sort(){
		while(start < total_n){
			if(a[start] < 0)	
				start ++;
			else{
				a[end] = a[start] + (a[start] = a[end]) - a[end]; // swap;
				end ++;
			}
		}
	}
	
	public static void display(){
		for(int i = 0; i < length; i ++){
			System.out.print(a[i] + " ");
		}
	}
	
	public static void main(String[] args){
		length = args.length;
		a = new int[length];
		for(int i = 0; i < length; i ++){
			a[i] = Integer.parseInt(args[i]);
			if(a[i] < 0) // count total negative numbers
				total_n ++;
		}
		end = total_n; // index where positive num starts
		sort();
		display();
	}
}

- Yuvraj Singh Babrah August 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice, but doesn't maintain order. (Swapping makes it unstable.)
Ex:
Input: 1 -2 3 -3 2 -1 1 -2 3 -3 2 -1
Output: -2 -2 -3 -3 -1 -1 1 1 3 3 2 2
Expected: -2 -3 -1 -2 -3 -1 1 3 2 1 3 2

- Anonymous September 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void sort(int[] array){
		
		int cout_pos = 0; int count_neg = 0;
		int sum_pos = 0; int sum_neg = 0; 
		int neg_co = 1; int pos_co = 1;
		
		for(int i=0; i!=array.length; ++i){
			if(array[i] < 0){
				neg_co *= 10;
				count_neg++;
				sum_neg += -1 * array[i] * neg_co;
				
			}
			else{
				pos_co *= 10;
				cout_pos++;
				sum_pos += array[i] * pos_co;
				
			}
		}
		
		//put them back in the array
		for(int i = count_neg -1; i!=0; --i){
			array[i] = -1*(sum_neg / neg_co);
			sum_neg -= array[i] * neg_co;
			neg_co /= 10;
			
		}
		
		for(int i = array.length-1; i!=count_neg-1; --i){
			array[i] = sum_pos / pos_co;
			sum_pos -= array[i] * pos_co;
			pos_co /= 10;
			
		}
	}

- Anonymous August 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void sort(int[] array){

int cout_pos = 0; int count_neg = 0;
int sum_pos = 0; int sum_neg = 0;
int neg_co = 1; int pos_co = 1;

for(int i=0; i!=array.length; ++i){
if(array[i] < 0){
neg_co *= 10;
count_neg++;
sum_neg += -1 * array[i] * neg_co;

}
else{
pos_co *= 10;
cout_pos++;
sum_pos += array[i] * pos_co;

}
}

//put them back in the array
for(int i = count_neg -1; i!=0; --i){
array[i] = -1*(sum_neg / neg_co);
sum_neg -= array[i] * neg_co;
neg_co /= 10;

}

for(int i = array.length-1; i!=count_neg-1; --i){
array[i] = sum_pos / pos_co;
sum_pos -= array[i] * pos_co;
pos_co /= 10;

}
}

- Nima August 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void sort(int[] array){
		
		int cout_pos = 0; int count_neg = 0;
		int sum_pos = 0; int sum_neg = 0; 
		int neg_co = 1; int pos_co = 1;
		
		for(int i=0; i!=array.length; ++i){
			if(array[i] < 0){
				neg_co *= 10;
				count_neg++;
				sum_neg += -1 * array[i] * neg_co;
				
			}
			else{
				pos_co *= 10;
				cout_pos++;
				sum_pos += array[i] * pos_co;
				
			}
		}
		
		//put them back in the array
		for(int i = count_neg -1; i!=0; --i){
			array[i] = -1*(sum_neg / neg_co);
			sum_neg -= array[i] * neg_co;
			neg_co /= 10;
			
		}
		
		for(int i = array.length-1; i!=count_neg-1; --i){
			array[i] = sum_pos / pos_co;
			sum_pos -= array[i] * pos_co;
			pos_co /= 10;
			
		}
	}

- Nima August 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args){
		int []A={1,-2,-3,4,5,6,7,8,-9,-10,11,12,13,-14,-15,-16,-17,-18, 19};
		int l=A.length;
		int j=l-1;
		int i=0;
		int [] b=sortArr(A, i, j);
		for(i=0; i<l; i++){
			System.out.print(b[i]+" ");
		}
	}
	
	
	static int [] sortArr(int []A, int i, int j){
		while(A[j]>=0 & j>-1){
			j--;
		}
		int k=j;
		while(A[k]<0 && k>-1){
			k--;
		}
		for(int p=k; p<j; p++){
			int temp=A[p];
			A[p]=A[p+1];
			A[p+1]=temp;
		}
		if(k==0){
			return A;
		}
		j--;
		k=j;
		
		return sortArr(A, i, j);
	}
}

- shashi_kr August 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Multiply all negative numbers by 10 and odd numbers by 10 and add 1
2. sort the array using stable sorting algorithm considering only the last digit of the number
-10 -20 11 31 21
3. divide all elements by 10
-1 -2 1 3 2
This is O(N) and O(1)
OR

2. O(NlogN) soln - sort using any standard algo considering only the last digit

- Abhay August 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def rearrange(src, tgt):
    src_pos = {}
    for i, s in enumerate(src):   # O(n)
        src_pos[s] = i

    zero = src.index(0)     # O(n)

    for i, t in enumerate(tgt):  # n times O(1)
        if t == 0 or t == src[i]:
            continue
        swap(src, zero, i)
        swap(src, src_pos[t], i)
        zero = src_pos[t]
    print src

- Anonymous August 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is linear time but also O(n) memory (for the hash map src_pos)

- Anonymous August 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I know time complexity is O(n^2).

#include<iostream>
using namespace std;
int main()
{
	int a[7]={2,-3,3,5,-6,2,-9},j,n=0;
	for (int i = 0; i < 7; ++i)
	{
		if (a[i]<0)
		{	int temp=a[i];
			for (j=i;j>n;j--)
			 	a[j]=a[j-1];
			a[n++]=temp;
		}
	}
	
	for (int i = 0; i < 7; ++i)
	{
		cout<<a[i]<<endl;
	}
	system("pause");
}

- Durgesh Suthar August 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Two Threaded solution:
One thread starts from n direction left to right.
Another thread from 1 right to left.
LR thread stops if it encounters -ve and waits for RL to encounter positive. If so swap.
Iteration breaks if two threads cross path.
o(n), o(1).

- natdev September 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void specialSort(int[] arr){
		if (arr == null) throw new NullPointerException();
		if(arr.length == 1) return;
		
		int temp = arr[0];
		int pos, neg;
		int n = arr.length;
		pos = neg = 0;
		while(neg < n){
			for(int k = neg;pos < n && neg < n;k++){
				if(arr[neg] >= 0){
					//check if the last element in the array is
					// a positive number. If so we are done
					if (neg < n-1){
						// move the positive numbers to the right
						// if you haven't reached the end of
						// the array
						int exch = arr[neg];
						arr[neg] = temp;
						temp = exch;
					}
						neg++;
				}
				if(arr[pos] < 0) pos++;
				if(neg >= n) break; //no more negative numbers
				if(arr[pos] >= 0 && arr[neg] < 0) break;
			}	
	        if(neg < n){//if neg > n then the last element of
	        	// the array is a positive number and we are done
			    if(neg > pos ){
				    if(arr[neg] < 0){
					    arr[pos] = arr[neg];
				        arr[neg] = temp;
				        pos = neg;
				    }
			    }
			    else neg = pos; // make sure we continue at 
			    // the higher index
			    neg++;
			    temp = arr[pos];
	        }
		}
		
	}

- devonyates11 September 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I believe I have achieved O(n) time and O(1) extra space complexity:-

Let us maintain such an invariant at all times:


The first n numbers of the array are negative.
The next p numbers of the array are positive.
So let the array look like this:

-ve -ve -ve ... -ve; +ve +ve +ve ... +ve; -ve ....
n times p times remaining


Now let us find n1 and p1 such that

-ve -ve -ve ... -ve; +ve +ve +ve ... +ve; -ve -ve -ve ... -ve; +ve +ve +ve .... +ve; -ve ....
n times p times n1 times p1 times remaining

Now let us try to 'consume' the n1 and p1 elements in the n and p elements. We can do this by swapping the 2nd and 3rd blocks(p and n1 elements). If we can do this in O(p+n1) time, then increment n to be n+n1 and p to be p+p1 and keep doing this, we should be able to do this for the whole array in O(n) time.

So the challenge is this:

x1 x2 x3 ... xp; y1 y2 y3 ... yq
has to be rearranged to form
y1 y2 y3 ... yq; x1 x2 x3 ... xp
in O(p+q) time.

If p==q, then it's easy. Just keep on swapping x1, y1; x2, y2 and so on.
If p!=q, suppose p>q without loss of generality. Then swap the elements y1..yq and x1..xq to get

y1 y2 y3 ... yq xq+1 xq+2 ... xp x1 x2 x3 ... xq

and repeat the procedure for the subarray xq+1 xq+2 ... xp; x1 x2 x3 ... xq

This way, it is possible to swap an unequal number of elements in place in O(n) time and O(1) extra space.

Code:

#include<stdio.h>
#include<stdlib.h>

void swap(int* arr, int pos1, int pos2) {
   arr[pos1] ^= arr[pos2];
   arr[pos2] ^= arr[pos1];
   arr[pos1] ^= arr[pos2];
}
void swap_in_place(int* arr, int ff, int fl, int sf, int sl) {
   if(ff==fl+1 || sf==sl+1) {
      return;
   }
   if(fl-ff>sl-sf) {
      int lesser = sl-sf+1;
      int i;
      for(i=0; i<lesser; i++) {
         swap(arr, ff+i, sf+i);
      }
      swap_in_place(arr, ff+lesser, fl, sf, sl);
   }
   else{
      int lesser = fl-ff+1;
      int i;
      for(i=0; i<lesser; i++) {
         swap(arr, fl-i, sl-i);
      }
      swap_in_place(arr, ff, fl, sf, sl-lesser);
   }
}

void print_array(int* arr, int size) {
   int i;
   for(i=0; i<size; i++) {
      printf("%d ", arr[i]);
   }
   printf("\n");
}

void swap_pos_neg(int* arr, int size) {
   int neg=0;
   int pos=0;
   while(neg<size && arr[neg]<0) {
      neg++;
   }
   pos=neg;
   while(pos<size && arr[pos]>0) {
      pos++;
   }
   if(pos>=size) return;
   while(pos<size) {
      int new_neg=pos;
      while(new_neg<size && arr[new_neg]<0) {
         new_neg++;
      }
      int new_pos = new_neg;
      while(new_pos<size && arr[new_pos]>0) {
         new_pos++;
      }
      swap_in_place(arr, neg, pos-1, pos, new_neg-1);
      neg += new_neg-pos;
      pos = new_pos;
   }
}
void main() {
   int size = 5;
   int arr[] = {-1, 1, 3, -2, 2};
   print_array(arr, size);
   swap_pos_neg(arr, size);
   print_array(arr, size);
}

This code takes .325 seconds for 10,000 elements.

- anotherguy September 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Try proving it. It is likely wrong. (And don't ask for a counter-example).

- Anonymous September 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>

int main()
{
	char arr[]=
{0,-1,1,-5,3,-2,6};
	int i,j=0;
	int k=0;

	int size=sizeof(arr)/sizeof(arr[0]);

	printf("before\n");
	for(i=0;i<size;i++)
		printf("%3d",arr[i]);
	printf("\n");

	i=0;
	int cnt=0;
	int loop=0;
	

	while(cnt<=size-j)
	{
		loop++;
		cnt++;
		if(arr[i]>=0&&!k)
		{
			j=i;
			k=1;
		}
		if((arr[i]>=0)&&(arr[i+1]<0))
		{
			int t=arr[i];
			arr[i]=arr[i+1];
			arr[i+1]=t;
			if(i==j)
				j=i+1;
			cnt=0;
		}
		if(i==size-2)
		{
			i=0;
			k=0;
		}
		else
			i++;
	}
	
	printf("after\n");
	for(i=0;i<size;i++)
		printf("%3d",arr[i]);
	printf("\n");
	printf("loop=%d\n",loop);
	
	
	
	return 0;
}

- Surajit Sinha September 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void reArrageArray(int []data) {
int loopCount = 0;
int nPos = -1;
for (int i = 0; i < data.length; i++) {
int nValue = data[i];
if (nValue < 0) { //2
if (nPos != i-1) {
for (int j = i ; j > 0; j--) {
if (data[j-1] >= 0) {
data[j] = data[j-1];
data[j-1] = nValue;
} else {
nPos = j;
}
loopCount++;
}
} else {
nPos = i;
loopCount++;
}

} else {
loopCount++;
}
}
System.out.println("Total loop count : " + loopCount);
for (int i = 0; i < data.length; i++) {
System.out.println(data[i]);
}

}

- @basker September 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Test{

   public static void main(String[] args){
      int[] a = {-1, 1, 3, -2, 2, -6, -7, 8,9,12};
   
      int i = 0, j = a.length - 1, tmp;
    
      while (i < j){
         if (a[i] < 0){
            i++;
         }
         if (a[j] > 0){
            j--;
         }
         if(i < j){
            tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
            i++;
            j--;        
         }
      }
      
      for(int k = 0; k < a.length; k++){
      System.out.print(a[k] + " | ");
      }

   }


}

- Anonymous September 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It seems not that difficult, someone did mention 'mergesort' but no one mentioned how to make it O(N): So, how about using a special version of mergesort recursively, where "merge" involves inserting +ve and -ve parts of the 'right' sub-list into the 'left' sub-list, this "merge" will take O(1), leading to O(N) for the whole mergesort?

- Sakiv September 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is not possible in O(1) space, O(n) time is fine. I guess interviewer wanted to see if interviewee is confident enough to say this.

- nIx September 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

He would be confident and wrong. I guess that puts him squarely in the arrogant bucket.

- Anonymous September 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

for O(1) space, can we not allocate max integer space and then fill it sequentially with occurred positive integers in given array, and then fill them back in original array from end of the array, here we will ensure that all -ve integers are pulled ahead. (filling up in original array should be easy). Help expand this logic if makes sense.

- nIx September 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<vector> A()
algorithm group(A)
{
n<-- length(A)
k=n+1
for i<-- 0 to n do
{
if(A[i]>0)
{
A[k]=A[i]
A.erase(A.begin()+i)
k=k+1
}
}
}

- gopinath September 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;

void swapp(int* a,int* b)
{
int t= *a;
*a=*b;
*b=t;
}

int main()
{
int n;
cin>>n;
int* a=new int[n];
for(int i=0;i<n;i++)
cin>>a[i];

int countneg=0,countpos=0;
for(int i=0;i<n;i++)
{
if(a[i]<0)countneg++;
else countpos++;
}
cout<<countneg<<" "<<countpos<<endl;
int j=0,tempcount=countneg;
for(int i=0;i<n;i++)
{
if(a[i]>0 && i<countneg)
{
swapp(&a[i],&a[tempcount]);
tempcount++;
}
else if(a[i]<=0)
{
swapp(&a[i],&a[j]);
j++;if(i>0) i--;
}
else continue;

}
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
delete []a;
}

- Nitin September 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Do an in-place partition (i.e. from the quick sort algorithm) on the pivot value 0. However, the partition algorithm is not stable, but we can fix that without too much extra work and constant overhead.

Example:

Given:  -1 1 3 -2 2
Correct Answer: -1 -2 1 3 2

Let's run through the quicksort partition algorithm:
-1 1 3 -2 2
^--- -1 <= 0, keep it there, adding it to the left paritition.
     increment the pointer.

-1 1 3 -2 2
   ^--- 1 > 0. This is the first value inserted to the right partition.
   							Call this position first_right_val.

-1 1 3 -2 2
   ^ ^ 3 > 0. do nothing when first_right_val is the first element of the right
              partition.

-1 -2 3 1 2
    ^   ^  swap to grow the left partition.
    			 note that this operation loses the "stable" property.
    			 however, we can regain that. for now, lets track that the value
    			 was swapped, i.e. update first_right_val to point to its new
    			 position.

-1 -2 2 1 3
      ^   ^--- 2 > 0. If first_right_val is not the first element of the 
      								right parition, we should do a swap. first_right_val
      								remains pointing to the "1"


Parition is finished. But the partition is not stable. However we know where
the first encountered element of the right partition _is_, i.e. its the "1".
And by adding extra swapping logic when examining the elements greater than
the pivot we have essentially kept a "rotated" copy of the right partition.

To recover a stable partition, simply do a rotate on the right paritition,
to get:
-1 -2 1 3 2

By the way, a stable_partition is already implemented in STL if using C++ that
does exactly what this question is asking.

bool IsLessThanZero(int val) { return val < 0; }
std::stable_partition(data_array.begin(), data_array.end(), IsLessThanZero);

If you have to implement the stable_partition manutally, you can always use the
STL rotate for the last step!

// After partitioning as above, keeping track of the first_right_val.
	std::rotate(data_array.begin() + right_partition_start_index,
						  data_array.begin() + first_right_val, // the new first element
						  data_array.end());

- Anonymous September 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

LOL. "Easy"? Have you even tried doing it yourself, rather than fanning yourself while waving your hands?

- Anonymous September 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

And yeah, -100.

- Anonymous September 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Do an in-place partition (i.e. from the quick sort algorithm) on the pivot value 0. However, the partition algorithm is not stable, but we can fix that without too much extra work and constant overhead.

Example:

Given:  -1 1 3 -2 2
Correct Answer: -1 -2 1 3 2

Let's run through the quicksort partition algorithm:
-1 1 3 -2 2
^--- -1 <= 0, keep it there, adding it to the left paritition.
     increment the pointer.

-1 1 3 -2 2
   ^--- 1 > 0. This is the first value inserted to the right partition.
   							Call this position first_right_val.

-1 1 3 -2 2
   ^ ^ 3 > 0. do nothing when first_right_val is the first element of the right
              partition.

-1 -2 3 1 2
    ^   ^  swap to grow the left partition.
    			 note that this operation loses the "stable" property.
    			 however, we can regain that. for now, lets track that the value
    			 was swapped, i.e. update first_right_val to point to its new
    			 position.

-1 -2 2 1 3
      ^   ^--- 2 > 0. If first_right_val is not the first element of the 
      								right parition, we should do a swap. first_right_val
      								remains pointing to the "1"


Parition is finished. But the partition is not stable. However we know where
the first encountered element of the right partition _is_, i.e. its the "1".
And by adding extra swapping logic when examining the elements greater than
the pivot we have essentially kept a "rotated" copy of the right partition.

To recover a stable partition, simply do a rotate on the right paritition,
to get:
-1 -2 1 3 2

By the way, a stable_partition is already implemented in STL if using C++ that
does exactly what this question is asking.

bool IsLessThanZero(int val) { return val < 0; }
std::stable_partition(data_array.begin(), data_array.end(), IsLessThanZero);

If you have to implement the stable_partition manutally, you can always use the
STL rotate for the last step!

// After partitioning as above, keeping track of the first_right_val.
	std::rotate(data_array.begin() + right_partition_start_index,
						  data_array.begin() + first_right_val, // the new first element
						  data_array.end());

- kastur September 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The quicksort partition swaps at most n times, and compares each element once with the pivot giving a running time O(n).

The partition is done in-place, so only O(1) memory overhead.

- Anonymous September 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

With a singly linked list (instead of an array) you can obtain O(n) time complexity and O(1) space complexity:

public void sort() {
		
		Node crtPos = list.head;
		Node crtNeg = list.head;
		
		while ((crtPos != null) && (crtPos.x < 0)) {
			crtPos = crtPos.next;
		}
		while ((crtNeg != null) && (crtNeg.x >= 0)) {
			crtNeg = crtNeg.next;
		}
		
		if ((crtNeg == null) || (crtPos == null)) {
			return;
		}
		
		// we've found the head of the list
		list.head = crtNeg;
		// keep a reference to the first positive item
		Node firstPos = crtPos;
		Node lastNeg = null;
		
		Node latestNeg = crtNeg;
		Node latestPos = crtPos;

		while ((latestNeg != null) && (latestPos != null)) {
			while ((crtNeg != null) && (crtNeg.x < 0)) {
				latestNeg = crtNeg;
				crtNeg = crtNeg.next;
			}
			lastNeg = latestNeg;
			
			while ((crtPos.x >= 0) && (crtPos != null)) {
				latestPos = crtPos;
				crtPos = crtPos.next;
			}
			while ((crtPos != null) && (crtPos.x < 0)) {
				crtPos = crtPos.next;
			}
			latestPos.next = crtPos;
			latestPos = crtPos;
			
			while ((crtNeg != null) && (crtNeg.x >= 0)) {
				crtNeg = crtNeg.next;
			}
			latestNeg.next = crtNeg;
			latestNeg = crtNeg;
		}

		lastNeg.next = firstPos;

	}

- Sorin September 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

O(n) O(1)!

void sort(int arr[], int n) {
    int nextNonNeg = 0;
    int i = 0;
    for (i, nextNonNeg; i < n; i++, nextNonNeg++)
        if (arr[i] > 0)
            break;

    for (i; i < n; i++) {
        if (arr[i] < 0) {
            int t = arr[i];
            memmove(&(arr[nextNonNeg + 1]), 
                    &(arr[nextNonNeg]), 
                    sizeof(int) * (i - nextNonNeg));
            // swap(arr, i, nextNonNeg);
            arr[nextNonNeg] = t;
            nextNonNeg++;
        }
    }
}

- pretonesio September 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice! Best yet!

- John Jeff September 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

Just Kidding! That's O(n^2) :P

- pretonesio September 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

right, memmove is O(n) while being in T(n) cycle, so overall is O(n^2).

- Iuri Covalisin November 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) time O(1) space solution:

def sort(A):
  while ( j < len(A) ):
    while ( i < len(A) and A[i] < 0 ):
      i += 1
    while ( j < len(A) and A[j] >= 0 ):
      j += 1
    if ( i < j and i < len(A) and j < len(A)):
      temp = A[i]
      A[i] = A[j]
      A[j] = temp
    j+=1
  return A

- Anonymous September 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

forgot to copy the initialization of i and j

i=0
  j=0

- taurus September 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't think this solution will maintain relative order. Can you give an example?

- Anonymous September 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

complexity is little more than (n)...

public class Googlearray {

    public static void main(String[] args) {
       
        int a[]={-1,1,-3,3,-2,-4,5,-3,2};
        int l=a.length;
        int i = 0,j=0;          //j for positive... i for negative numbers
        int count=0;  
        int temp;
        
        
        while(i<l && j<l){
            if(a[j]<0)
                j++;
            if(a[i]<0 && count>0){      
                temp = a[i];            //swap -ive no with previous one until it
                a[i]=a[i-1];            //is not replaced by positive.
                a[i-1]=temp;
                count--;
                i--;
            }
            if(a[i]<0 && count==0){                
                i++;
            }         
            if(a[i]>0)
            {
                count++;                //keep counts for swaping the -ne no.
                i++;
            }                     
    }
        for(i=0;i<=l-1;i++){
            System.out.println(a[i]);
        }
    }
}

- gurpreet.kharoud88 September 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<?php
$arr = array(1, 1, 3, -2, 2);
$arr = customSort($arr);
var_dump(implode(",",$arr));

function customSort($arr)
{
    $negCount = 0;
    foreach($arr as $value){

        if($value < 0){
            $negCount++;
        }
    }
    $sIndex = 0;
    /*if(count($arr) % 2 == 0){
        $eIndex = count($arr) - $negCount ;
    }else{
        $eIndex = count($arr) - $negCount -1;
    }*/

    $eIndex = $negCount ;
    $i = 0;
    while($sIndex < $negCount){
        if($arr[$i] < 0){
            $temp = $arr[$i];
            $arr[$i]=$arr[$sIndex];
            $arr[$sIndex] = $temp;
            $sIndex++;
            $i++;
        }else{
            $temp = $arr[$i];
            $arr[$i]=$arr[$eIndex];
            $arr[$eIndex] = $temp;
            $eIndex++;
        }
    }
    return $arr;

}

?>

- VV September 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(n) :)

- VV September 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have a completly different approach.

What I would suggest is to use Godel numbering to hold the array. we will have 2 Godel numbering. one for the positive numbers, and one for the negative ones.

The godel numbers will be created based on the position of the numbers in the array.

there are some issues in the solution, such as Godel number might grow exponentially with n, and also that if the numbers are not in N, this method won't work.

but still this is a cool approach, maybe someone can develop it a bit more.

- Bee September 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using double pointers. The first pointer is to head and the other one to tail.

If the first pointer value is less than zero, first pointer move one step forward. Otherwise, if first pointer greater than zero, waiting second pointer scan from tail till find the first one which is negative.

The complex is O(1) (the constant is 1) and space is O(1) .

static List<int> DoSearch(List<int> n) {

            if ((n.Count == 1) || (n.Count == 0))
                return n;

            int x = 0;
            int y = n.Count - 1;


            while (x <= y) {

                if (n[x] > 0) {

                    while (n[y] >= 0)
                    {
                        y--;
                    }

                    if (y <= x)
                        break;

                    int m = n[x];
                    n[x] = n[y];
                    n[y] = m;

                    x++;
                    y--;
                }

                x++;
            }

            return n;        
        }

- dingli.china September 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int negatifindex=0;
int prevnegatifindex=-1;
int pozitifindex=4; // array.length-1
int nextpozitifindex=-1;
while (negatifindex<=pozitifindex)
{
if(array[negatifindex]<0)
{
if (prevnegatifindex!=-1)
swap(array[prevnegatifindex],array[negatifindex])
prevnegatifindex=-1;
negatifindex++;

}
if(array[pozitifindex]>0)
{
if (nextpozitifindex!=-1)
swap(array[nextpozitifindex],array[pozitifindex])
nextpozitifindex=-1;
pozitifindex--;
}
if (array[pozitifindex]<0 & array[negatifindex]>0)
{
swap(array[pozitifindex],array[negatifindex])
prevnegatifindex=negatifindex;,
pozitifindex--;
nextpozitifindex=pozitifindex;
negatifindex++;
}
}

Time complexity is O(n) and space is O(1)

- Gözde September 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Let's solve this problem by diving it into two much simpler problems:
A) We want negative numbers to be at the right positions; we don't care about the positive one
B) We move the positive numbers at the right positions, not caring about the negative one
C) We apply A B on copies of the array and then combine the result to get the final solution

A and B can be easily solve linearly.

Solution for A:
{{
void solveA(int* a, int n)
{
int p = 0;
for (int i = 0; i < n; i++)
if (a[i] < 0)
{
a[p] = a[i];
p++
}
}
}}

For B the solution is similar.

C) is also quite easy. We just need to count how many negative and positive number we have in order to know how many values to copies from the two partial solution.

Complexity: O(n) both time and space

- Andrei September 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package problems;

public class 
SpecialSort 
{
	public static int[]
	SS
	(int... is)
	{
		for (int i = is.length - 1; i > 0; --i)
			for (int j = i; j < is.length && is[j-1] >= 0 && is[j] < 0; ++j) {
				int tmp = is[j-1];
				is[j-1] = is[j];
				is[j] = tmp;
			}	
		return is;
	}
}

- David Illescas September 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) and O(n)

void positionSort(int x[])
{
	int tempArr[count];
	memcpy(tempArr,x,count*sizeof(int));

	int neg_index = 0, 
		pos_index=count-1,temp=0;
	
	for(int i=0;i<count;i++)
	{
		if(tempArr[i] < 0)
		{
			x[neg_index++] = tempArr[i];
		}

		if(tempArr[count-i] >= 0)
		{
			x[pos_index--] = tempArr[count-i];

		}

	}

}

- Anonymous October 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's the simple code, where you shift right everything when you encounter negative number.

public static void specialOrderedSort(int[] array){
		if ( array == null){
			return;
		}
		int negNumIndex = -1;
		int firstPosNumIndex = -1;
		for ( int index = 0; index < array.length; index++){
			if(array[index] < 0){
				negNumIndex = index;
			}else{
				if ( firstPosNumIndex == -1){
					firstPosNumIndex = index;
				}
			}
			
			if ( negNumIndex >= firstPosNumIndex){
				int negNum = array[negNumIndex];
				for ( int i = negNumIndex-1; i >= firstPosNumIndex;i--){
					array[i+1]=array[i];
				}
				array[firstPosNumIndex] = negNum;
				firstPosNumIndex++;
				negNumIndex = -1; //reset to get next -ve number position.
			}
		}
		
	}

- sathya October 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This works in O(n) time and O(1) space.

Algorithm:

index = -1 // maintains the current index where the first positive number is stored
for i = 1 to n:
	if(a[i] < 0) {
		if(index != -1) {
			swap(&a[index], &a[i])
			index ++
		}
	} else {
		if(index == -1) 
			index = i
	}	
endFor

- rishabhnigam31 November 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my solution O(n) time and constant space complexity
1) count number of negative numbers in the array
2) set the index where positive number is supposed to start as pivot
3) count number of positive numbers before pivot and after pivot
4) iterate each number in the array until pivot
a) if number is negative proceed
b) if number if positive initiate rearrangment to place each number in its correct position until we come back to current position.

c++ code

#include <iostream>
using namespace std;
int countNegatives(int a[], int n){
	int negNums = 0;
	for(int i = 0 ; i < n ; ++i){
		if(a[i] < 0)
			negNums++;
	}
	return negNums;
}

int countPositivesBeforePivot(int a[], int pivot){
	int numPos = 0;
	for(int i = 0 ; i < pivot ; ++i){
		if(a[i] > 0)
			numPos++;
	}
	return numPos;
}

void rearrange(int a[], int posCount, int i, int numNegs, int posBeforePivots, int posAfterPivots){
	int nexti = posCount + numNegs - 1;
	int curval = a[i];
	while(nexti != i){
		int temp = a[nexti];
		a[nexti] = curval;
		curval = temp;
		cout << nexti << " " << temp << endl;
		if(temp > 0){
			cout << "positive" << endl;
			nexti = nexti  + posBeforePivots;
		}
		if(temp < 0){
			cout << "negative" << endl;
			nexti = nexti - (posBeforePivots + posAfterPivots);
		}
	}
	a[i] = curval;
}
void sepNegnPos(int a[], int n){
	int negNums = countNegatives(a, n);
	std::cout << " num negs " << negNums << std::endl;
	int posBeforePivots = countPositivesBeforePivot(a, negNums);
	std::cout << " num pos before pivot " << posBeforePivots << std::endl;
	int posAfterPivots = n - negNums - posBeforePivots;
	int numPosSofar = 0;
	for(int i = 0 ; i < negNums ; ++i){
		std::cout << a[i] << std::endl;
		if(a[i] == 0){
			std::cout << "zero not allowed" << std::endl;
			return;
		}
		if(i < negNums && a[i] < 0)
			continue;
		else if(i < negNums && a[i] > 0){
			numPosSofar++;
			rearrange(a, numPosSofar, i, negNums, posBeforePivots, posAfterPivots);
		}
	}
}
int main(void){
	int a[] = {-1, 1, 4, 3, 5, -2, -3};
	sepNegnPos(a, 7);
	for(int i = 0 ; i < 7 ; ++i){
		std::cout << a[i] << " ";
	}
	std::cout << std::endl;
}

- Vinni December 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Instead of numbers we should work with segments of positive or negative numbers. Lets say the numbers are [1 2 -1 -2 -3 4 5 6 -7 -8 -9].

initial segments: [1 2], [-1 -2 -3]*, [4 5 6], [-7 -8 -9]
step 1. [-1 -2], [1 2]*, [-3], [4 5 6], [-7 -8 -9] ... pushed right seg to left, 2 swaps
step 2. [-1 -2 -3], [1 2 4 5 6]*, [-7 -8 -9] ... pushed left seg to right, 2 swaps
step 3. [-1 -2 -3], [1 2], [-7 -8 -9]*, [4 5 6] ... pushed left seg to right, 3 swaps
step 4. [-1 -2 -3 -7 -8], [1 2]*, [-9], [4 5 6] ... pushed right seg to left, 2 swaps
step 5. [-1 -2 -3 -7 -8 -9], [1 2 4 5 6] ... pushed left seg to right, 2 swaps

Total 11 swaps.

Lets say the negative segment is N and the positive segment is P. Now, given a situation like "[all negative], P, N, [unknown]", we need to do the following.

1. If |N| >= |P|, send right segment to left, total swap needed |N|+|P|
2. If |N| < |P|, send left segment to right, total swap needed |N|+|P|

Amortized O(n).

- lasthope January 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please let me know if it has any problem? it is in O(N) time complexity and O(1) space.

/*
============================================================================
Author         : Shashi Shekhar
Email          : shashishekhar32@gmail.com
Description    : Given an array which has n integers. It has both positive and negative integers.Now you need to sort this array in such a way that,the negative integers should be in the front,and the positive integers should at the back.Also the relative position should not be changed.
				eg. -1 1 3 -2 2 ans: -1 -2 1 3 2.Required running time complexity is O(N) and the space complexity is O(1)
Created Date   : 26-JAN-2014
===========================================================================
*/
#include<stdio.h>


void sort_array(int arr[],int n)
{
	int count =0;
	int temp1=0;
	int pos_to_fill_with_positive_num=0;
	int pos1=0;
	int pos2=0;
	int just_moved =0;
	int num_remaining=0;

	for(int i=0;i<n;i++)
	{
		if(arr[i]<0)
		{
			count++;
		}
	}
	pos1 = count;
	num_remaining=count;
	for(int i=0;i<n;i++)
	{
		if(arr[i]<0)
		{
			temp1=arr[pos2];
			arr[pos2]=arr[i];
			arr[i]=temp1;
			pos2++;
			if(pos1>=i && i>count)
				{pos1++;
			just_moved=1;
			}
			
			num_remaining--;
		}
		else
		{
			if(pos2==count)
				break;
			else if((i>=count) && (i<pos1) &&(!just_moved))
				continue;
			else if(just_moved)
			{
				just_moved=0;
				temp1=arr[i];
				arr[i]=arr[pos2];
				arr[pos2]=temp1;
			}
			else
				{	
				
					if(i<count)
					{
						temp1=arr[pos1];
						arr[pos1]=arr[i];
						if((pos_to_fill_with_positive_num>=pos2)&&(pos_to_fill_with_positive_num<count))
						arr[pos_to_fill_with_positive_num]=temp1;
						else if(pos_to_fill_with_positive_num<count)
							arr[++pos_to_fill_with_positive_num]=temp1;
						else
						{
							pos_to_fill_with_positive_num=pos2;
							arr[pos_to_fill_with_positive_num]=temp1;
						}
						pos_to_fill_with_positive_num++;
						pos1++;
					}
					else
					{
						temp1=arr[pos1];
						arr[pos1]=arr[pos_to_fill_with_positive_num];
						arr[pos_to_fill_with_positive_num]=temp1;
						pos_to_fill_with_positive_num++;
						pos1++;
					}
				  }
		}

		if(num_remaining==0)
			break;
	}
}

void main()
{
	int n = 9;
	int arr[9]={-1,1,3,4,6,-3,1,-2,2};
	//int arr[7]={-1,3,-2,4,5,-5,9};
	//int arr[5]={-1,1,3,-2,2};
	printf("\input array:");
	for(int i=0;i<n;i++)
	printf(" %d ",arr[i]);
	sort_array(arr,n);
	printf("\noutput array");
	for(int i=0;i<n;i++)
	printf(" %d ",arr[i]);
	
}

- shashi shekhar January 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

#include<stdio.h>


void sort_array(int arr[],int n)
{
	int count =0;
	int temp1=0;
	int pos_to_fill_with_positive_num=0;
	int pos1=0;
	int pos2=0;
	int just_moved =0;
	int num_remaining=0;

	for(int i=0;i<n;i++)
	{
		if(arr[i]<0)
		{
			count++;
		}
	}
	pos1 = count;
	num_remaining=count;
	for(int i=0;i<n;i++)
	{
		if(arr[i]<0)
		{
			temp1=arr[pos2];
			arr[pos2]=arr[i];
			arr[i]=temp1;
			pos2++;
			if(pos1>=i && i>count)
				{pos1++;
			just_moved=1;
			}
			
			num_remaining--;
		}
		else
		{
			if(pos2==count)
				break;
			else if((i>=count) && (i<pos1) &&(!just_moved))
				continue;
			else if(just_moved)
			{
				just_moved=0;
				temp1=arr[i];
				arr[i]=arr[pos2];
				arr[pos2]=temp1;
			}
			else
				{	
				
					if(i<count)
					{
						temp1=arr[pos1];
						arr[pos1]=arr[i];
						if((pos_to_fill_with_positive_num>=pos2)&&(pos_to_fill_with_positive_num<count))
						arr[pos_to_fill_with_positive_num]=temp1;
						else if(pos_to_fill_with_positive_num<count)
							arr[++pos_to_fill_with_positive_num]=temp1;
						else
						{
							pos_to_fill_with_positive_num=pos2;
							arr[pos_to_fill_with_positive_num]=temp1;
						}
						pos_to_fill_with_positive_num++;
						pos1++;
					}
					else
					{
						temp1=arr[pos1];
						arr[pos1]=arr[pos_to_fill_with_positive_num];
						arr[pos_to_fill_with_positive_num]=temp1;
						pos_to_fill_with_positive_num++;
						pos1++;
					}
				  }
		}

		if(num_remaining==0)
			break;
	printf("\nin step %d",i+1);
	for(int j=0;j<n;j++)
	printf(" %d ",arr[j]);
	}
}

void main()
{
	int n = 9;
	int arr[9]={-1,1,3,4,6,-3,1,-2,2};
	//int arr[7]={-1,3,-2,4,5,-5,9};
	//int arr[5]={-1,1,3,-2,2};
	printf("\input array:");
	for(int i=0;i<n;i++)
	printf(" %d ",arr[i]);
	sort_array(arr,n);
	printf("\noutput array");
	for(int i=0;i<n;i++)
	printf(" %d ",arr[i]);
	
}

- shashi shekhar January 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] arg) {
int[] arr = { -1, 1, 3, -2, 2, -7, 8 };
System.out.println(Arrays.toString(arr));
for (int i = 0; i < arr.length; i++) {
if (arr[i] < 0) {
checkAndSwap(arr, i);
}
}
System.out.println(Arrays.toString(arr));
}
private static void checkAndSwap(int[] arr, int currIndex) {
for (int i = currIndex - 1; i > 0; i--) {
if (arr[i] > 0) {
int temp = arr[i];
arr[i] = arr[currIndex];
arr[currIndex] = temp;
currIndex = i;
} else {
break;
}
}
}

- prateek February 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{ public static void main(String[] arg) {
int[] arr = { -1, 1, 3, -2, 2, -7, 8 };
System.out.println(Arrays.toString(arr));
for (int i = 0; i < arr.length; i++) {
if (arr[i] < 0) {
checkAndSwap(arr, i);
}
}
System.out.println(Arrays.toString(arr));
}
private static void checkAndSwap(int[] arr, int currIndex) {
for (int i = currIndex - 1; i > 0; i--) {
if (arr[i] > 0) {
int temp = arr[i];
arr[i] = arr[currIndex];
arr[currIndex] = temp;
currIndex = i;
} else {
break;
}
}
}
}

- Anonymous February 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class TestLogic {

public static void main(String[] arg) {
int[] arr = { -1, 1, 3, -2, 2, -7, 8 };
System.out.println(Arrays.toString(arr));
for (int i = 0; i < arr.length; i++) {
if (arr[i] < 0) {
checkAndSwap(arr, i);
}
}
System.out.println(Arrays.toString(arr));
}
private static void checkAndSwap(int[] arr, int currIndex) {
for (int i = currIndex - 1; i > 0; i--) {
if (arr[i] > 0) {
int temp = arr[i];
arr[i] = arr[currIndex];
arr[currIndex] = temp;
currIndex = i;
} else {
break;
}
}
}
}

- prateek87mathur February 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class TestLogic {

public static void main(String[] arg) {
int[] arr = { -1, 1, 3, -2, 2, -7, 8 };
System.out.println(Arrays.toString(arr));
for (int i = 0; i < arr.length; i++) {
if (arr[i] < 0) {
checkAndSwap(arr, i);
}
}
System.out.println(Arrays.toString(arr));
}
private static void checkAndSwap(int[] arr, int currIndex) {
for (int i = currIndex - 1; i > 0; i--) {
if (arr[i] > 0) {
int temp = arr[i];
arr[i] = arr[currIndex];
arr[currIndex] = temp;
currIndex = i;
} else {
break;
}
}
}
}

- prateek87mathur February 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The problem can indeed be solved in O(n) time and with O(1) complexity.

Below is my solution:

#include <vector>
#include <iostream>
#include <stdio.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repv(i, v) for(int i = 0; i < v.size(); i++)

void printArray(const vector<int> &A)
{
	repv(i, A) cout << A[i] << " ";
	cout << endl;
}

void reverse(vector<int> &A, int start, int end)
{
	while(start < end) swap(A[start++], A[end--]);
}

void sortPosNeg(vector<int> &A)
{
	// find and sort each segment of positive-streak followed by negative-streak
	// time complexity -- O( A.size() ) , space complexity -- O(1)
	int pstart, pend;
	int nstart, nend;
	int i = 0;
	
	while(i < A.size())
	{
		// ignore leading streak of negatives
		if( i == 0 )
		{	
			while(i < A.size() && A[i] < 0) i++;		
			if(i == A.size()) break;
			printf( "leading neg-streak: (%d,%d)\n", 0, i-1);

			pstart = i;
			pend = pstart;
		}	

		// find start and end of postive-streak -- O( length(pos-streak) )
		while(pend < A.size() && A[pend] > 0) pend++;
		if(pend-- == A.size()) break;

		printf( "pos-streak: (%d,%d)\n", pstart, pend);

		// find start and end of negative-streak -- O( length(neg-streak) )
		nstart = pend+1;

		nend = nstart;
		while(nend < A.size() && A[nend] < 0) nend++;
		nend--;

		printf( "neg-streak: (%d,%d)\n", nstart, nend);

		// now swap positions pos-streak with neg-streak
		// Note: this is just like reversing words in a sentence
		reverse(A, pstart, pend); // O( length(pos-streak) )
		reverse(A, nstart, nend); // O( length(neg-streak) )
		reverse(A, pstart, nend); // O( length(pos-streak) + O( length(neg-streak) )
		// update the position of the positive-streak which we just moved
		pstart = nend - (pend - pstart);
		pend = nend;

		// A[0] to A[nend] has been sorted now move on to the rest of the array
		i = nend + 1;
	}	
}

int main()
{
	// read data
	int N;
	cin >> N;

	vector<int> A(N);
	rep(i, N) cin >> A[i];
	cout << "Before sorting: " << endl;
	printArray(A);

	// sort the array
	sortPosNeg(A);
	cout << "After sorting: " << endl;
	printArray(A);

	return 0;
}

Approach:

Think of the array as continguous streaks of positive and negative integers: [n0 p1, n1, p2, n2, p3, n3, ...]

Each streak can have any number of integers in it.

We can ignore the leading streak of negative integers (if any) because they are already in the sorted position.

Now we need to find a solution to sort each [pi, ni] pair or a positive streak followed by a negative streak.

After sorting [pi, ni] we get [ni, pi] -- essentially swap/switch the locations of the streaks.

To do this, do the following steps

-- Reverse pi to get rev(pi)
-- Reverse ni to get rev(ni)
-- Reverse [ rev(pi), rev(ni) ] to get [ rev(rev(ni)), rev(rev(pi)) ] which is equal to [ni, pi]

This is very similar to reversing all the words within a sentence (not the whole sentence).

I would appreciate it if you could correct me if i am wrong anywhere.

- Deepak Roy February 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution in C++ below. Running time is O(n) (two passes) and it's done in place (O(1) extra-space) :

#include <iostream>
#include <vector>

using namespace std;

void swap(vector<int>& L, int i, int j) {
    int tmp = L[i];
    L[i] = L[j];
    L[j] = tmp;
}

void signSort(vector<int>& L) {
    int cntNeg = 0, i = 0, j = 0;
    for (vector<int>::iterator it = L.begin(); it < L.end(); ++it) {
        if (*it < 0) ++cntNeg;
    }
    while (i < cntNeg && cntNeg + j < L.size()) {
        if (L[i] >= 0) {
            swap(L, i, cntNeg + j);
            ++j;
        } else {
            ++i;
        }
    }
}

int main(int argc, char **argv) {
    vector<int> L;
    L.push_back(-1);
    L.push_back(1);
    L.push_back(3);
    L.push_back(-2);
    L.push_back(2);
    signSort(L);
    for (vector<int>::iterator it = L.begin(); it != L.end(); ++it) {
        cout << *it << endl;
    }
    return 0;
}

- Thomas February 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There is a paper showing O(n) time and O(1) space algorithm "Stable minimum space partitioning in linear time."
diku.dk/hjemmesider/ansatte/jyrki/Paper/KP92b.pdf

- lasthope February 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time O(N) and space O(1)

#include <stdio.h>

/*
	we will take positive number block and negative number block.
	And will move negative number block in front of positive number block.
*/

int main()
{
	int num[] = {-1, 1, 3, -2, -3, 4, 5, -7, 2, 8, -8};
	int len = sizeof(num)/sizeof(int);
	int i,l_t,var_t;
	int ps,pe,ns,ne,nc,pc;

	ps = pe = ns = ne = 0;

	while (1){
		for (;num[ps] < 0; ps++); /* Find start of positive number block */
		for (pe = ps; num[pe+1] >= 0 && pe+1 < len; pe++);  /* Find end of positive number block */
		if (pe+1 == len) {
			break;
		}
		ns = pe + 1; /* Assign start of negative number block */
		for (ne = ns; num[ne+1] < 0 && ne+1 < len; ne++);  /* Find end of negative number block */
		nc = ne - ns + 1;  /* Count negative numbers in block */
		pc = pe - ps + 1;  /* Count positive numbers in block */

		i = ns;
		var_t = num[ns];
		while (1) {
			if (i-pc >= ps && num[i-pc] >= 0) {  /* Move negative number to new position */
				i -= pc;
				l_t = num[i];
				num[i] = var_t;
				var_t = l_t;
			} else if (i+nc <= ne) { /* Move positive number to new position */
				i += nc;
				l_t = num[i];
				num[i] = var_t;
				var_t = l_t;
			} else {  /* Pick next -ve number  */
				for (;num[ns] >= 0 && ns <= ne; ++ns);
				if (ns > ne) break;
				i = ns;
				var_t = num[ns];
			}
		}
	}

	for (i=0; i < len; ++i) {
		printf("%d ", num[i]);
	}
	printf("\n");
	
	return 0;
}

- Girish February 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void sortNegPos(int arr[], size n)
{
	int i = 0, j = n-1, index = -1, key = 0;

	while (arr[i] < 0)
	i++;

	while (arr[j] >= 0)
	j--;

	// At this point i points to the first positive integer and j to the last negative integer

	index = i;
	key = arr[i];

	while (i < j)
	{
		if (key >= 0)
		{
			key = arr[i + 1];
			arr[i+1] = arr[i];
		}
		else
		{
			arr[index] = key;
			++index; 
		}
		i++;
	}
}

- Bhuvan March 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isNegative(int t) {
return t < 0 ? true : false;
}

void sort(int A[], int n) {
std::stable_partition(A, A + n, isNegative);
}

- muyepiaozhou March 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isNegative(int t) {
return t < 0 ? true : false;
}

void sort(int A[], int n) {
std::stable_partition(A, A + n, isNegative);
}

- muyepiaozhou March 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isNegative(int t) {
return t < 0 ? true : false;
}

void sort(int A[], int n) {
std::stable_partition(A, A + n, isNegative);
}

- muyepiaozhou March 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isNegative(int t) {
return t < 0 ? true : false;
}

void sort(int A[], int n) {
std::stable_partition(A, A + n, isNegative);
}

- muyepiaozhou March 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The following solution seems like O(n) time and O(1) to me. Comments?

/* Align negative numbers on one side and positive on the other, with relative positions unperturbed. */

uint64_t i;
uint64_t j;

for (i = 0; i < n; ++ i) {
    if (a[i] < 0) {
        ++negativeCount;
    }
}

for (i = 0, j = negativeCount; i < negativeCount && j < n;) {
    if (a[i] > 0 && a[j] > 0) {
        swap(a[i], a[j]);
        ++j;
    } else if (a[i] < 0) {
        ++i;
    } else {
        // a[j] < 0
        swap(a[i], a[j]);
        ++i;
    }
}

- Anonymous March 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void NegPostSort(int[] a, int low)
        {
            int neg = -1;
            int pos = -1;
            int current = low;
            while ((current < a.Length) && ((neg < 0) || (pos < 0)))
            {
                if (a[current] > 0 && pos < 0)
                    pos = current;
                if (a[current] < 0 && neg < 0)
                    neg = current;
                current++;
            }
            
            while (neg > pos)
            {
                swap(ref a[neg], ref a[--neg]);
            }
            if (++neg < a.Length && current < a.Length)
                NegPostSort(a, neg);
        }

        private void swap(ref int a, ref int b)
        {
            int t = a;
            a = b;
            b = t;

}

- tunguyen161088 March 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void NegPostSort(int[] a, int low)
        {
            int neg = -1;
            int pos = -1;
            int current = low;
            while ((current < a.Length) && ((neg < 0) || (pos < 0)))
            {
                if (a[current] > 0 && pos < 0)
                    pos = current;
                if (a[current] < 0 && neg < 0)
                    neg = current;
                current++;
            }
            
            while (neg > pos)
            {
                swap(ref a[neg], ref a[--neg]);
            }
            if (++neg < a.Length && current < a.Length)
                NegPostSort(a, neg);
        }

        private void swap(ref int a, ref int b)
        {
            int t = a;
            a = b;
            b = t;

}

- tunguyen161088 March 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void reOrder(final int[] a, final int n) {
int j = 0;
for (int i = 0; i < n; i++) {
if (a[i] < 0) {
int k = i;
while (k - 1 >= j && a[k - 1] > 0) {
final int temp = a[k];
a[k] = a[k - 1];
a[k - 1] = temp;
k--;
}
j++;
}
}
}

- @lvns April 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
void reOrder(final int[] a, final int n) {
// TODO Auto-generated method stub
int j = 0;
for (int i = 0; i < n; i++) {
if (a[i] < 0) {
int k = i;
while (k - 1 >= j && a[k - 1] > 0) {
final int temp = a[k];
a[k] = a[k - 1];
a[k - 1] = temp;
k--;
}
j++;
}
}
}
}

- Anonymous April 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{code}

void reOrder(final int[] a, final int n) {
// TODO Auto-generated method stub
int j = 0;
for (int i = 0; i < n; i++) {
if (a[i] < 0) {
int k = i;
while (k - 1 >= j && a[k - 1] > 0) {
final int temp = a[k];
a[k] = a[k - 1];
a[k - 1] = temp;
k--;
}
j++;
}
}
}

- @lvns April 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This works.

void reOrder(final int[] a, final int n) {
// TODO Auto-generated method stub
int j = 0;
for (int i = 0; i < n; i++) {
if (a[i] < 0) {
int k = i;
while (k - 1 >= j && a[k - 1] > 0) {
final int temp = a[k];
a[k] = a[k - 1];
a[k - 1] = temp;
k--;
}
j++;
}
}
}

- @lvns April 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This works.

void reOrder(final int[] a, final int n) {
// TODO Auto-generated method stub
int j = 0;
for (int i = 0; i < n; i++) {
if (a[i] < 0) {
int k = i;
while (k - 1 >= j && a[k - 1] > 0) {
final int temp = a[k];
a[k] = a[k - 1];
a[k - 1] = temp;
k--;
}
j++;
}
}
}

- @lvns April 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If anybody comes up with an O(1) space, O(n) time solution, we can work together and write a paper on in-place, stable, O(n logn) worst-case sorting algorithm.

- jatin085 April 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the java implementation for O(n) time complexity, O(1) space complexity solution. Pretty sure others would have answered it already on this forum...I just did not take time to go through all the solutions.

import java.util.Arrays;
import java.util.List;

public class Sort {

    public static void main(String[] args) {
        System.out.println(sortPositiveNegative(Arrays.asList(-1, 1, 2, -4, 6, 8, -8, 10)));
    }

    public static List<Integer> sortPositiveNegative(List<Integer> numbers) {
        int numbersCount = numbers.size();
        // select pivot as 0 because we want to keep all negative numbers before
        // any positive numbers
        int pivot = 0;

        int i = 0;
        // Lets take i to the first positive number. Before that everything is
        // sorted anyways.
        while (numbers.get(i) < pivot) {
            i++;
        }

        // Rearrange rest of the numbers properly.
        for (int j = i + 1; j < numbersCount; j++) {
            if (numbers.get(j) < pivot) {
                swap(i, j, numbers);
                i++;
            }
        }

        return numbers;
    }

    private static void swap(int i, int j, List<Integer> numbers) {
        // keep it simple as below or try some bit manipulation.
        int temp = numbers.get(i);
        numbers.set(i, numbers.get(j));
        numbers.set(j, temp);
    }
}

- abhi June 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can anyone find something wrong with this? It should be O(n)/O(1).

void weird_sort(int a[], int n)
{
	.
	.
	/* Find first positive number */
	for (i=0; i<n; i++)
	{
		if (a[i]>=0) break;
	}

	pivot=i;

	/* Swap negative numbers and advance pivot */
	for (i=pivot+1; i<n; i++)
	{
		if (a[i]<0)
		{
			swap(a,i,pivot);
			pivot++;
		}
	}

- Alex P June 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Below is basically a merge-sort implementation. I did this in Python but easy to port to C. It is O(N logN) I think (log N calls to sort, merge is O(n)), and could be farmed out to multiple machines too for each independent part for scale. Not sure how to evaluate space usage -- do you count the stack? Also, the Python tuple concatenation and list division is not ideal in memory usage of course but could easily be improved and done in-place in C.

#!/usr/bin/env python

import sys


def sort(l):
    if len(l) == 1:
        return l
    elif len(l) == 2:
        if l[0] > 0 and l[1] < 0:
            return (l[1], l[0])
        else:
            return (l[0], l[1])
    else:
        return merge(sort(l[0:len(l)/2]), sort(l[len(l)/2:]))

def merge(l1, l2):
    result = ()
    for val in l1 + l2:
        if val < 0:
            result += (val,)
    for val in l1 + l2:
        if val >= 0:
            result += (val,)
    return result

if __name__ == '__main__':
    print sort(tuple([int(v) for v in sys.argv[1].split(',')]))

- Dan July 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

example: -1 , 1 , 3 , -2 , 2, -4 , 4 , 5 , -5

O(n) time O(1) space solution

Count the number of negative elements (k = 4 here) , as a first step try to get first 4 elements in correct order, every time you swap an element out record its index, let f be the encoding function for negatives and g for positives.
Step1.1 : -1 , 1 , -4 , -5 , 2 , g(3,3), 4 , 5 , f(-2,4)
Step1.2 ( f(x,y) will be in the order f(x1, y1), f(x2, y2), f(x3, y3) , ..., where y1 < y2 < y3 < .. , same property holds for g). But you have the rest of the negative elements in their final destinations, freeze these elements. Treat f(x,y) as your new negatives on an array, perform swaps similar to step1, let h be the encoding function for positives dislocated in this step:
-1 , f(-2,4) , -4 , -5 , 2 , g(3,3) , 4 , 5 , h(1,2)
Step2: Stable sort the unfrozen negative elements
Step3: Now you are done with all the negatives. You have the property max(y / h(x,y)) < max(y / g(x,y)), again h(x,y) will appear in increasing order of y. Stable sort h union g relative to the other positives:
<all negatives> , h(1,2) , g(3,3), 2 , 4 , 5

You can always pick to work on the positives first / negatives first based on the sizes of arrays appearing in the recursive step. So you would have
T(n) = O(n) + T(a) + T(b) ( where a+b < 3n/4)
so T(n) = O(n)

It is unreasonable to expect someone to solve this within 1 hour

- just_do_it July 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] PosNegSort(int[] dataArray)
        {
            int[] result = new int[dataArray.Length];
            int index = 0;

            // 1 - Collect the negative numbers first.
            foreach (int data in dataArray)
            {
                if (data < 0)
                {
                    result[index++] = data;
                }
            }

            // 2 - Collect the zero(s) second.
            foreach (int data in dataArray)
            {
                if (data == 0)
                {
                    result[index++] = data;
                }
            }

            // 3 - And finally collect the positive numbers.
            foreach (int data in dataArray)
            {
                if (data > 0)
                {
                    result[index++] = data;
                }
            }

            return result;
        }

- hatiger July 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class SpecialSort {
	
	public static void main(String[] args) {
		int[] data = {-1, 1, 3, -2, 2};
		int length = data.length - 1;
		
		int[] specialSort = specialSort(data, length);
		for(int i=0; i<specialSort.length; i++){
			System.out.printf("%d ", specialSort[i]);
		}
	}

	private static int[] specialSort(int[] data, int length) {
		for(int i=0; i<length-1; i++){
			for(int k=0; k<length-i; k++){
				if(data[k] > 0 && data[k+1] < 0){
					int temp = data[k];
					data[k] = data[k+1];
					data[k+1] = temp; 
				}
			}
		}
		return data;
	}
}

- SuhyunJeon July 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Bubble sort, only a[i]>0&&a[i+1]<0 will exchange each other
Code:

public class HelloWorld{

     public static void main(String []args){
       int a[]={-1,3,5,-7,2,4,-6,8};
       int len=a.length;
       for(int i=0;i<len;i++)//bubble sort times
       {
           for(int j=0;j<len-1-i;j++)// times of comparison in each loop
           {
             if(a[j]>0&&a[j+1]<0)
             {a[j]=a[j]-a[j+1];
             a[j+1]=a[j]+a[j+1];
             a[j]=a[j+1]-a[j];
             }
           }
       }
       for (int i=0;i<len;i++)
       {
           System.out.println(a[i]);
       }
     }
}

- jkboy880826 August 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Bubble sort, only a[i]>0&&a[i+1]<0 will exchange each other
Code:

public class HelloWorld{

     public static void main(String []args){
       int a[]={-1,3,5,-7,2,4,-6,8};
       int len=a.length;
       for(int i=0;i<len;i++)//bubble sort times
       {
           for(int j=0;j<len-1-i;j++)// times of comparison in each loop
           {
             if(a[j]>0&&a[j+1]<0)
             {a[j]=a[j]-a[j+1];
             a[j+1]=a[j]+a[j+1];
             a[j]=a[j+1]-a[j];
             }
           }
       }
       for (int i=0;i<len;i++)
       {
           System.out.println(a[i]);
       }
     }
}

- jkboy880826 August 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Bubble sort, only a[i]>0&&a[i+1]<0 will exchange each other
Code:

public class HelloWorld{

     public static void main(String []args){
       int a[]={-1,3,5,-7,2,4,-6,8};
       int len=a.length;
       for(int i=0;i<len;i++)//bubble sort times
       {
           for(int j=0;j<len-1-i;j++)// times of comparison in each loop
           {
             if(a[j]>0&&a[j+1]<0)
             {a[j]=a[j]-a[j+1];
             a[j+1]=a[j]+a[j+1];
             a[j]=a[j+1]-a[j];
             }
           }
       }
       for (int i=0;i<len;i++)
       {
           System.out.println(a[i]);
       }
     }
}

- jkboy880826 August 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Bubble sort, only a[i]>0&&a[i+1]<0 will exchange each other
Code:

public class HelloWorld{

     public static void main(String []args){
       int a[]={-1,3,5,-7,2,4,-6,8};
       int len=a.length;
       for(int i=0;i<len;i++)//bubble sort times
       {
           for(int j=0;j<len-1-i;j++)// times of comparison in each loop
           {
             if(a[j]>0&&a[j+1]<0)
             {a[j]=a[j]-a[j+1];
             a[j+1]=a[j]+a[j+1];
             a[j]=a[j+1]-a[j];
             }
           }
       }
       for (int i=0;i<len;i++)
       {
           System.out.println(a[i]);
       }
     }
}

- jkboy880826 August 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Bubble sort, only a[i]>0&&a[i+1]<0 will exchange each other
Code:

public class HelloWorld{

     public static void main(String []args){
       int a[]={-1,3,5,-7,2,4,-6,8};
       int len=a.length;
       for(int i=0;i<len;i++)//bubble sort times
       {
           for(int j=0;j<len-1-i;j++)// times of comparison in each loop
           {
             if(a[j]>0&&a[j+1]<0)
             {a[j]=a[j]-a[j+1];
             a[j+1]=a[j]+a[j+1];
             a[j]=a[j+1]-a[j];
             }
           }
       }
       for (int i=0;i<len;i++)
       {
           System.out.println(a[i]);
       }
     }
}

- jkboy880826 August 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Bubble sort, only a[i]>0&&a[i+1]<0 will exchange each other
Code:

public class HelloWorld{

     public static void main(String []args){
       int a[]={-1,3,5,-7,2,4,-6,8};
       int len=a.length;
       for(int i=0;i<len;i++)//bubble sort times
       {
           for(int j=0;j<len-1-i;j++)// times of comparison in each loop
           {
             if(a[j]>0&&a[j+1]<0)
             {a[j]=a[j]-a[j+1];
             a[j+1]=a[j]+a[j+1];
             a[j]=a[j+1]-a[j];
             }
           }
       }
       for (int i=0;i<len;i++)
       {
           System.out.println(a[i]);
       }
     }
}

- jkboy880826 August 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void sortArray() {
        int changeIndex = -1;
        int[] a = {-34, -3, 41, 2, -3, -4, 4, 54, -56, 43, -34, 34, 345, -55, 55, -5, 6, 8, 9, -8};
        displayArrayElements(a);
        for (int i = 0; i < a.length - 1; i++) {
            if (a[i] * a[i + 1] < 0) {
                if (changeIndex == -1) {
                    changeIndex = i + 1;
                } else {
                    moveElements(a, changeIndex, i + 1);
                    changeIndex += 1;
                }
            } else {
            }
        }
        displayArrayElements(a);
    }

    private static void displayArrayElements(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }

    private static void moveElements(int[] a, int changeIndex, int i) {
        int element = a[i];
        for (int j = i; j > changeIndex; j--) {
            a[j] = a[j - 1];
        }
        a[changeIndex] = element;
    }

- Ch.deepak08 September 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static int[] reorderArray(int[] input) {
        if (input==null || input.length==0)
            return input;
        int fistPositiveNumber = -1;
        int temp = 0;
        for (int position = 0;position<input.length; position++) {
            if (input[position]>0 && fistPositiveNumber<0)
                fistPositiveNumber = position;
            if (input[position]<0 && fistPositiveNumber>=0) {
                temp = input[position];
                System.out.println(fistPositiveNumber +" "+ temp);
                System.arraycopy(input,fistPositiveNumber,input,fistPositiveNumber+1,position-fistPositiveNumber);
                input[fistPositiveNumber] = temp;
                fistPositiveNumber++;
            }
            printArrays(input);
        }
        return input;
    }

- soar September 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static int[] reorderArray(int[] input) {
        if (input==null || input.length==0)
            return input;
        int fistPositiveNumber = -1;
        int temp = 0;
        for (int position = 0;position<input.length; position++) {
            if (input[position]>0 && fistPositiveNumber<0)
                fistPositiveNumber = position;
            if (input[position]<0 && fistPositiveNumber>=0) {
                temp = input[position];
                System.out.println(fistPositiveNumber +" "+ temp);
                System.arraycopy(input,fistPositiveNumber,input,fistPositiveNumber+1,position-fistPositiveNumber);
                input[fistPositiveNumber] = temp;
                fistPositiveNumber++;
            }
            printArrays(input);
        }
        return input;
    }

- soar September 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

n 0 1 2 3 4
value -1 1 3 -2 2

1. define boolean inProcess = false;

2. From 0 to n, if value(n) = negative, continue

else
inProcess = true;
tempA = n;

while(inProcess) {

if(value[n] = negative)
inProcess = false;

tempB = value(n+1)
shift value(n) from n to n+1

increase n until find a negative value (m).
}

value[tempA] = tempB;

{{
int[] array = {-1, 1, 3, 4, -2, 2};
boolean inProcess = false;
while(i<array.length) {
if(array[i] < 0) {
i++;
} else {
inProcess = true;
tempNo = i;
while(inProcess) {

if(tempB == null)
tempA = array[i];
else
tampA = tempB;
tempB = array[i+1];
if(array[i+1] < 0)
inProcess = false;

array[i+1] = tempA;
i++;
}
array[tempNo] = tempB;
}
}
}}

- Julie October 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

n 0 1 2 3 4
value -1 1 3 -2 2

1. define boolean inProcess = false;

2. From 0 to n, if value(n) = negative, continue

else
inProcess = true;
tempA = n;

while(inProcess) {

if(value[n] = negative)
inProcess = false;

tempB = value(n+1)
shift value(n) from n to n+1

increase n until find a negative value (m).
}

value[tempA] = tempB;

int[] array = {-1, 1, 3, 4, -2, 2};
boolean inProcess = false;
while(i<array.length) {
	if(array[i] < 0) {
	i++;
} else {
	inProcess = true;
	tempNo = i;
	while(inProcess) {

             if(tempB == null)
	           tempA = array[i];
             else
                   tampA = tempB;
                   tempB = array[i+1];
                   if(array[i+1] < 0) 
	                inProcess = false;

                   array[i+1] = tempA;
                   i++;
              }
             array[tempNo] = tempB;
       }
}

- Julie October 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] relSort3(int[] arr){
		
		int[] res=new int[arr.length];
		
		int lastExch=0;
		//sort negatives
		for(int i=0; i<res.length; i++){
			
			for(int j=lastExch; j<arr.length; j++ )
			if(arr[j]<0){
				res[i]=arr[j];
				lastExch=j+1;
				break;
			}
			
		}
		
		int lastExch2=arr.length-1;
		//sort positives
		for(int i=res.length-1; i>0; i--){
			
			for(int j=lastExch2; j>-1; j-- )
			if(arr[j]>0){
				res[i]=arr[j];
				lastExch2=j-1;
				break;
			}
			
		}
		
		return res;
		
	}

private static  void exch(int[] a, int i, int j) {
		   int swap = a[i];
		   a[i] = a[j];
		   a[j] = swap;
	}

- ATuring October 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't understand. Why not solving this problem in the simplest way? I think time is O(n) and space is O(l)
a=[-1 1 3 -2 2]
b=[]
c=[]
for _item in a:
{ if _item <0:}
{{ b.append(_item)}}
{ else:}
{{c.append(_item)}}
print b.extend(c)

- LFT1988 October 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I dont understand. Why not trying the simplest way? I think the time is O(n) and space is O(l)

a=[-1 1 3 -2 2]
b=[]
c=[]
for _item in a:
{if _item <0:}
{{b.append(_item)}}
{else:}
{{c.append(_item)}}
print b.extend(c)

- LFT1988 October 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class ReOrder:
     '''Give you 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 perfect. '''
     def __init__(self, items):
          self.items = items
     def prt(self):
          swap = True
          iLen = len(self.items)
          x = self.items #just make it easier for typing, one can directly use self.items for x
          if iLen < 2:
               print self.items
               return
          cnt = 0
          while swap:
               swap = False
               for i in range(iLen-1):
                    if x[i] > 0 and x[i+1] < 0:
                         x[i], x[i+1] = x[i+1], x[i]
                         swap = True
                         cnt += 1
          print (cnt, x)

- Frank Wang November 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] getMagicSort(int[] a){
    int firstNeg=0;
    for(int start=0; start < a.length; start++){
        while(firstNeg < a.lenght){
            if(a[firstNeg] < 0){
                break;
            }
            firstNeg++;
        }        
        percolate(a, start, firstNeg);
    }
}
        
    
private void percolate(int[] a, int sI, int eI){
    if(eI <= sT)
        return;
    int temp = a[eI-1];
    a[eI-1] = a[eI];
    a[eI] = temp;
    percolate(int a, sI, eI-1);
}

- tomahawk November 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

space complexity O(1), time complexity O(N)
It seems quite easy, I don't understand why it should be done in O(Nlog(N)).

#include <stdio.h>
#include <stdlib.h>
int main(){

	
	int* arr;
	int pn, pp;
	int nn = 0, np = 0;
	int i, N;

	scanf("%d", &N);
	if(N < 0)
		return 0; 

	arr = (int*)malloc(sizeof(int)*N);

	for(i=0; i<N; i++){
		scanf("%d", &arr[i]);
	}
 
	for(i=0; i<N; i++){
		if(arr[i] < 0)
			nn++;
	}

	pn = 0;
	pp = nn;
	int ppp = pp;
	while(1){
		while(arr[pn] < 0 && pn < ppp)
			pn++;
		while(arr[pp] >= 0 && pp < N)
			pp++;

		if(pn < ppp && pp < N){
			int p = arr[pn];
			arr[pn] = arr[pp];
			arr[pp] = p;
		}else
			break;
		pn++;
		pp++;
	}

	for(i=0; i<N; i++){
		printf("%d ", arr[i]);
	}
	printf("\n");

	return 0;
}

- gigilibala November 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void inplaceReplacePosNeg(int [] a , int start , int end){
int count = 0;
if(end-start<2){
return;
}
for(int i=start;i<end;i++){
if(a[i]<0)
count++;
}
if(start+count<end)
inplaceReplacePosNeg(a, start, start+count);
if(count>0)
inplaceReplacePosNeg(a, start+count, end);
int i=start;int j=start+count;

while(i<start+count){
if(a[i]<0){
i++;
continue;
}
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j++;
}

}

- Anonymous December 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void inplaceReplacePosNeg(int [] a , int start , int end){
		int count = 0;
		if(end-start<2){
			return;
		}
		for(int i=start;i<end;i++){
			if(a[i]<0)
				count++;
		}
		if(start+count<end)
			inplaceReplacePosNeg(a, start, start+count);
		if(count>0)
			inplaceReplacePosNeg(a, start+count, end);
		int i=start;int j=start+count;
		
		while(i<start+count){
			if(a[i]<0){
				i++;
				continue; 
			}
			int temp = a[i];
			a[i] = a[j];
			a[j] = temp;
			i++;
			j++;
		}
		
	}

- Anonymous December 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String args[]) {

        int a[] = {-1, 2, 3, -2, 4, -5};
        int temp[] = new int[a.length];
        int j = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i] < 0) {
                temp[j++] = a[i];
                a[i] = Integer.MAX_VALUE;

            }
        }
        for (int i = 0; i < a.length; i++) {
            if (a[i] >= 0 && a[i] != Integer.MAX_VALUE) {
                temp[j++] = a[i];
            }
        }
        for(int i = 0; i<a.length; i++){
            System.out.println(temp[i]);
        }

    }

- daljeet virdi December 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence

- Kaushik Sharma December 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence

- Kaushik Sharma December 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence

- Kaushik Sharma December 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence

- Kaushik Sharma December 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence

- Kaushik Sharma December 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence

- Kaushik Sharma December 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence

- Kaushik Sharma December 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence

- Kaushik Sharma December 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence

- Kaushik Sharma December 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence

- kaushikmtc December 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence

- kaushikmtc December 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and hence

- kaushikmtc December 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is very much possible in O(n) time and O(1) complexity. The idea is to see the array as contigous blocks of positive and negative arrays combined together. say array a = p1n1,p2n2,...pini , where pi represents all positives and ni all negatives. we need to first get the indices od begining of pi end of pi and end of ni say i,j and k . We now need to operate on pini to convert it to nipi and continue from pi . If we prove that to do so we are in O(nipi) the whole thing can be done in O(n). So the problem boils down to converting PN to NP in O(N+P) this is possible as we do Reverse(PN); Reverse(P),Reverse(N) and The code in c#

public  static void Segregrate(int[] a)
        {
            bool isPositiveBlock;
            //first rule out case of all positive or all -ve integers
            int j = getContigousBlock(a, 0, out isPositiveBlock);

            if((j==-1) || (j==a.Length-1) )
                return;

            int i = 0;

            if (!isPositiveBlock)
            {
                i = j + 1;
                j = getContigousBlock(a, i, out isPositiveBlock);
            }

            // Invariant:  i is the begining of the +ve block and j the end of the positive block and if we enter forsure there 
            //is a -ve block starting at j+1

            while(j<a.Length-1 && (j>=0))
            {
                
                int k = getContigousBlock(a, j+1, out isPositiveBlock); // k is the end of the negative block 
                if (isPositiveBlock) // invariant is broken something wrong with algo as we must get negative block 
                    throw new Exception("invariant is broken something wrong with algo as we must get negative block");

                MovePositivestoEndOfBlock(a, i, j, k);
                
                i = i+k-j;  // number of negative integers being k-j which are now shifted and starts from i+k-j and does not end at k but goes beyond
                j = getContigousBlock(a, k + 1, out isPositiveBlock);

                if (j!=-1 && !isPositiveBlock) // invariant is broken something wrong with algo we must get a positive block 
                    throw new Exception("invariant is broken something wrong with algo we must get a positive block ");
            }

}

- kaushikmtc December 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public  static void Segregrate(int[] a)
        {
            bool isPositiveBlock;
            //first rule out case of all positive or all -ve integers
            int j = getContigousBlock(a, 0, out isPositiveBlock);

            if((j==-1) || (j==a.Length-1) )
                return;

            int i = 0;

            if (!isPositiveBlock)
            {
                i = j + 1;
                j = getContigousBlock(a, i, out isPositiveBlock);
            }

            // Invariant:  i is the begining of the +ve block and j the end of the positive block and if we enter forsure there 
            //is a -ve block starting at j+1

            while(j<a.Length-1 && (j>=0))
            {
                
                int k = getContigousBlock(a, j+1, out isPositiveBlock); // k is the end of the negative block 
                if (isPositiveBlock) // invariant is broken something wrong with algo as we must get negative block 
                    throw new Exception("invariant is broken something wrong with algo as we must get negative block");

                MovePositivestoEndOfBlock(a, i, j, k);
                
                i = i+k-j;  // number of negative integers being k-j which are now shifted and starts from i+k-j and does not end at k but goes beyond
                j = getContigousBlock(a, k + 1, out isPositiveBlock);

                if (j!=-1 && !isPositiveBlock) // invariant is broken something wrong with algo we must get a positive block 
                    throw new Exception("invariant is broken something wrong with algo we must get a positive block ");
            }

}

- kaushikmtc December 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void Segregrate(int[] a)
{
bool isPositiveBlock;
//first rule out case of all positive or all -ve integers
int j = getContigousBlock(a, 0, out isPositiveBlock);

if((j==-1) || (j==a.Length-1) )
return;

int i = 0;

if (!isPositiveBlock)
{
i = j + 1;
j = getContigousBlock(a, i, out isPositiveBlock);
}

// Invariant: i is the begining of the +ve block and j the end of the positive block and if we enter forsure there
//is a -ve block starting at j+1

while(j<a.Length-1 && (j>=0))
{

int k = getContigousBlock(a, j+1, out isPositiveBlock); // k is the end of the negative block
if (isPositiveBlock) // invariant is broken something wrong with algo as we must get negative block
throw new Exception("invariant is broken something wrong with algo as we must get negative block");

MovePositivestoEndOfBlock(a, i, j, k);

i = i+k-j; // number of negative integers being k-j which are now shifted and starts from i+k-j and does not end at k but goes beyond
j = getContigousBlock(a, k + 1, out isPositiveBlock);

if (j!=-1 && !isPositiveBlock) // invariant is broken something wrong with algo we must get a positive block
throw new Exception("invariant is broken something wrong with algo we must get a positive block ");
}

}

- kaushikmtc December 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public  static void Segregrate(int[] a)
        {
            bool isPositiveBlock;
            //first rule out case of all positive or all -ve integers
            int j = getContigousBlock(a, 0, out isPositiveBlock);

            if((j==-1) || (j==a.Length-1) )
                return;

            int i = 0;

            if (!isPositiveBlock)
            {
                i = j + 1;
                j = getContigousBlock(a, i, out isPositiveBlock);
            }

            // Invariant:  i is the begining of the +ve block and j the end of the positive block and if we enter forsure there 
            //is a -ve block starting at j+1

            while(j<a.Length-1 && (j>=0))
            {
                
                int k = getContigousBlock(a, j+1, out isPositiveBlock); // k is the end of the negative block 
                if (isPositiveBlock) // invariant is broken something wrong with algo as we must get negative block 
                    throw new Exception("invariant is broken something wrong with algo as we must get negative block");

                MovePositivestoEndOfBlock(a, i, j, k);
                
                i = i+k-j;  // number of negative integers being k-j which are now shifted and starts from i+k-j and does not end at k but goes beyond
                j = getContigousBlock(a, k + 1, out isPositiveBlock);

                if (j!=-1 && !isPositiveBlock) // invariant is broken something wrong with algo we must get a positive block 
                    throw new Exception("invariant is broken something wrong with algo we must get a positive block ");
            }

}

- kaushikmtc December 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public  static void Segregrate(int[] a)
        {
            bool isPositiveBlock;
            //first rule out case of all positive or all -ve integers
            int j = getContigousBlock(a, 0, out isPositiveBlock);

            if((j==-1) || (j==a.Length-1) )
                return;

            int i = 0;

            if (!isPositiveBlock)
            {
                i = j + 1;
                j = getContigousBlock(a, i, out isPositiveBlock);
            }

            // Invariant:  i is the begining of the +ve block and j the end of the positive block and if we enter forsure there 
            //is a -ve block starting at j+1

            while(j<a.Length-1 && (j>=0))
            {
                
                int k = getContigousBlock(a, j+1, out isPositiveBlock); // k is the end of the negative block 
                if (isPositiveBlock) // invariant is broken something wrong with algo as we must get negative block 
                    throw new Exception("invariant is broken something wrong with algo as we must get negative block");

                MovePositivestoEndOfBlock(a, i, j, k);
                
                i = i+k-j;  // number of negative integers being k-j which are now shifted and starts from i+k-j and does not end at k but goes beyond
                j = getContigousBlock(a, k + 1, out isPositiveBlock);

                if (j!=-1 && !isPositiveBlock) // invariant is broken something wrong with algo we must get a positive block 
                    throw new Exception("invariant is broken something wrong with algo we must get a positive block ");
            }

        }
        //Starting from startIndex returns the index till which the sign of integers has not changed , sets out isPositive to true is numbers >=0 and false
        // if numbers are < 0
        private static int getContigousBlock(int[] a, int startIndex, out bool isPositive)
        {
            isPositive = false;
            comparisons = comparisons + 4;
            if (a==null || a.Length==0 ||  startIndex < 0 || startIndex > a.Length - 1)
                return -1;

            isPositive = (a[startIndex] >= 0);

            comparisons++; // complexity analysis variable 
            int i = startIndex;
            comparisons++;
            if (isPositive)
            {
                comparisons++;
                while (i < a.Length && a[i] >= 0 )
                {
                    i++;
                    comparisons= comparisons +2;
                }
                return i - 1;
            }
            else
            {
                comparisons++;
                while (i < a.Length && a[i] < 0)
                {
                    i++;
                    comparisons = comparisons + 2;
                }
                return i - 1;
            }
        }
        //Input is an array of non negative integers followed by -ve integers
        // Out put is array of -ve integers followed by positive integers. relative position of the -ve and non negative integers
        //amongst them remains the same

        // Algo Array A= PN where P is positive N is -ve
        //Reverse A we get N-reversed + P-Reversed
        // Now reverse N-Reversed and P-Reversed , so essentially O (n)
        public static void MovePositivestoEndOfBlock(int[] a, int pFirst, int pEnd, int nEnd )
        {
            Reverse(a, pFirst, nEnd);
            Reverse (a, pFirst, pFirst + nEnd-pEnd-1);
            Reverse (a, pFirst+ nEnd-pEnd , nEnd);
        }
        public static void Reverse(int[]a, int startIndex, int endIndex)
        {
            comparisons = comparisons + 3;
            if((a==null) || (a.Length==0) || (a.Length==1))
                return;

            comparisons++; 
             for(int i=startIndex,j=endIndex; i<j; i++, j--)
             {
                 int temp = a[i];
                 a[i] = a[j];
                 a[j] = temp;
                 assignments = assignments + 3;
                 comparisons++;
             }

        }

- kaushikmtc December 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) time, O(1) space

import java.util.*;
class NegativePositiveSort {
        private static void sort(int[] data) {
                int i = 0;
                while(i < data.length) {
                        if(data[i] > 0) {
                                int j = i;
                                while(j < data.length && data[j] > 0) {
                                        j++;
                                }
                                if(j < data.length) {
                                        int neg = data[j];
                                        for(; j > i; j--) {
                                                data[j] = data[j - 1];
                                        }
                                        data[i] = neg;
                                }
                                i = j;
                        } else {
                                i++;
                        }
                }
        }
        public static void main(String... args) {
                //int[] data = new int[] {-1, 1, 3, -2, 2};
                //int[] data = new int[]{1, 2, 3, 4, 5, -5, -4, -3, -2, -1};
                int[] data = new int[] {1, -1, 2, -2};
                sort(data);
                System.out.println(Arrays.toString(data));
        }
}

- Anonymous January 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;

public class sort {
public static void main(String[] args){
sort instance = new sort();
int[] m = {-2, 6, 4, 5,-6, 9, -1};
System.out.println(Arrays.toString(instance.sortArray(m)));

}

public int[] sortArray(int[] array){
int n = array.length;
int[] result = new int[n];
int count = 0;

for(int i = 0; i < n; i++){
if(array[i] < 0){
result[count] = array[i];
count = count + 1;
}
}

for(int j = 0; j < n; j++){
if(array[j] > 0){
result[count] = array[j];
count = count + 1;
}
}



return result;

}
}

- suncyycs January 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Find min in vector which will be O(n) and the using min as pivot do stable_sort?

int minPositive(vector<int> v) {
  int minP = std::numeric_limits<int>::max();
  for(int i: v) {
    if(i > 0) {
      if(i < minP)
        minP = i;
    }
  }
  return minP;
}

// O(1) space
void sort_1(vector<int> &v) {
  vector<int>::iterator _min = min_element(v.begin(), v.end());
  int min_value = 0;
  min_value = minPositive(v);
  stable_sort(v.begin(), v.end(), [min_value](int i, int j) {return i < min_value;});
  print_vector(v);
}

- tenumm February 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int minPositive(vector<int> v) {
  int minP = std::numeric_limits<int>::max();
  for(int i: v) {
    if(i > 0) {
      if(i < minP)
        minP = i;
    }
  }
  return minP;
}

void sort_1(vector<int> &v) {
  vector<int>::iterator _min = min_element(v.begin(), v.end());
  int min_value = 0;
  min_value = minPositive(v);
  stable_sort(v.begin(), v.end(), [min_value](int i, int j) {return i < min_value;});
  print_vector(v);
}

- tenumm February 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Does this fit the bill?

def sort_array(arr)
  counter = 0
  arr.length.times do
    val = arr[counter]
    if val >= 0
      arr.delete_at(counter)
      arr.push(val)
    else
      counter += 1
    end
  end
  return arr
end

Solution is in Ruby, sorry. I must be missing something?

- Liam June 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be solved with a variation on pivot of 0 (from quicksort).
Some solutions here tried to go that way but they do not keep relative position. In order to do that, we need a little bit more info.

1. Scan the array and count positive numbers (O(n))
2. Start with two pointers- one at the start and one in position (arrayLength - numOfPositives).
3. As long as the first pointer points to a positive number, swap elements and increment second pointer.
4. If first points to negative number, increment first pointer.

This works because instead of going backwards you swap the positive integers in order.

This allows us to pivot without losing order. Unless I am missing something, this is O(n) time and O(1) space.

public void pivotWithOrder(int[] arr) {
	int posIndex = arr.length - getNumOfPositives();
	if (posIndex == 0 || posIndex == arr.length) 
		return;
	int origPosIndex = posIndex;
	int negIndex = 0;
	while (negIndex < origPosIndex) {
		if (arr[negIndex] < 0) {
			swap(arr, negIndex, posIndex);
			posIndex++;
		}
		else negIndex++;
	}
}

- streamer July 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) time O(1) space Ruby solution

def strangesort(array)
  array.each.with_index do |num, pos|
    if num > 0
      any = swap_next_negative(array, pos)
      return array unless any
    end
  end
end

def swap_next_negative(array, pos)
  array[pos+1 .. -1].each.with_index do |num, i|
    index = i + pos + 1
    if num < 0
      while index > pos
        array[index] = array[index -= 1]
      end
      array[pos] = num
      return true
    end
  end

  false
end

- fl00r August 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

in python

input = [ -1, 1, 3, -2, 2]

output = [0] * len(input)
negatives = 0
for t in input:
    if t < 0:
        negatives += 1

negativeIndex = 0
positiveIndex = negatives
for t in input:
    if t < 0:
        output[negativeIndex] = t
        negativeIndex += 1
    else:
        output[positiveIndex] = t
        positiveIndex += 1

print(output)

- om471987 September 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python code

input = [ -1, 1, 3, -2, 2]

n = len(input)
output = [0] * n

negativeIndex = 0
positiveIndex = n - 1

for i, t in enumerate(input):
    if input[i] < 0:
        output[negativeIndex] = input[i]
        negativeIndex += 1
    if input[n - 1 - i] > 0:
        output[positiveIndex] = input[n - 1 - i]
        positiveIndex -= 1

print(output)

- om471987 September 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

time: o(n)
memory: o(1)

//
//  LinkedList.m
//  AlgorythmsPlayground
//
//  Created by Kirill Kirikov on 29.09.15.
//  Copyright © 2015 Seductive. All rights reserved.
//

#import "SortingLinkedList.h"

@interface Node : NSObject
@property (nonatomic, strong) Node *next;
@property (nonatomic, assign) int value;
- (instancetype) initWithValue:(int)value;
@end

@implementation Node
- (instancetype) initWithValue:(int)value {
    self = [super init];
    if (self) {
        self.value = value;
    }
    return self;
}
@end

@interface SortingLinkedList()
@property (nonatomic, strong) Node *negative;
@property (nonatomic, strong) Node *positive;
@property (nonatomic, strong) Node *head;
@end

@implementation SortingLinkedList

- (void) insert:(int) elem {
    Node *node = [[Node alloc] initWithValue:elem];
    
    if (elem <= 0) {
        [self insertNegative:node];
    } else {
        [self insertPositive:node];
    }
}

- (void) insertNegative:(Node *)node {
    if (!self.negative) {
        if (self.head) {
            node.next = self.head;
        }
        self.head = node;
    } else {
        node.next = self.negative.next;
        self.negative.next = node;
    }
    
    self.negative = node;
}

- (void) insertPositive:(Node *)node {
    
    if (!self.head) {
        self.head = node;
    } else if (self.positive) {
        self.positive.next = node;
    } else {
        self.negative.next = node;
    }
    
    self.positive = node;
}

- (void) print {
    Node *iterator = self.head;
    while (iterator) {
        NSLog(@"%d", iterator.value);
        iterator = iterator.next;
    }
}

@end

- Kirill Kirikov September 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time: o(n)
Memory: o(1);

//
//  LinkedList.m
//  AlgorythmsPlayground
//
//  Created by Kirill Kirikov on 29.09.15.
//  Copyright © 2015 Seductive. All rights reserved.
//

#import "SortingLinkedList.h"

@interface Node : NSObject
@property (nonatomic, strong) Node *next;
@property (nonatomic, assign) int value;
- (instancetype) initWithValue:(int)value;
@end

@implementation Node
- (instancetype) initWithValue:(int)value {
    self = [super init];
    if (self) {
        self.value = value;
    }
    return self;
}
@end

@interface SortingLinkedList()
@property (nonatomic, strong) Node *negative;
@property (nonatomic, strong) Node *positive;
@property (nonatomic, strong) Node *head;
@end

@implementation SortingLinkedList

- (void) insert:(int) elem {
    Node *node = [[Node alloc] initWithValue:elem];
    
    if (elem <= 0) {
        [self insertNegative:node];
    } else {
        [self insertPositive:node];
    }
}

- (void) insertNegative:(Node *)node {
    if (!self.negative) {
        if (self.head) {
            node.next = self.head;
        }
        self.head = node;
    } else {
        node.next = self.negative.next;
        self.negative.next = node;
    }
    
    self.negative = node;
}

- (void) insertPositive:(Node *)node {
    
    if (!self.head) {
        self.head = node;
    } else if (self.positive) {
        self.positive.next = node;
    } else {
        self.negative.next = node;
    }
    
    self.positive = node;
}

- (void) print {
    Node *iterator = self.head;
    while (iterator) {
        NSLog(@"%d", iterator.value);
        iterator = iterator.next;
    }
}

@end

- Kirill September 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time: o(n)
Memory: o(1);

//
//  LinkedList.m
//  AlgorythmsPlayground
//
//  Created by Kirill Kirikov on 29.09.15.
//  Copyright © 2015 Seductive. All rights reserved.
//

#import "SortingLinkedList.h"

@interface Node : NSObject
@property (nonatomic, strong) Node *next;
@property (nonatomic, assign) int value;
- (instancetype) initWithValue:(int)value;
@end

@implementation Node
- (instancetype) initWithValue:(int)value {
    self = [super init];
    if (self) {
        self.value = value;
    }
    return self;
}
@end

@interface SortingLinkedList()
@property (nonatomic, strong) Node *negative;
@property (nonatomic, strong) Node *positive;
@property (nonatomic, strong) Node *head;
@end

@implementation SortingLinkedList

- (void) insert:(int) elem {
    Node *node = [[Node alloc] initWithValue:elem];
    
    if (elem <= 0) {
        [self insertNegative:node];
    } else {
        [self insertPositive:node];
    }
}

- (void) insertNegative:(Node *)node {
    if (!self.negative) {
        if (self.head) {
            node.next = self.head;
        }
        self.head = node;
    } else {
        node.next = self.negative.next;
        self.negative.next = node;
    }
    
    self.negative = node;
}

- (void) insertPositive:(Node *)node {
    
    if (!self.head) {
        self.head = node;
    } else if (self.positive) {
        self.positive.next = node;
    } else {
        self.negative.next = node;
    }
    
    self.positive = node;
}

- (void) print {
    Node *iterator = self.head;
    while (iterator) {
        NSLog(@"%d", iterator.value);
        iterator = iterator.next;
    }
}

@end

- olmer.k September 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
We can use some data structure which protects the order like LinkedList.

Here I am marking all negatives with 1 and positives with 2 and corresponding to that I am maintaining a linkedlist which we can print at end.

Basically Map one linkedlist to 1 i.e. the mark for negatives and
one with 2 i.e. the mark for positives now print them separately preventing their relative order

*/

import java.util.*;

public class test{
        public static void main(String[] args){
                LinkedHashMap<Integer,LinkedList<Integer>> m = new LinkedHashMap<Integer,LinkedList<Integer>>();

                int a[] = {-1,1,2,-3,2};
                for(int i = 0; i< a.length; i++){

                        if(a[i] < 0){
                                if(!m.containsKey(1)){
                                        LinkedList<Integer>  temp = new LinkedList<Integer>();
                                        temp.add(a[i]);
                                        m.put(1,temp);
                                }else{
                                        m.get(1).add(a[i]);
                                }
                        }else{
                                if(!m.containsKey(2)){
                                       LinkedList<Integer>  temp = new LinkedList<Integer>();
                                       temp.add(a[i]);
                                       m.put(2,temp);
                                }else{
                                        m.get(2).add(a[i]);
                                }
                        }
                }

                LinkedList<Integer> l = m.get(1);
                Iterator i = l.iterator();
                while(i.hasNext()){
                        System.out.print(i.next()+" ");
                }
                l = m.get(2);
                i = l.iterator();
                while(i.hasNext()){
                        System.out.print(i.next()+" ");
                }
        }
}

- lordzuko October 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this is just about the most readable solution (in Java):

public static int[] signSort(int[] input) {
    int[] ans = new int[input.length];
    int index = 0;
    for(int i = 0; i < input.length; i++) {
      if(input[i] < 0) {
        ans[index++] = input[i];
      }
    }
    for(int i = 0; i < input.length; i++) {
      if(input[i] > 0) {
        ans[index++] = input[i];
      }
    }

    return ans;
  }

It's O(n) runtime, O(n) space, so not ideal.

- ddavidson621 October 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n), O(n) solution:

public static void reorder(int[] array){
        int totalNegativ=0;
        for(int i=0; i < array.length; i++){
            if(array[i] < 0)
                totalNegativ++;
        }

        int[] positions = new int[array.length];

        int negativLeft = totalNegativ;
        int positivMeet = 0;
        for(int i=0; i < array.length; i++){
            if(array[i] < 0){
                positions[i] = i - positivMeet;
                negativLeft--;
            }else{
                positions[i] = i + negativLeft;
                positivMeet++;
            }
        }

        for(int i=0; i<array.length; i++){
            while(positions[i]!=i){
                swap(array, positions, i, positions[i]);
            }
        }
    }

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

- Maxim October 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;


 int main()
 {
 	
 	vector<int> vc;
 	vector<int> vc1;
 	vector<int> vc2;
 	int n,i,x;
 	
 	 cin>>n;
 	  for(i=0;i<n;i++)
 	  {
 	  	cin>>x;
 	  	vc.push_back(x);
 	  }
 	
 	   for(i=0;i<vc.size();i++)
 	   {
 	   	if(vc[i]<0)
 	   	{
 	   		vc1.push_back(vc[i]);
 	   	}
 	   	else
 	   	{
 	   		vc2.push_back(vc[i]);
 	   	}
 	   }
 	   
 	   vc.clear();
 	   
 	   for(i=0;i<vc1.size();i++)
 	   {
 	   	vc.push_back(vc1[i]);
 	   }
 	   
 	   for(i=0;i<vc2.size();i++)
 	   {
 	   	vc.push_back(vc2[i]);
 	   }
 	   
 	 
 	  
 	  for(i=0;i<vc.size();i++)
 	  {
 	  	cout<<vc[i]<<"  ";
 	  }

}

- Anonymous November 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;


 int main()
 {
 	
 	vector<int> vc;
 	vector<int> vc1;
 	vector<int> vc2;
 	int n,i,x;
 	
 	 cin>>n;
 	  for(i=0;i<n;i++)
 	  {
 	  	cin>>x;
 	  	vc.push_back(x);
 	  }
 	
 	   for(i=0;i<vc.size();i++)
 	   {
 	   	if(vc[i]<0)
 	   	{
 	   		vc1.push_back(vc[i]);
 	   	}
 	   	else
 	   	{
 	   		vc2.push_back(vc[i]);
 	   	}
 	   }
 	   
 	   vc.clear();
 	   
 	   for(i=0;i<vc1.size();i++)
 	   {
 	   	vc.push_back(vc1[i]);
 	   }
 	   
 	   for(i=0;i<vc2.size();i++)
 	   {
 	   	vc.push_back(vc2[i]);
 	   }
 	   
 	 
 	  
 	  for(i=0;i<vc.size();i++)
 	  {
 	  	cout<<vc[i]<<"  ";
 	  }

}

- @bp singh November 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time O(n), space O(1)
C code:

void sort(int *a, int size)
{
int pivot = 0, runner = 0;
while (runner < size)
{
if (a[runner] < 0)
{
swap (a[runner], a[pivot]);
pivot++;
}

runner++;
}
}

- m.mirzamo December 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ain't working !!!!
Worked for negative numbers but relative position of positive numbers are changed.

- falconkumarcpp December 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

**It can be done in O(n) and space O(1).**

we need to scan 3 times through the array and change some values carefully.

Assumption: the max value in the array with size N is should be smaller than (N+1) * Interger.MAX_VALUE.

We need this assumption since we well change some positive values in the array.

- in the first scan, find # of negative and positive values, and the max.
- in the second scan we create the negative section of array as follows:

we start from the beginging of the array and we "**swap**" the first found positive number (e.g. at index i) with the first found negative number (e.g. j). since negative number are being considered with respect to their location, the swap will be okay. the problem is the positive numbers because there might be some other positive numbers between i and j. To handle this issue, we have to somehow encode the index of the positive number in that value before swaping. so then we can realize where it was at the first point. we can do this by a[i]=(i+1)*(max)+a[i].

- in the third scan, we create the positive section of array. by end of the second scan, the negative array is constructed, and the positive numbers are shifted to the right side, but their location may not be correct. So we go though it and correct their position since this info was encoded their value.

Here is the code:

import java.util.Arrays;

public class LinearShifting {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] a = {-1,7,3,-5,4,-3,1,2};
		sort(a);
		System.out.println(Arrays.toString(a));  //output: [-1, -5, -3, 7, 3, 4, 1, 2]
	}
	public static void sort(int[] a){
		int pos = 0;
		int neg = 0;
		int i,j;
		int max = Integer.MIN_VALUE;
		for(i=0; i<a.length; i++){
			if(a[i]<0) neg++;
			else pos++;
			if(a[i]>max) max = a[i];
		}
		max++;
		if(neg==0 || pos == 0) return;//already sorted
		i=0;
		j=1;
		while(true){
			while(i<=neg && a[i]<0) i++;
			while(j<a.length && a[j]>=0) j++;
			if(i>neg || j>=a.length) break;
			a[i]+= max*(i+1);
			swap(a,i,j);
		}
		
		i = a.length-1;
		while(i>=neg){
			int div = a[i]/max;
			if(div == 0) i--;
			else{
				a[i]%=max;
				swap(a,i,neg+div-2);// minus 2 since a[i]+= max*(i+1);
			}
		}
		
	}
	private static void swap(int[] a, int i , int j){
		int t = a[i];
		a[i] = a[j];
		a[j] = t;
	}

}

- mehraz December 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function negativeSort(array) {
	var nextIndex = 0
	var sortedArray = []
	
	for(var i = 0; i < array.length; i++) {
		var item = array[i]
		
		if(item < 0)
			sortedArray.splice(nextIndex++, 0, item)
		else
			sortedArray.push(item)
	}
	
	console.log(sortedArray)
}

negativeSort([-1,1,3,-2,2,-4,10,-8,0])

- Brian Vallelunga April 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function negativeSort(array) {
	var nextIndex = 0
	var sortedArray = []
	
	for(var i = 0; i < array.length; i++) {
		var item = array[i]
		
		if(item < 0)
			sortedArray.splice(nextIndex++, 0, item)
		else
			sortedArray.push(item)
	}
	
	console.log(sortedArray)
}

negativeSort([-1,1,3,-2,2,-4,10,-8,0])

- Brian Vallelunga April 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Seriously, this is super simple for O(n) time and constant space

public List<Integer> signSort(List<Integer> input) {
	List<Integer> negatives = new ArrayList<>();
	List<Integer> zeros = new ArrayList<>();
	List<Integer> positives = new ArrayList<>();

	for(Integer n : input) {
		if(n<0)
			negatives.add(n);
		else if(n==0)
			zeros.add(n);
		else
			positives.add(n);
	}

	List<Integer> sorted = new ArrayList<>();
	sorted.addAll(negatives);
	sorted.addAll(zeros);
	sorted.addAll(positives);
	return sorted;
}

- CosmicMJ June 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

= [-1, 1, 3, -2, 2]
k = 1000
p = 0
mark = []
mark2 = []
for i in d:
    if(i < 0):
        mark2.append(i)
    else:
        mark.append(i)


for m in mark2:
    d[p] = m
    p = p + 1

n=p
for f in mark  :
   d[n] = f
   n = n + 1

for m in d:
    print m

- Anonymous August 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

= [-1, 1, 3, -2, 2]
k = 1000
p = 0
mark = []
mark2 = []
for i in d:
if(i < 0):
mark2.append(i)
else:
mark.append(i)


for m in mark2:
d[p] = m
p = p + 1

n=p
for f in mark :
d[n] = f
n = n + 1

for m in d:
print m

- Anonymous August 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

= [-1, 1, 3, -2, 2]
k = 1000
p = 0
mark = []
mark2 = []
for i in d:
if(i < 0):
mark2.append(i)
else:
mark.append(i)


for m in mark2:
d[p] = m
p = p + 1

n=p
for f in mark :
d[n] = f
n = n + 1

for m in d:
print m

- shashi jey August 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<html>
<body>
<main>
Here is my code with hack:
<pre>
d = [-1, 1, 3, -2, 2]
k = 1000
p = 0
mark = []
mark2 = []
for i in d:
if(i < 0):
mark2.append(i)
else:
mark.append(i)


for m in mark2:
d[p] = m
p = p + 1

n=p
for f in mark :
d[n] = f
n = n + 1

for m in d:
print m




</pre>


</main>
<body>
</html>

- shashi jey August 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

easy to make a sort using code similar to quick sorts but no need to recursively partition. O(n) time O(1) space:

#include <stdio.h>

#define SIZEOF_ARRAY( arr ) sizeof( arr ) / sizeof( arr[0] )

void sort(int nums[], int n) {
    int i = 0, j = n - 1;

    while (i < j) {
        while (nums[i] < 0) {
            i++;
        }

        while (nums[j] > 0) {
            j--;
        }

        if (i < j) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }

    }
}

void printArr (int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main (void) {
    int arr[] = {4,8,2,1,3,-6,-4,7,-8,-9,-10};
    printArr(arr,SIZEOF_ARRAY(arr));
    sort(arr,SIZEOF_ARRAY(arr));
    printArr(arr,SIZEOF_ARRAY(arr));
    return 0;
}

- sortman August 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void sort(int nums[], int n) {
    int i = 0, j = n - 1;

    while (i < j) {
        while (nums[i] < 0) {
            i++;
        }

        while (nums[j] > 0) {
            j--;
        }

        if (i < j) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }

    }
}

- Anonymous August 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void sort(int nums[], int n) {
    int i = 0, j = n - 1;

    while (i < j) {
        while (nums[i] < 0) {
            i++;
        }

        while (nums[j] > 0) {
            j--;
        }

        if (i < j) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }

    }

}

- sortman August 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution is to iterate over the list once. First make a temp copy of the list and then iterate over the list. While iterating, if the number is negative then pop it out of the temp list and then add it back to the end of temp list. For the positive numbers, do the opposite which is to pop the number out from the temp list and then add it to the front of the temp list, which also a reverse order for the positive numbers. Keep track of count for positive numbers, so you can slice the final temp list into positive and negative lists. Now, you just need to reverse the positive list and append the two lists into a single list as a return value.

[-1,1,3,-2,2]

After iterating over the original list
[2,3,1,-1,-2]

After slicing by positive-integer count
[2,3,1] [-1,-2]

After reversing positive list
[1,3,2] [-1,-2]

Return
[-1,-2,1,3,2]

#!bash/bin/python

def reorderList(num_ary):
    
    temp = num_ary[:]
    count = 0
    
    for i in num_ary:
        temp.pop(i)
        if i < 0:
            temp.append(i)
        else:
            temp.insert(0,i)
            count += 1
            
    return temp[count:len(temp)] + temp[0:count][::-1]
    

print reorderList([-1,1,3,-2,2])

[-1, -2, 1, 3, 2]

- Zorigt.Baz August 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def sort(l):

	'''Question doesn't specify how to deal with zeros (positive values or should they be
		in the middle?). This implementation puts them in the middle. 

	Algorithm is O(n) time, O(1) space.
	'''

	index = 0
	zeros = 0
	for _ in range(len(l)):

		## since we want negatives on the left,
		## leave an entry alone if it's negative
		if l[index] < 0:
			index += 1
			continue

		## if the entry is positive,
		## move it to the end but keep
		## index the same.
		if l[index] > 0:
			l += [l.pop(index)]
			continue

		## Finally, if l[index] is zero
		## increase the number of zeros to be
		## added after and pop zero
		if l[index] == 0:
			l.pop(index)
			zeros += 1
			continue

	return l[:index]+[0]*zeros+l[index:]

- nick September 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

could you teach me what is the time complexity and space complexity below code?

import unittest

def rearrange(array):
	# max  = len(array)
	p = 0
	for i in range(0, len(array)):
		cur = array[p]
		if cur >= 0:
			array.append(cur)
			del array[p]	
		else:
			p += 1
	return array
	
class Test(unittest.TestCase):
	def test(self):
		self.assertEqual(rearrange([-1, 1, 3, -2, 2]), [-1, -2, 1, 3, 2])
		self.assertEqual(rearrange([1, -3, 4, 2, -4, 5]), [-3, -4, 1, 4, 2, 5])
		self.assertEqual(rearrange([1, -3, 4, 2, -4, 0]), [-3, -4, 1, 4, 2, 0])
		self.assertEqual(rearrange([1, -3, 4, 0, 2, -4]), [-3, -4, 1, 4, 0, 2])

if __name__ == "__main__":
	unittest.main()

- youngtip February 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>

#include<algorithm>

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;

}

- harrypotter0 September 19, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have an O(n^2) solution, but I think it's easy to understand.

public void rearrangeArray2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int firstNegative = 0;
        int q = 0;
        while (firstNegative < nums.length && nums[firstNegative] > 0) {
                firstNegative++;
        }
        q = firstNegative;
        while (q < nums.length) {
            while (nums[q] < 0) {
                q++;
            }
            if (q == nums.length) {
                break;
            }
            for (int i = q; i > firstNegative; i--) {
                int tmp = nums[i - 1];
                nums[i - 1] = nums[i];
                nums[i] = tmp;
            }
            firstNegative++;
            q++;
        }

}

- Sherry January 17, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
public class check {
	private static final int[] arr = { 100, -1, 5, 4, -7, 11, 12, 0, -2, -1, -10, 11, -2 };
	public static void main(String[] args){
		int c = 0;
		int[] pos = new int[arr.length]; 
		for(int i=0;i<arr.length;i++) {
			if(arr[i]<0) {
				pos[c] = i;
				c++;
			}
		}
		for(int j=0;j<arr.length;j++) {
			if(arr[j]>=0) {
				pos[c] = j;
				c++;
			}
		}
		for(int k=0;k<arr.length;k++) {
			System.out.println(arr[pos[k]]);
		}
		
}
}

- f2015238@pilani.bits-pilani.ac.in February 07, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def pos_neg_sort(array)
	neg = []
	pos = []
	
	array.each{|n| n < 0 ? neg.push(n) : pos.push(n)}

	return neg + pos
end

- jesuskwice February 19, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What about this one?

def sep_neg_pos(arr):
    neg=0
    pos = len(arr) - 1
    for i in range(int(len(arr)/2) + 1):
        if neg >= pos:
            break;
        if arr[i] < 0:
            swap(arr, neg,i)
            neg+= 1
        if arr[len(arr)-1-i] >= 0:
            swap(arr, pos, len(arr)-1-i)
            pos -=1
    return arr

- JustACoder June 16, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def neg_pos(A):
neg = []
pos = []
for value in A:
if value < 0:
neg.append(value)
else:
pos.append(value)
return neg + pos

- Anonymous August 23, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

(((def neg_pos(A):
neg = []
pos = []
for value in A:
if value < 0:
neg.append(value)
else:
pos.append(value)
return neg + pos)))

- Anonymous August 23, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I hope it will work :

//let arr = [-1,1,3,-2,2];
let arr = [-5,1,3,7,-4,-2,9,2]
let resulr = [...arr];
let neg = []
arr.find((item) =>{
if(item <0){
neg.push(item);
}
})
resulr.unshift(...neg)
console.log(resulr)
let final = [...new Set([...resulr])];
console.log(final)

- ganrath07 January 13, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

array = [-1, 1, 3, -2, 2]

if __name__ == '__main__':
	first_positive_number_index = -1
	last_number_was_positive = False

	for i in range(len(array)):
		if (array[i] < 0):
			if (first_positive_number_index >= 0):
				temp = array[i]
				for j in range(i, first_positive_number_index - 1, -1):
					array[j] = array[j - 1]
				array[first_positive_number_index] = temp
		elif (array[i] == 0):
			raise Exception("Unexpected input")
		elif (not last_number_was_positive):
			first_positive_number_index = i
			last_number_was_positive = True

	print(array)

- Özgür Macit October 30, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

func sequentionalNumbers() -> [Int] {
let input = [-1, 1, 3, -2, 2]
var finalOutput = [Int]()
var subOutput2 = [Int]()
for num in input {
if num < 0 {
finalOutput.append(num)
}
else {
subOutput2.append(num)
}
}
return finalOutput + subOutput2
}

- Algorithm Analyst September 26, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I believe this to be O(n) runtime (scans the entire array 2 times) while also being O(1) memory (swaps in-place with only a few 'placeholder' variables and counters).

function arrSpecialSort2() {
  let arr1 = [-1,1,3,-2,2,10,-9,-4,4,5];

  let negCount = 0;

  arr1.forEach(x => {
    if(x < 0) 
      negCount++;
  });

  // Escape early if no negatives
  if(negCount === 0)
    return;

  let i = 0;
  let j = i+1;

  console.log(`Arr NegCount - ${negCount} || i - ${i}`, arr1);
  while(i < negCount) {
    
    // If negative - continue to next element
    if(arr1[i] < 0) {
      i++;
    }

    // If positive - handle finding next positive above 'negCount' barrier then swap 
    else {
      // console.log(`Arr - ${arr1.length} NegCount - ${negCount} || i - ${i}`, arr1);
      while(arr1[j] > 0) {
        j++;
      }
      let tmp = arr1[i];
      arr1[i] = arr1[j];
      arr1[j] = tmp; 
      j++;
      i++;
    }
  }

  console.log(arr1);
}

- masterjaso June 10, 2022 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include<stdio.h>
main()
{
int n;
scanf("%d",&n);
int a[n],b[n];
int i=0;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
int k=0;
for(i=0;i<n;i++)
{
if(a[i]<0)
{
b[k]=a[i];k=k+1;
}
else
{k=k;}
}


for(i=0;i<n;i++)
{
if(a[i]>0){b[k]=a[i];k++;}else{k=k;}
}

for(i=0;i<k;i++)
{
printf(" %d",b[i]);
}
}

- A.Nasimunni August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public int[] sortInOrder(int[] data){
		
		int pos=0;
		int negPos=0;
		for (pos=0;pos<data.length;) {
			
			if(data[pos]>=0){
				while(negPos<data.length && data[negPos]>=0  ){
					negPos++;
				}
				
				if(negPos==data.length)
					break;
				while(negPos>pos){
					int temp=data[negPos];
					data[negPos]=data[negPos-1];
					data[negPos-1] = temp;
					negPos--;
				}
			}
				negPos++;
				pos++;
			
		}
		
		return data;
	}

- avinash jha August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

how can you preserve the relative position???????????

- gzgujs September 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

It cannot be done in O(n) . If it can done in O(n), then lower bound for comparision based sorting is O(n) which is false. So, the order is O(nlogn) and space is O(1)

void sort(vector<int>& a)
{
   int n = a.size();
   int i = 0 ;
   while (i < n && a[i]  < 0) i++;
   while (i < n)
   {
         int j = i;
         while (j < n && a[j] > 0) j++;
         int k = j;
         while (k < n && a[k] < 0) k++;
         if (k < n) {
                 rev(a, i, j-1);
                 rev(a, j, k-1);
                 rev(a, i, k-1);
         }
         i = i + (k-j); 
   }
}

- Anonymous September 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include <iostream>
#include <iostream>
using namespace std;

int arr[] = {1,2,-1,1,3,-2,2};

void reverse(int i, int j){
	while(i<j){
		int t  = arr[i];
		arr[i] = arr[j];
		arr[j] = t;
		i++; j--;
	}
}

void rotatelist(int i, int j, int k){
	reverse(i,j-1);
	reverse(j, k);
	reverse(i,k);
}

int transform(int N){
	/****
	arr   1 2 -1 1 3 -2 2
	index 0 1  2 3 4  5 6
	k = 5 
	j = 5 
	i = 3 
	such that j<= x <=k , arr[x] is negative number
	such that i<= x <j , arr[x] is positive number
	***/	
	int k = N-1, j, i;
	while(k>=0 && arr[k]>=0)  
		k--;	
	j = k;	
	do {
		while(j>=0 && arr[j]<0)  
			j--;
		j++;	
		i = j-1;
		while(i>=0 && arr[i]>=0)  i--;
		i++;
		rotatelist(i, j, k);
		k = i + (k-j);
		j = i-1;		
	}while(j>0);		
}


int main(){	
	int N = sizeof(arr) / sizeof(arr[0]);
	for(int i=0;i<N;i++) 
		cout << arr[i] << ' ' ; 
	cout << endl;
	transform(N);
	for(int i=0;i<N;i++) 
		cout << arr[i] << ' ' ; 
	cout << endl;	
}

- Weak Learner September 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Very bad code, see what happens with the array {-1,1,3,-2,2}

- varun August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Part of the inplace quicksort algorithm?

- gbodurov August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The inplace quicksort doesn't remain the order.

-1 1 3 -2 2 and pivot 0 it would give -1 -2 3 1 2 instead of -1 -2 1 3 2

- joe kidd August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Joe Kidd I said *part* of, not the whole sorting procedure, but the dividing part, which moves all negative numbers to the left and moves all the positive numbers to the right....

- gbodurov August 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 4 vote

Here is an O(n) solution without extra space.

void sort(int array[]){
		
		int pos_p = -1;
		int num_n = 0;
		
		for(int a:array)
			if(a<0) num_n++;
		
		for(int i=0;i<array.length;i++){
			if(array[i]>0){
				if(pos_p == -1)
					pos_p = i;
				else
					if(num_n > 0)
						swap(array, i, pos_p);
			}else{
				num_n--;
				if(pos_p >= 0){
					swap(array, i, pos_p);
					if(num_n>0)
						pos_p = i;
					else
						pos_p = -1;
				}
			}
		}
		
	}
void swap(int array[], int i, int j){
	int temp = array[j];
	array[j] = array[i];
	array[i] = temp;
}

- srdjan August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice one!

- joe kidd August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Doesn't work, check this for example -1 ,1 ,3 ,-2, -5, 2

- uruk hai August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

1,2,3,-1,-2. your code fail on tghis
123,-1,-2
213,-1,-2
312,-1,-2
-1,1,2,3,-2
-1,1,2,-2,3

- Anonymous August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 4 vote

1.Start counters i at 0th index and j at nth index of the array.
2.Increase i until arr[i]>=0
3.Decrease j until arr[j]<0
4.swap arr[i] ,arr[j]
5.repeat steps 2, 3,4 till i<j

time-O(n),space-O(1)

- Anonymous August 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please read the question again....relative position not keeping.

- Vin August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
1
of 1 vote

Its said in o (n) time & o (1) space....

- Ankit Gadia August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Man I 'm so sorry , here is the algo :
e.g {-1,2,8,1,-2,4} is the array
1)start i as 0, j as 0
2)while j<n
inc j by one
if arr[j] is negative ,
make arr[i] as this neg number arr[j]
inc i by 1
and shift all the elements from arr[i to j-1] by one position

but again i 'm afraid it is O(n^2) WC and O(1) space :| ,sorry for not having read the memory constraints above,,actually this shifting procedure is O(N) itself :/

- Dale Steyn August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

Order not maintained...

- varun August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

Aren't you using extra space ?? New array is being created here.....

- varun August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Impossible? Don't make claims about which you have no clue.

- Anonymous August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This problem has a O(n) time and O(1) space complexity solution if relative ordering is not a factor. To keep space constant you have to use n^2 operations (swaps and compares) to rearrange the array. To keep operations constant you would need to allocate additional memory to keep track of where each positive/negative entry will need to land.

Also note that I am making the assumption that 0 is treated like a positive number, although I would clarify this point with the interviewer to ensure correctness.

O(n) time, O(1) space without ordering solution:
1. Start with two pointers, one at the front and one at the end ( i=0, j = array.length -1). While i is less than j repeat steps 2-4.
2. Evaluate i - if it is less than 0 increment it by 1
3. Evaluate j - if it is greater than or equal to 0 decrement it by 1
4. Evaluate i && j - if i is greater than or equal to zero AND j is less than 0 then swap the elements. Increment i and decrement j.

Here is a working sample:

public static void sort(int[] a){
        int i = 0; 
        int j = a.length - 1;
        int tmp;
        
        while(i < j){
            if(a[i] >= 0 && a[j] < 0){
                tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
                i++;
                j--;
                continue;
            }
            
            if(a[i] < 0){i++;}
            
            if(a[j] >= 0){j--;}

        }
    }

- masterjaso August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@masterjaso

I don't think your algorithm will ensure the relative positions of both +ve and -ve numbers. Will you algorithm work for [-1 1 -2 2 -3 3]?

- Murali Mohan August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This paper:

"Stable minimum space partitioning in linear time"

by

Jyrki Katajainen,
Tomi Pasanen


does it in O(n) time and O(1) space, and maintains the relative order (which is what makes the problem difficult), and hence the usage of the word "stable" as the very first word in the title of the paper.

- Anonymous August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you explain that paper? It's over my head.

- Bryan August 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ Erasmus

You are correct, my shown algorithm does not maintain the relative order (as disclosed in my comments). I do want to thank you for the sample, it helped me identify a bug and I have amended my post with updated and correct code.

- masterjaso August 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Bryan. Don't worry if you don't understand, this is an impossible interview question.

- Anonymous August 25, 2013 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More