public class Solution {

public void sortColors(int[] nums) {

```
//Algo thinking: two pass, first pass count 0s, 1s, 2s, second pass fill array with respect to counts
//Better: use 3 pointers, left, right, i
int left = 0, i = 0, right = nums.length - 1;
while (i <= right) {
if (nums[i] == 0) {
swap(nums, i++, left++); // loop invariant: left either points to 0 or 1, so after swap, i++
} else if (nums[i] == 2) {
swap(nums, i, right--);
} else { // nums[i] == 1
i ++;
}
}
}
private void swap(int[] a, int i, int j) {
int t = a[i]; a[i] = a[j]; a[j] = t;
}
```

}