Time Complexity=O(n), Space complexity=O(1)
aaaaa bbbbb xxxxx ccccc
i j-> k
Initialization:
i = 0: all letters to the left-hand side of i are all “a”’s
j = 0: j is the current index, all letters in [i, j) are all “b”’s
k = n - 1: all letters the the right-hand side of k are all “c”’s
unknown area is [j…k]
class Solution {
public void sortColors(int[] nums) {
int i = 0;
int j = 0;
int k = nums.length - 1;
while (j <= k) {
if (nums[j] == 0) {
swap(nums, i, j);
i++;
j++;
} else if (nums[j] == 1) {
j++;
} else if (nums[j] == 2) {
swap(nums, j, k);
k--;
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}