Segregation logic to Sort an array of 0's, 1's and 2's


Asked In: AmazonMicrosoftAdobeWalmartLabs

Array consist of only 0's, 1's and 2's. Write an algorithm to sort this array in O(n) time complexity with only one traversal

Example:

Input : [0 1 2 0 1 2]

Modify array so that it becomes : [0 0 1 1 2 2]
constraint1 : You are not suppose to use any extra space
constraint2 : You need to change the same array with single traversal with O(n) time complexity

Problem level: Easy