## Google Interview Question for Interns

Country: CHINA
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
15
of 27 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)

Comment hidden because of low score. Click to expand.
4

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

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.

Comment hidden because of low score. Click to expand.
14

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.

Comment hidden because of low score. Click to expand.
0

@Jason. I like your three-reversion solution.

Comment hidden because of low score. Click to expand.
7

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

Comment hidden because of low score. Click to expand.
3

@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.

Comment hidden because of low score. Click to expand.
0

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

}

Comment hidden because of low score. Click to expand.
2

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

Comment hidden because of low score. Click to expand.
0

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.

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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)

Comment hidden because of low score. Click to expand.
0

package util;

public class SachinTest {

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

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

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

continue;
}
temp = temp.next;
}

print();
}

private static void init() {
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);

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() {
while (temp != null) {
System.out.println(temp.data);
temp = temp.next;
}
}

static class Node {
int data;
Node next;

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

Comment hidden because of low score. Click to expand.
0

@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.

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?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

@Rocky, or quicksort for that matter...

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?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

@anonymous: true, but I was referring to quicksort

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

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;
};
{
// 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;
while(pos != nullptr)
{
if (pos->value < 0)
{
if (prev != last_neg)
{
// There are some positive elements in between
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;
}
}

void main()
{
}

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

}

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

}

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, ]

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

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
1
of 1 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.

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

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.
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)

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?

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

I thought rather bout a single variable.

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

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

That's O(n^2)

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

thanks

Comment hidden because of low score. Click to expand.
0

@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.

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

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

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){

}
}

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

if(arr[i]>0){

}
}

System.out.println(list);
}
}

Comment hidden because of low score. Click to expand.
1
of 1 vote

space ??? you are using arraylist

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

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

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

Comment hidden because of low score. Click to expand.
0

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)

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.

Comment hidden because of low score. Click to expand.
0

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}

Comment hidden because of low score. Click to expand.
0

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.

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 + " ");
}

}

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

Comment hidden because of low score. Click to expand.
0

Last loop should be

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

Comment hidden because of low score. Click to expand.
0

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

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

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

Comment hidden because of low score. Click to expand.
0

you are taking extra space O(n)

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

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]

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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...

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

Comment hidden because of low score. Click to expand.
0

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

Comment hidden because of low score. Click to expand.
0
of 6 vote

// anshumandvyas@gmail.com

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

}

Comment hidden because of low score. Click to expand.
3

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

Comment hidden because of low score. Click to expand.
0

How is this O(n)? Please explain.

Comment hidden because of low score. Click to expand.
0

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

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

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

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

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.

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

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

}

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

Comment hidden because of low score. Click to expand.
0

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.

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;

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.

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

Comment hidden because of low score. Click to expand.
0
of 0 vote
Comment hidden because of low score. Click to expand.
0

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

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");

}

Comment hidden because of low score. Click to expand.
0

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

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.

Comment hidden because of low score. Click to expand.
0

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.

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(',')

Comment hidden because of low score. Click to expand.
0

ideone.com/jYtdmD

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

}

}

Comment hidden because of low score. Click to expand.
0

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

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).

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>

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

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();
}
}

Comment hidden because of low score. Click to expand.
0

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

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;

}
}

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;

}
}

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;

}
}

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

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

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

Comment hidden because of low score. Click to expand.
0

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

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");
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

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

}

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.

Comment hidden because of low score. Click to expand.
0

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

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

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

}

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] + " | ");
}

}

}

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?

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.

Comment hidden because of low score. Click to expand.
0

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

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.

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

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

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());

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

And yeah, -100.

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());

Comment hidden because of low score. Click to expand.
0

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.

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() {

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
// 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;

}

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

Comment hidden because of low score. Click to expand.
0

Nice! Best yet!

Comment hidden because of low score. Click to expand.
3

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

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

forgot to copy the initialization of i and j

i=0
j=0

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?

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

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;

}

?>

Comment hidden because of low score. Click to expand.
0

O(n) :)

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.

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

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)

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

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

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

}

}

}

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.
}
}

}

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

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

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).

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

}

Comment hidden because of low score. Click to expand.
0

#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]);

}

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

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

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

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

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()
{
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.

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

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

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

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

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

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

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

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

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

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;

}

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;

}

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

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

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

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

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

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.

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

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

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(',')]))

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)

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)

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)

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

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

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

}

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

}

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

}

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

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

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

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

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

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

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

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

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

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

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

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

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 ");
}

}

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 ");
}

}

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 ");
}

}

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 ");
}

}

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

}

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

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;

}
}

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

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

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?

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

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

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)

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

time: o(n)
memory: o(1)

//
//  AlgorythmsPlayground
//
//  Created by Kirill Kirikov on 29.09.15.
//

@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

@property (nonatomic, strong) Node *negative;
@property (nonatomic, strong) Node *positive;
@end

- (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) {
}
} else {
node.next = self.negative.next;
self.negative.next = node;
}

self.negative = node;
}

- (void) insertPositive:(Node *)node {

} else if (self.positive) {
self.positive.next = node;
} else {
self.negative.next = node;
}

self.positive = node;
}

- (void) print {
while (iterator) {
NSLog(@"%d", iterator.value);
iterator = iterator.next;
}
}

@end

Comment hidden because of low score. Click to expand.
0
of 0 vote

Time: o(n)
Memory: o(1);

//
//  AlgorythmsPlayground
//
//  Created by Kirill Kirikov on 29.09.15.
//

@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

@property (nonatomic, strong) Node *negative;
@property (nonatomic, strong) Node *positive;
@end

- (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) {
}
} else {
node.next = self.negative.next;
self.negative.next = node;
}

self.negative = node;
}

- (void) insertPositive:(Node *)node {

} else if (self.positive) {
self.positive.next = node;
} else {
self.negative.next = node;
}

self.positive = node;
}

- (void) print {
while (iterator) {
NSLog(@"%d", iterator.value);
iterator = iterator.next;
}
}

@end

Comment hidden because of low score. Click to expand.
0
of 0 vote

Time: o(n)
Memory: o(1);

//
//  AlgorythmsPlayground
//
//  Created by Kirill Kirikov on 29.09.15.
//

@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

@property (nonatomic, strong) Node *negative;
@property (nonatomic, strong) Node *positive;
@end

- (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) {
}
} else {
node.next = self.negative.next;
self.negative.next = node;
}

self.negative = node;
}

- (void) insertPositive:(Node *)node {

} else if (self.positive) {
self.positive.next = node;
} else {
self.negative.next = node;
}

self.positive = node;
}

- (void) print {
while (iterator) {
NSLog(@"%d", iterator.value);
iterator = iterator.next;
}
}

@end

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){

int a[] = {-1,1,2,-3,2};
for(int i = 0; i< a.length; i++){

if(a[i] < 0){
if(!m.containsKey(1)){
m.put(1,temp);
}else{
}
}else{
if(!m.containsKey(2)){
m.put(2,temp);
}else{
}
}
}

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()+" ");
}
}
}

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.

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

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

}

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

}

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

Comment hidden because of low score. Click to expand.
0

Ain't working !!!!
Worked for negative numbers but relative position of positive numbers are changed.

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

}

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])

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])

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)
else if(n==0)
else
}

List<Integer> sorted = new ArrayList<>();
return sorted;
}

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

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

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

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>

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

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

}
}

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

}

}

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]

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

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()

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() {

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;

}

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

}

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

}
}

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

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)))

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)

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)

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

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

Comment hidden because of low score. Click to expand.
0

how can you preserve the relative position???????????

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

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

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}

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Part of the inplace quicksort algorithm?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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....

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

Comment hidden because of low score. Click to expand.
0

Nice one!

Comment hidden because of low score. Click to expand.
0

Doesn't work, check this for example -1 ,1 ,3 ,-2, -5, 2

Comment hidden because of low score. Click to expand.
0

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

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)

Comment hidden because of low score. Click to expand.
0

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....

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

Order not maintained...

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

Aren't you using extra space ?? New array is being created here.....

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.

Comment hidden because of low score. Click to expand.
0

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

}
}

Comment hidden because of low score. Click to expand.
0

@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]?

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.

Comment hidden because of low score. Click to expand.
0

Can you explain that paper? It's over my head.

Comment hidden because of low score. Click to expand.
0

@ 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.

Comment hidden because of low score. Click to expand.
0

@Bryan. Don't worry if you don't understand, this is an impossible interview question.

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.

### 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.