4-5

class Solution {
    public void sortColors(int[] nums) {
        int pos = 0;
        // The array will have 3 blocks: [zeros, ones, twos].
        // 1. Move all 0s to the beginning of the array (to form `zeros` block).
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 1) swap(nums, i, pos++);
        }
        // 2. pos points at the beginning of `ones` block –
        //    move all 1s to the `ones` block.
        for (int i = pos; i < nums.length; i++) {
            if (nums[i] == 1) swap(nums, i, pos++);
        }
        // We don't need to do anything else since `zeros` and `ones` blocks
        // are formed, which means `twos` block is already formed as well.
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}



class Solution {
    public void sortColors(int[] nums) {
        int[] freq = new int[3];
        for (int x : nums) {
            freq[x]++;
        }
        for (int x = 0, i = 0; x <= 2; x++) {
            while (freq[x]-- > 0) {
                nums[i++] = x;
            }
        }
    }
}



class Solution {
    public void sortColors(int[] nums) {
        int zerosPosition = 0;
        int ones = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) nums[zerosPosition++] = 0;
            else if (nums[i] == 1) ones++;
        }
        for (int i = zerosPosition; i < nums.length; i++) {
            nums[i] = i < zerosPosition + ones ? 1 : 2;
        }
    }
}