Sort Colors LeetCode Solution
We will use the integers 0
, 1
, and 2
to represent the color red, white, and blue, respectively.
You must solve this problem without using the library’s sort function.
Example 1:
Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2]
Example 2:
Input: nums = [2,0,1] Output: [0,1,2]
Constraints:
n == nums.length
1 <= n <= 300
nums[i]
is either0
,1
, or2
.
Follow up: Could you come up with a one-pass algorithm using only constant extra space?
Sort Colors Solutions
✅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
Watch Tutorial
Checkout more Solutions here