Sort Colors – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Given an array nums
with n
objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.
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
.
C++ Sort Colors LeetCode Solution
class Solution {
public:
void sortColors(vector<int>& nums)
{
int tmp = 0, low = 0, mid = 0, high = nums.size() - 1;
while(mid <= high)
{
if(nums[mid] == 0)
{
tmp = nums[low];
nums[low] = nums[mid];
nums[mid] = tmp;
low++;
mid++;
}
else if(nums[mid] == 1)
{
mid++;
}
else if(nums[mid] == 2)
{
tmp = nums[high];
nums[high] = nums[mid];
nums[mid] = tmp;
high--;
}
}
}
};
Java Sort Colors LeetCode Solution
public void sortColors(int[] nums) {
// 1-pass
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++;
}
}
Python 3 Sort Colors LeetCode Solution
def sortColors(self, nums):
red, white, blue = 0, 0, len(nums)-1
while white <= blue:
if nums[white] == 0:
nums[red], nums[white] = nums[white], nums[red]
white += 1
red += 1
elif nums[white] == 1:
white += 1
else:
nums[white], nums[blue] = nums[blue], nums[white]
blue -= 1
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
Leave a comment below