class Solution {
    // space O(1)
    // with zero, index, and two pointers.
    public void sortColors(int[] nums) {
        int i = 0;
        int k = 0;
        int j = nums.length - 1;
        while (k <= j) {
            if (nums[k] == 2) {
                nums[k] = nums[j];
                nums[j] = 2;
                j--;
            }
            else {
                if (nums[k] == 0) {
                    nums[k] = nums[i];
                    nums[i] = 0;
                    i++;
                }
                k++;
            }
        }
    }

    // public void sortColors(int[] nums) {
    //     int[] counts = new int[3];

    //     for (int i = 0; i < nums.length; i++) {
    //         counts[nums[i]]++;
    //     }

    //     int j = 0;
    //     int index = 0;
    //     while (index < nums.length) {
    //         if (counts[j] <= 0) {
    //             j++;
    //             continue;
    //         }
    //         nums[index] = j;
    //         counts[j]--;
    //         index++;
    //     }
    // }
}