CODEWITHSUNDEEP
arraysalgorithm
ABC ABC
ABC ABC

Reputation: 1

Rearrange Array positive and negative on either side

Given a set of positive and negative integers group all the positive integers on one side and negative integers on one side. The numbers should be in the same order they appear.

Example:

Array = {1, -3, -5, 9 , -8}

O/P = {-3, -5, -8, 1, 9}

I dont think using extra space is challenging to this problem as you can simple loop in and fill the new array. Challenge is to do it in place without using extra space. This question was asked by my friend.

(I was thinking of solving it with 2 pointers and swapping positive negative etc but soon the relative ordering in which elements appear seems to be messed up)

Any suggestions?

Upvotes: 0

Views: 1246

Answers (2)

Ankit
Ankit

Reputation: 43

This can be of O(n). Below is the sample code in python. Using Pivot like one in quick sort solves the purpose. The solution would look like this - 

def one_side_arrange(self, arr):
    i = -1
    for j in range(len(arr)):
        if (arr[j] < 0):
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    return arr

Input Arr = [1,2,3,-1,2,-3,3,4,-3,-5] OutPut = [-1, -3, -3, -5, 2, 2, 3, 4, 3, 1]

Upvotes: -1

Eric J.
Eric J.

Reputation: 150118

This feels like homework, so I'll give you a hint.

Apply a stable sort.

Stable sorting algorithms maintain the relative order of records with equal keys.

As your equality test, don't use the actual value of the number. Instead, consider any positive number equal to any other positive number, and any negative number equal to any other negative number.

Upvotes: 2

Related Questions