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, 2011 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, 2011 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, 2015 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, 2016 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, 2016 at 20:26

0

Reset to default

Browse other questions tagged or ask your own question.