Given an array of positive and negative integers, re-arrange it so that you have positive integers on one end and negative integers on other

I recently came across a Microsoft Interview Question for Software Engineer.

Given an array of positive and negative integers, re-arrange it so that you have positive integers on one end and negative integers on other, but retain their order of appearance in the original array.

For example, given [1, 7, -5, 9, -12, 15]
The answer would be: [-5, -12, 1, 7, 9, 15]

This should be done in O(n) time complexity and O(1) space complexity.

We could easily do it in O(n) time complexity, but I am not able to think how we can maintain the order of elements as in original array. If we forget about O(n) complexity, could someone tell me how we can preserve the order of elements without taking into consideration the space- and time-complexity.

To achieve this result in constant space (but quadratic time), you can use the two-queue approach by placing one queue at each end of the array (similar to the Dutch National Flag algorithm). Read items left-to-right : adding an item to the left queue means leaving it alone, adding an item to the right queue means shifting all elements not in a queue to the left by one and placing the added item at the end. Then, to concatenate the queues, simply reverse the order of elements in the second queue.

This performs an O(n) operation (shifting elements left) up to O(n) times, which yields an O(n²) running time.

By using a method similar to merge sort, you can achieve a lower O(n log n) complexity: slice the array in two halves, recursively sort them in the form [N P] [N P] then swap the first P with the second N in O(n) time (it gets a bit tricky when they don't have exactly the same size, but it's still linear).

I have absolutely no idea of how to get this down to O(n) time.

EDIT: actually, your linked list insight is right. If the data is provided as a doubly linked list, you can implement the two-queue strategy in O(n) time, O(1) space:

sort(list):
  negative = empty
  positive = empty
  while (list != empty)
     first = pop(list)
     if (first > 0) 
         append(positive,first)
     else
         append(negative,first)
  return concatenate(negative,positive)

With a linked list implementation that keeps pointers to the first and last elements, then pop, append and concatenate are all O(1) operations, so the total complexity is O(n). As for space, none of the operations allocate any memory (append merely uses the memory released by pop), so it's O(1) overall.

Here is a constriant version of O(n) time O(1) space solution, it assume maxValue*(maxValue+1) is less than Integer.MAX_VALUE, where maxValue is the result of maxmum value minus minmum value in the array. It utilize the original array as the temporary array to store the result.

public static void specialSort(int[] A){
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for(int i=0; i<A.length; i++){
        if(A[i] > max)
            max = A[i];
        if(A[i] < min)
            min = A[i];
    }
    //Change all values to Positive
    for(int i=0; i<A.length; i++)
        A[i]-= min;

    int newMax = max-min+1;

    //Save original negative values into new positions
    int currNegativeIndex = 0;
    for(int i=0; i<A.length; i++)
        if(A[i]%newMax < (-min))
            A[currNegativeIndex++] += (A[i]%newMax)*newMax;
    //Save original positive values into new positions
    int currPositiveIndex = currNegativeIndex;
    for(int i=0; i<A.length; i++)
        if(A[i]%newMax > (-min))
            A[currPositiveIndex++] += (A[i]%newMax)*newMax;
    //Recover to original value 
    for(int i=0; i<A.length; i++){
        A[i] = A[i]/newMax + min; 
    }
}

I'm not sure I understand the question correctly, as the answer appears to be too simple:

• Walk through the array and count negative numbers - O(n)
• Create a new array of size O(n)
• Walk through original array and place numbers into the new array. Use the known number of negative numbers to offset the positive ones - O(n)

Here's a quick way to do it in Python. It slightly differs from the above in first creating an array for the negatives, then appending the positives. So it's not as efficient, but still O(n).

>>> a = [1,7,-5,9,-12,15]
>>> print [x for x in a if x < 0] + [y for y in a if y >= 0]
[-5, -12, 1, 7, 9, 15]

Edit: Ok, now with O(1) space compexity it gets much harder. I'm interested in how to achieve it in O(n) time complexity, too. If it helps, here's a way to keep the O(1) space complexity, but requires O(n^2) time complexity:

• Start from the leftmost negative number. Walk through the array until you find the next negative number.
• In a new loop, exchange the negative number with the positive number left of it. Do this until you reach the other negative numbers. This ensures the order of the numbers remains unchanged.
• Rince and repeat until you reach the end of the array when looking for a new negative number.