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


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

Analyze in: Java Python

Code in: Java Python C++

Scroll right to view the diagram