CODEWITHSUNDEEP
algorithmsorting
Xinrui Ma
Xinrui Ma

Reputation: 2105

Segregate Even and Odd numbers, preserve order, O(1) space， O(N) time complexity

Input  = {12, 34, 45, 9, 8, 90, 3} 
Output = {12, 34, 8, 90, 45, 9, 3}

Given an array of integer, rearrange all even integer before all odd numbers, but keep their original sequence in array, using O(1) space and O(n) time complexity.

Thought:

Algorithm: segregateEvenOdd()
1) Initialize two index variables left and right:  
            left = 0,  right = size -1 
2) Keep incrementing left index until we see an odd number.
3) Keep decrementing right index until we see an even number.
4) If lef < right then swap arr[left] and arr[right]

But this can't guarantee the order is the same.

What if I want to use O(1) space to solve this problem?

Upvotes: 3

Views: 1494

Answers (1)

Tomasz Andel
Tomasz Andel

Reputation: 173

You have to store last odd and last even position,

1. Initialize both last_odd, last_even to -1;
2. Iterate over array
   - Check if array[i] is odd or even,
   - if diff(last_odd/last_even,i) >= 2 and last_odd/even not equal to 
     -1:
        if (element is odd/even) new index = last_odd/even+1
        - store element value in temp
        - move elements from new_index up to i one to right 
          starting back from i-1 down to new_index.
        - store temp in new_index
        - store last_odd/even as new_index accordingly and add to 
          last_even/odd the diff(which is +1)
   - else store last_odd/even as i accordingly

Upvotes: -1

Related Questions