//time:o(n)

//space:o(1)

class Solution{

// public void SortedColors(int[] nums) {

// // 2-pass

// int count0 = 0, count1 = 0, count2 = 0;

// for (int i = 0; i < nums.length; i++) {

// if (nums[i] == 0) {count0++;}

// if (nums[i] == 1) {count1++;}

// if (nums[i] == 2) {count2++;}

// }

// for(int i = 0; i < nums.length; i++) {

// if (i < count0) {nums[i] = 0;}

// else if (i < count0 + count1) {nums[i] = 1;}

// else {nums[i] = 2;}

// }

// }

public void SortedColors(int[] nums) {

// 1-pass

if(nums == null || nums.length==0) return;

int p1 = 0, p2 = nums.length - 1, index = 0;

while (index <= p2) {

if (nums[index] == 0) {

nums[index] = nums[p1];

nums[p1] = 0;

p1++;

}

if (nums[index] == 2) {

nums[index] = nums[p2];

nums[p2] = 2;

p2--;

index--;

}

index++;

}

}

}