• Time:O(n)
• Space:O(1)

C++

``````class Solution {
public:
void sortColors(vector<int>& nums) {
int zero = -1;
int one = -1;
int two = -1;

for (const int num : nums)
if (num == 0) {
nums[++two] = 2;
nums[++one] = 1;
nums[++zero] = 0;
} else if (num == 1) {
nums[++two] = 2;
nums[++one] = 1;
} else {
nums[++two] = 2;
}
}
};
``````

JAVA

``````class Solution {
public void sortColors(int[] nums) {
int zero = -1;
int one = -1;
int two = -1;

for (final int num : nums)
if (num == 0) {
nums[++two] = 2;
nums[++one] = 1;
nums[++zero] = 0;
} else if (num == 1) {
nums[++two] = 2;
nums[++one] = 1;
} else {
nums[++two] = 2;
}
}
}
``````

Python

``````class Solution:
def sortColors(self, nums: List[int]) -> None:
zero = -1
one = -1
two = -1

for num in nums:
if num == 0:
two += 1
one += 1
zero += 1
nums[two] = 2
nums[one] = 1
nums[zero] = 0
elif num == 1:
two += 1
one += 1
nums[two] = 2
nums[one] = 1
else:
two += 1
nums[two] = 2
``````

• Time:O(n)
• Space:O(1)

C++

``````class Solution {
public:
void sortColors(vector<int>& nums) {
int l = 0;                // next 0 should be put in l
int r = nums.size() - 1;  // next 2 should be put in r

for (int i = 0; i <= r;)
if (nums[i] == 0)
swap(nums[i++], nums[l++]);
else if (nums[i] == 1)
++i;
else
// we may swap a 0 to index i, but we're still not sure whether
// this 0 is put in the correct index, so we can't move pointer i
swap(nums[i], nums[r--]);
}
};
``````

JAVA

``````class Solution {
public void sortColors(int[] nums) {
int l = 0;               // next 0 should be put in l
int r = nums.length - 1; // next 2 should be put in r

for (int i = 0; i <= r;)
if (nums[i] == 0)
swap(nums, i++, l++);
else if (nums[i] == 1)
++i;
else
// we may swap a 0 to index i, but we're still not sure whether
// this 0 is put in the correct index, so we can't move pointer i
swap(nums, i, r--);
}

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

Python

``````class Solution:
def sortColors(self, nums: List[int]) -> None:
l = 0  # next 0 should be put in l
r = len(nums) - 1  # next 2 should be put in r

i = 0
while i <= r:
if nums[i] == 0:
nums[i], nums[l] = nums[l], nums[i]
i += 1
l += 1
elif nums[i] == 1:
i += 1
else:
# we may swap a 0 to index i, but we're still not sure whether
# this 0 is put in the correct index, so we can't move pointer i
nums[i], nums[r] = nums[r], nums[i]
r -= 1
``````