Sort an array of 0 s, 1 s and 2 s


Asked In: AmazonMicrosoftAdobeWalmartLabs

You are given an array consist of only 0 s, 1 s and 2 s. You need to sort this array in O(n) time complexity with only one traversal.

Example:

Example:
Input : [2, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]

Modify array so that it becomes 
Output: [0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2]

Constraint1 :No extra space allowed

Constraint2 : Modify same array with single
traversal with O(n) time complexity

Problem level: Easy