# iterate over the list, and keep track of where the next 0 and 1 should be placed
# because 2 will always be last, replace the current element with 2
# TAKEAWAY: when sorting in place, have a counter to keep track of where an element should placed next
class Solution:
    def sort_colors(self, colors):
        next_red, next_white = 0, 0
        for i, c in enumerate(colors):
            if c < 2:
                colors[i] = 2
                colors[next_white] = 1
                next_white += 1
                if c == 0:
                    colors[next_red] = 0
                    next_red += 1

solution = Solution()
colors = [2, 1, 2, 2, 1, 0, 0]
print(colors)
solution.sort_colors(colors)
print(colors)
