Given an array of 3 different colored balls, we have to sort it using minimum number of swaps. It could be done in O(n) using 3-pointers and two traversals(one to count no. of occurrences of each color and other to sort). Could this be implemented in one traversal(count is not known before).
Yes, it can be done with a single traversal. For easier explanation, assume you have an array of integers, and those integers are either 1, 2 or 3. While you read the input, count how many 1's, 2's and 3's you have. Now you know what portion of the array should have 1's in the end, what portion should have 2's and what portion should have 3's. Let G1 be the portion of the array that should have 1's at the end, and similarly, G2 and G3 the same for 2's and 3's.