Given an input array consisting of only 0, 1, and 2, sort the array in a single traversal. You're not allowed to use any sorting function that Python provides.
Note: O(n) does not necessarily mean single-traversal. For example, if you traverse the array twice that would still be an O(n) solution but it will not count as single traversal.
No data structures are required other than the input array and a few primitives for calculations. This is an in-place sort.
Time complexity is O(n) by inspection. Each element in the array must be compared once.
Auxiliary complexity is O(1) by inspection. This is an in-place sort without any additional data structures.