Segregate 0s & 1s

#1

Problem - 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]

One way to solve this problem is to use 2 pointer approach?

Is there any other way possible?

#2

Another one can be that

  1. Count the number of 0s. Let count be C.
  2. Once we have count, we can put C 0s at the beginning and 1s at the remaining n – C positions in array.
#3

Yes, this method will take O(n) time. Is there any other way possible which will take less time?

#4

To count n elements, the minimum time amount we can take is O(n) only, so i don’t think so, there will be more optimised way of doing it.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#6

can’t we just do sorting? it will take less time na if we use inbuilt sort() function?

#7

yes you can do it using sorting but
sorting take nlog(n) time
which is more than n

#8

cool gotcha! thanks.

#9

if your doubt resolved
plz mark it as resolved from your side

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.