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 ?