Bobek's blog

How to solve this without extra memory
By Bobek, history, 9 years ago, In English

I am trying to solve this problem http://www.geeksforgeeks.org/rearrange-array-alternating-positive-negative-items-o1-extra-space/ There is a solution, but in my opinion it's actually O(n^2) , because rotate function also is O(n). Am I right ? Is there a way to solve it in O(n) time and O(1) space ?

  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Yes, the approach with O(1) extra space runs in quadratic time.

As far as I know, it's only possible to do this with O(1) extra space in a linked list, not in an array. In an array, the best I know with linear time and constant space is preserving the order of one of the sides: positive xor negative, not both.

→ Reply