7
\$\begingroup\$

From SO.

You are given an array with positive and negative integers. Write a function to change the elements order in the array such that negative integers are at the beginning, the positive integers are at the end and two integers that have the same sign don't change order.

Example:

  • Input 1,7,-5,9,-12,15
  • Output -5,-12,1,7,9,15
  • Input 1,-2,-1,2
  • Output -2, -1, 1, 2

Constraints: O(n) time limit and O(1) extra memory.

Improve this question
\$\endgroup\$
14
  • 2
    \$\begingroup\$ Is it at all possible in O(1) memory? The SO people haven't found one yet. \$\endgroup\$
    – J B
    Feb 5 '11 at 5:46
  • 1
    \$\begingroup\$ This question doesn't mention anything about being a code golf, yet the answers are all golfing. Can you clarify this? If it was intended to be code golf, this shows people are not specifying properly and that is a problem. If it was not, then answerers are not looking at the lack of the shortest code constraint and that is also a problem. \$\endgroup\$
    – moinudin
    Feb 5 '11 at 12:15
  • 6
    \$\begingroup\$ It's not possible in O(1) memory unless you use a transdichotomic machine model. An index into an array of length n takes up log n space. \$\endgroup\$
    – FUZxxl
    Jan 30 '15 at 11:33
  • 2
    \$\begingroup\$ @mbomb007 Yes. Storing an index into an array of size O(n) takes O(log n) space. none of the linked answers account for that. \$\endgroup\$
    – FUZxxl
    Jun 29 '16 at 22:43
  • 4
    \$\begingroup\$ I'm voting to close this question as off-topic because the challenge is not solvable. \$\endgroup\$
    – mbomb007
    Sep 26 '16 at 20:26