Segregate 0s and 1s in an array

You are given an array of 0s and 1s in random order. Segregate 0s on left side and 1s on right side of the array. Traverse array only once.

Input array   =  [0, 1, 0, 1, 0, 0, 1, 1, 1, 0] 
Output array =  [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]

Solution:

def solution(arr)
  left = 0
  right = arr.length - 1

  while left < right do
    while (arr[left] == 0 && left < right) do
      left += 1
    end

    while (arr[right] == 1 && left < right) do
      right -= 1
    end

    if (left < right)
      arr[left] = 0
      arr[right] = 1
      left += 1
      right -= 1
    end
  end
  return arr
end

arr = [0,1,0,1,1,1,0,0,0]
print solution(arr)

3 thoughts on “Segregate 0s and 1s in an array”

  • 1
    Piyush on April 10, 2017 Reply

    This is great. Reduces the time by almost half

  • 3
    online learning on May 20, 2017 Reply

    Informative article, just what I wanted to find.

Leave a Reply

Your email address will not be published. Required fields are marked *