An array contains both positive and negative numbers in random order. Rearrange the array elements so that positive and negative numbers are placed alternatively. Number of positive and negative numbers need not be equal. If there are more positive numbers they appear at the end of the array. If there are more negative numbers, they too appear in the end of the array.
For example, if the input array is [-1, 2, -3, 4, 5, 6, -7, 8, 9], then the output should be [2,-1,4,-3,5,-7,6,8,9]
array size < 10^3
Ok so we have 2 cases depending on whether there are more negative numbers or vice-versa. Once we separate the negative numbers on the left side and the positive ones on the right side, it's easy to permute a prefix or suffix in O(1) by some swaps to get the array alternatively. Let K = the number of negative numbers. Start with a pointer, j, at K+1th position. Now start with i from 1 to K. If p[i] < 0 do nothing, otherwise increase j as long as p[j] > 0. You stop when P[j]<0 and then make a swap (p[i], p[j]). At the end of this process you'll have separated the negative numbers from the positive ones. Then you only need to permute a prefix or a suffix on the basis of some simple formulas