Here is the brief explanation of my question -:
Given an array of positive and negative numbers, arrange them in an alternate fashion such that every positive number is followed by negative and vice-versa maintaining the order of appearance. 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.
Example: Input: arr[] = {1, 2, 3, -4, -1, 4} Output: arr[] = {-4, 1, -1, 2, 3, 4}
Input: arr[] = {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8} output: arr[] = {-5, 5, -2, 2, -8, 4, 7, 1, 8, 0}
I'm trying to solve this problem with the constraint O(n) time complexity and O(1) space complexity.But I didn't get any logic
Your blog title is incomprehensible. Try to actually describe the problem instead of trying to "summarize" it badly.
I guess you are looking for stable sort. I don't think it is possible to solve the problem in $$$O(n)$$$ time and $$$O(1)$$$ space unless there are some specific constraints. CMIIW
No this is not a stable sort problem. If my understanding is correct 2 -2 1 would result to -2 2 1
also stable sort on integers makes no sense. stable sort makes sense when objects you are sorting have a specific sort-key that is different from the object.
edit: in a way it can be viewed as stable sort when sortkey function is sign function.
edit2: oh no after the author changed the description it seems they were meaning completely different thing!
My idea is to use stable sorting algorithm to sort the given integers based on their signedness. Thus, the array $$$[2, -2, 1]$$$ can be seen as $$$[+, -, +]$$$ or $$$[1, 0, 1]$$$.
Do you wanna do a partition about 0 like we partition in stable quick sort?