rinku11's blog

Rearrange positive and negative numbers in O(n) time and O(1) extra space in an array and also you have to have to maintain order of appearance of positive and negetive number .
By rinku11, history, 3 years ago, In English

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

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

Comments Comments (5)
| Write comment?
»
3 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Your blog title is incomprehensible. Try to actually describe the problem instead of trying to "summarize" it badly.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    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!

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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]$$$.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you wanna do a partition about 0 like we partition in stable quick sort?

→ Reply