# LC75 - Sort Colors
# Two pointers

class Solution {
    public void sortColors(int[] nums) {
        // sanity check
        // ...
        
        int length = nums.length;
        // elements from 0 to i but not include i is 0
        // elements from i to k but not include k is 1
        // elements from k to j is unknown
        // elements from j to length-1 but not include j is 2
        int i = 0; 
        int j = length - 1; 
        int k = 0;
        while (k <= j) {
            if (nums[k] == 0) {
                swap(nums, k++, i++);
            } else if (nums[k] == 1) {
                k++;
            } else if (nums[k] == 2) {
                swap(nums, k, j--);
            }
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}