SortColors [source code]
public class SortColors {
static
/******************************************************************************/
class Solution {
public void sortColors(int[] nums) {
int lo = 0, hi = nums.length - 1;
for (int i = 0; i <= hi; i++) {
while (i < hi && nums[i] == 2) swap (nums, i, hi--);
while (i > lo && nums[i] == 0) swap (nums, i, lo++);
}
}
void swap (int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
/******************************************************************************/
public static void main(String[] args) {
SortColors.Solution tester = new SortColors.Solution();
int[][] inputs = {
{0,1,2,0,1,2},{0,0,1,1,2,2},
{0,1,2,1,1,1,2,0,1,2},{0,0,1,1,1,1,1,2,2,2},
{0,0}, {0,0},
{1,0}, {0,1},
{2,0}, {0,2},
{0,2,1}, {0,1,2},
{1,2,2,1,2,0}, {0,1,1,2,2,2},
{2,1,2}, {1,2,2},
};
for (int i = 0; i < inputs.length / 2; i++) {
int[] nums = inputs[2 * i];
String input_str = Printer.array (nums), ans_str = Printer.array (inputs[2 * i + 1]);
System.out.println (Printer.separator ());
tester.sortColors (nums);
String output_str = Printer.array (nums);
System.out.printf ("[%s] -> [%s], expected: [%s]\n",
input_str, Printer.wrap (output_str, output_str.equals (ans_str) ? 92 : 91), ans_str
);
}
}
}
Follow-Up里面的这个counting sort是很直观的, 毕竟这题的value的range非常的小;
Follow-Up是在之前的题目要求上加了更多的restriction, 这时候你要有两个方向:
- 是不是可以直接通过优化naive的做法来做? 比如是不是flag和counts的方式?
- 是不是需要完全重新的考虑问题, 换一个思路? 比如当时学Moore voting的时候;
这题如果单单是O(1) space的限制, 直接一个InPlace counts的方法就搞定了, 但是这题还要求1pass, 所以我感觉counts这个做法整个就不行了;
好像有点思路, 可能是利用类似MoveZeros类似的2pointer的做法? 不过逻辑可能要稍微复杂一点;
一开始的想法是直接只找0和1, 剩下的都是2, 然后0和1的收集区反正都是连在一起的, 维护起来也许比较好协调? 但是实际算了两下, 发现这个维护很难做到O(N);
然后想了一个比较损的办法: 从左边找0, 右边找2, 然后剩下的都是1; 这个可以写到一个循环里, 因为两个方向上面的fast指针的速度是一样的, 但是感觉这个方法可能会被喷不是真1pass; 不管了, 直接写写看;
while header好像不知道怎么写, 先不管, 先写里面的;
写了两个小时好吧, 写不出来, 放弃, 各种corner case各种break; 分别用了swap的方法和MoveZero里面的方法, 都不行, 代码:
int N = nums.length, zero_slow = 0, zero_fast = 0, two_slow = N - 1, two_fast = N - 1;
while (zero_fast < two_slow && two_fast > zero_slow) {
if (nums[zero_fast] == 0) {
nums[zero_slow] = 0;
if (zero_fast > zero_slow && zero_fast < two_slow)
nums[zero_fast] = 1;
zero_slow++;
} else if (zero_fast < two_slow && nums[zero_fast] == 2) {
nums[two_slow] = 2;
if (zero_fast > zero_slow && zero_fast < two_slow)
nums[zero_fast] = 1;
two_slow--;
}
if (nums[two_fast] == 2) {
nums[two_slow] = 2;
if (two_fast < two_slow && two_fast > zero_slow)
nums[two_fast] = 1;
two_slow--;
} else if (two_fast > zero_slow && nums[two_fast] == 0) {
nums[zero_slow] = 0;
if (two_fast < two_slow && two_fast > zero_slow)
nums[two_fast] = 1;
zero_slow++;
}
zero_fast++;
two_fast--;
if (zero_slow < two_slow)
nums[zero_slow] = 1;
if (two_slow > zero_slow)
nums[two_slow] = 1;
}
int N = nums.length, zero_slow = -1, zero_fast = 0, two_slow = N, two_fast = N - 1;
while (zero_slow < two_fast && zero_fast < two_slow) {
int next_zero_fast = zero_fast + 1, next_two_fast = two_fast - 1;
if (nums[zero_fast] == 0) {
zero_slow++;
swap (nums, zero_fast, zero_slow);
} else if (nums[zero_fast] == 2) {
two_slow--;
if (two_fast == two_slow)
two_fast = next_two_fast;
swap (nums, zero_fast, two_slow);
}
if (!(zero_slow < two_fast && zero_fast < two_slow))
break;
if (nums[two_fast] == 2) {
two_slow--;
swap (nums, two_fast, two_slow);
} else if (nums[two_fast] == 0) {
zero_slow++;
if (zero_fast == zero_slow)
zero_fast = next_zero_fast;
swap (nums, two_fast, zero_slow);
}
zero_fast = next_zero_fast;
two_fast = next_two_fast;
}
看完discussion之后发现我大概的思路还是知道的, 不过还是基本功不扎实; 我感觉我如果对quick sort partition的算法稍微再熟悉一点, 那么应该是有可能想到这题的conditional increment的写法的; 另外, 因为conditional increment的写法记得太熟了, 所以直接就用nested advance的思路来写写看;
没有editorial;
2018-02-12 10:51:53 今天LeetCode好像discussion维护, 不能直接看原帖, 所以这题的discussion很多就都是手动复制的, 没有原来帖子的链接;
@yidawang said in Share my at most two-pass constant space 10-line solution:
The idea is to sweep all 0s to the left and all 2s to the right, then all 1s are left in the middle.
It is hard to define what is a "one-pass" solution but this algorithm is bounded by O(2n), meaning that at most each element will be seen and operated twice (in the case of all 0s). You may be able to write an algorithm which goes through the list only once, but each step requires multiple operations, leading the total operations larger than O(2n).
class Solution {
public:
void sortColors(int A[], int n) {
int second=n-1, zero=0;
for (int i=0; i<=second; i++) {
while (A[i]==2 && i<second) swap(A[i], A[second--]);
while (A[i]==0 && i>zero) swap(A[i], A[zero++]);
}
}
};
这个实际上是一个很naive的做法, 先从左边开始把所有不是... 不对, 这个算法本身其实一点都不naive; 这个其实就是后面要讲的DNF(Dutch National Flag)问题的解法, 只不过这个不是标准的写法; 标准的写法后面要讲, 是一个conditional increment的写法, 而这里是用一个类似nested advance的做法来完成, 这两者之间的互换已经见过很多次了; 不过就这题来说, 这题最后实际上是conditional increment的写法更加的readable, 虽然这种代码结构一般来说写起来相对复杂一些;
下面的:
My java version is more readable, the basic idea is to use two pointer low and high and an iterator i
every elem left low pointer is 0, elem right high pointer is 2
public void sortColors(int[] A) {
if(A==null || A.length<2) return;
int low = 0;
int high = A.length-1;
for(int i = low; i<=high;) {
if(A[i]==0) {
// swap A[i] and A[low] and i,low both ++
int temp = A[i];
A[i] = A[low];
A[low]=temp;
i++;low++;
}else if(A[i]==2) {
//swap A[i] and A[high] and high--;
int temp = A[i];
A[i] = A[high];
A[high]=temp;
high--;
}else {
i++;
}
}
}
这个其实就是标准的DNF的写法, 具体的原理后面再说;
下面有人问这个算法需要先swap2, 然后再swap0, 这个其实我是理解的, 但是下面有人给了一个比较奇怪的理解:
Because the loop is from 0 to A.length-1, that is, small to large, left to right. In this way, if some swapping steps in (A[i]==0) break the order , it will be solved in the next i. But if some swapping steps in (A[i]==2) break the order, it will not be solved ,as the i has passed . So if you want to switch the order of the A[i]==2 line with the line below A[i]==0,just try
for(int i=A.length-1;i>=0;i—){}
说实话我是不赞同这个想法的, 首先, 他i的下限写的是0, 这个说明他根本没有理解这个算法的内核;
首先, 这个是另外一个帖子里面的DNF标准写法, 这个很好记:
A more general problem is the Dutch national flag problem by Edsger Dijkstra, which can be used to solve this problem, as well as partition in quicksort.
class Solution {
public:
void sortColors(int A[], int n) {
int i = 0, lo = 0, hi = n - 1;
// invariants: A[0..lo-1] are less than pivot 1, A[lo..i-1] equal, A[hi+1..end] greater
while (i <= hi)
if (A[i] < 1)
swap(A[i++], A[lo++]);
else if (A[i] > 1)
swap(A[i], A[hi--]);
else
i++;
}
};
DNF invariant
对比DNF的两种写法(一个是OP的), 我们可以大概理解这个算法的思路, 0..lo-1维护0, 然后hi+1..end维护2, 然后lo..i-1维护1, 然后i..hi是unprocessed: 这也是为什么header判断的是i <= hi, 因为只要unprocessed至少还有长度1, 那么循环就可以继续;
注意这里为什么定义比如lo-1和hi+1, 首先, 这个是很intuitive的, 当第一个iteration之前的state, 这两个区域都应该是Empty, 而整个0..N-1都是unprocessed, 合情合理, 包括1的区域实际上也是Empty;
这个算法的本身是非常类似quick sort的partition的, 实际上几乎没有多少差别, quick sort partition直接是只要分0和1, 然后标准写法是从0开始维护; 0区域和1区域的boundary在swap的过程中向后移动;
这里这个虽然是partition成三个, 但是实际的思路, 跟quick sort的partition基本没有区别! 我们的主要思路照样是从坐标维护0 region和1region, 只不过额外加一个(要先做)对2的处理: 直接往后面丢; 因为从后往前维护的只有2一个, 所以2region其实很好维护;
一个不好理解的是, 为什么当我们在[i]发现一个2, 然后丢给[hi++]之后, 我们自己手上要抓着[hi]之前的位置的数字? 很简单, 因为这个数字还是unprocessed的! 这个算法对于unprocessed的处理, 是一个从左到右的过程, 所以如果我们在之前的[hi]位置发现了一个还没有被处理过的数字, 自然放在unprocessed区域的最左边再处理, 这个也是为什么标准写法里面, swap2之后i不要++;
而swap0的其实就很简单, 我们在i, 左边0..lo-1是0region, lo..i-1是1region, 你发现了一个0, 你怎么处理? 很简单啊, 丢给[lo], 然后把[lo]之前的这个1拿到现在[i]的位置, 然后i和lo一起++, 因为0region和1region的末尾都要向后移动一个位置; 所以这个算法跟quick sort的partition就真的很像, 更关键的就是怎么维护0region和1region, 至于对2region的处理, 只是一个小的extension(也就是两个要点, swap回来之后不要i++, 然后i的上限应该是hi而不是N-1);
另外, 为了证明OP的写法跟conditional increment实际上是一样的:
class Solution {
public void sortColors(int[] nums) {
int lo = 0, hi = nums.length - 1;
for (int i = 0; i <= hi; i++) {
while (i <= hi && nums[i] == 2) swap (nums, i, hi--);
if (i >= lo && nums[i] == 0) swap (nums, i, lo++);
}
}
void swap (int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
这里, 第二个while改成了if, 照样AC; 注意我现在对于i的判断, 里面是包含==的了; OP原来的写法是为了方便避免了等号, 但是实际上保留等号感觉更有利于避免bug;
为什么我这里认为第二个对0的判断只可能有一个? 因为你[i]找到一个0, 直接丢给[lo]之后, [lo]原来的1丢回来到[i], 然后你下面i就应该++了. [lo]是不可能丢回来一个0给你的; 这个跟swap2不一样, [hi]可能继续丢回来一个2给[i], 但是[lo]丢给[i]的一定不可能继续是0; 理解了这个变动才是真的理解了这个DNF算法的invariant;
不过上面这个解释实际上并没有很好的解释为什么OP这里一定要先处理2然后再0? 按理说只要自己逻辑梳理清楚, 没有理由不能调换顺序?
尝试一下解决这个调换顺序的问题:
class Solution {
public void sortColors(int[] nums) {
int lo = 0, hi = nums.length - 1;
for (int i = 0; i <= hi; i++) {
while (i > lo && i <= hi && nums[i] == 0) swap (nums, i++, lo++);
while (i < hi && i >= lo && nums[i] == 2) swap (nums, i, hi--);
}
}
void swap (int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
lo:(0), i:(0), hi:(2) [[1, 2, 0]]
lo:(0), i:(0), hi:(2) [[1, 2, 0]]
lo:(0), i:(0), hi:(2) [[1, 2, 0]]
lo:(0), i:(1), hi:(2) [[1, 2, 0]]
lo:(0), i:(1), hi:(2) [[1, 2, 0]]
lo:(0), i:(1), hi:(1) [[1, 0, 2]]
看起来, 好像之前那个人的说法有点道理; 调换顺序, 因为我们i是从左到右, 如果先swap0, 那么swap完了之后, i肯定要前进, ...不对头
class Solution {
public void sortColors(int[] nums) {
int lo = 0, hi = nums.length - 1;
for (int i = 0; i <= hi; i++) {
if (i >= lo && nums[i] == 0) swap (nums, i++, lo++);
while (i <= hi && nums[i] == 2) swap (nums, i, hi--);
}
}
void swap (int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
lo:(0), i:(0), hi:(2) [[1, 2, 0]]
lo:(0), i:(0), hi:(2) [[1, 2, 0]]
lo:(0), i:(0), hi:(2) [[1, 2, 0]]
lo:(0), i:(1), hi:(2) [[1, 2, 0]]
lo:(0), i:(1), hi:(2) [[1, 2, 0]]
lo:(0), i:(1), hi:(1) [[1, 0, 2]]
我大概理解了, 首先虽然我们在处理i..hi的时候, 是一个从左到右的顺序, 但是实际上我们有时候是左右两头开弓的, 因为[hi]会把右边的unprocessed的数字给丢给[i], 所以实际上很多时候是两头同时缩进;
也就是对于一个i, 我们可能两头的unprocessed都要处理; 那么问题来了, 应该先处理左右哪头的? again, 仔细想一下, 如果[i]的位置是0, 那么我们一般只要正常的移动0region和1region的末尾就行了, 然后你再swap2(处理右边), 这时候要是[hi]又丢过来一个新的0怎么办? 但是这个iteration里面你swap0的部分已经过了啊? 那么只能指望下一个iteration了, 但是下一个iteration的i的位置已经不对了! 所以之前那个说order调换之后的那个人的说法是正确的, 不过当时看起来是有点不好理解;
但是那个人说的不够全面, 实际上, 解决这个问题还有一个思路:
class Solution {
public void sortColors(int[] nums) {
int lo = 0, hi = nums.length - 1;
for (int i = 0; i <= hi; i++) {
if (i >= lo && nums[i] == 0) swap (nums, i++, lo++);
while (i <= hi && nums[i] == 2) swap (nums, i, hi--);
if (i >= lo && i <= hi && nums[i] == 0) swap (nums, i, lo++);
}
}
void swap (int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
没错, 为了在i移动之前解决被[hi]丢过来的0, 在swap2之后, 我们再多加一个swap0, 注意这个swap0不要做i++因为外层的for loop会自动做. 当然, 这个代码就不那么好看了;
https://discuss.leetcode.com/topic/6968/four-different-solutions
// two pass O(m+n) space
void sortColors(int A[], int n) {
int num0 = 0, num1 = 0, num2 = 0;
for(int i = 0; i < n; i++) {
if (A[i] == 0) ++num0;
else if (A[i] == 1) ++num1;
else if (A[i] == 2) ++num2;
}
for(int i = 0; i < num0; ++i) A[i] = 0;
for(int i = 0; i < num1; ++i) A[num0+i] = 1;
for(int i = 0; i < num2; ++i) A[num0+num1+i] = 2;
}
// one pass in place solution
void sortColors(int A[], int n) {
int n0 = -1, n1 = -1, n2 = -1;
for (int i = 0; i < n; ++i) {
if (A[i] == 0)
{
A[++n2] = 2; A[++n1] = 1; A[++n0] = 0;
}
else if (A[i] == 1)
{
A[++n2] = 2; A[++n1] = 1;
}
else if (A[i] == 2)
{
A[++n2] = 2;
}
}
}
这个做法就是忽略了和quick sort partition之间的关系, 直接从左边开始同时维护三个region; 这个写起来风格差异比较大;
注意他这里的初始值, 是暴露了他的invariant的: 0..n0 is 0region, n0+1..n1 is 1region, n1+1..n2 is 2region; n2+1..i is unprocessed, starting with (before iteration 0) 0..n-1 totally unprocessed. 理解这个unprocessed的范围比较关键;
看到这里你可能思考, 拿为什么之前那个DJ的写法, 定义的时候是一个类似exclusive的风格? 其实最后只要你自己固定理解这个invariant, 怎么写是无所谓的; DJ的写法是为了保证i..hi这个闭区间代表unprocessed, 这样header的terminate好判断(as long as unprocessed length is >0), 而且其他几个变量开始的时候也不用使用-1这样的special value;
理解了这个invariant之后, 这个算法是出奇的intuitive和好理解!!! 实际上, 比如看到0的时候, 那么你如果把0写到0region的末尾, 也就是[n0+1], 你就要占用1region的一个位置, 那么1region就要占用[n1+1], 这个又占用了2region的位置, 所以2region也要向后多占用一个; 为了避免冲突, 2region先向后侵占, 然后1region, 然后0region; 其他的都类似; 这个算法还是很聪明的, 比DJ的写法更容易理解;
// one pass in place solution
void sortColors(int A[], int n) {
int j = 0, k = n - 1;
for (int i = 0; i <= k; ++i){
if (A[i] == 0 && i != j)
swap(A[i--], A[j++]);
else if (A[i] == 2 && i != k)
swap(A[i--], A[k--]);
}
}
这个开始就是正常的左边维护两个, 右边维护一个region的做法了; 注意, 他这个看起来很想之前OP的nested advance的做法, 实际上不是啊, 里面是一个if else结构, 而且这个写法其实是比较无聊的: 只要0和1中的任何一个swap触发, 就i--, 就是为了抵消header里面的i++, 意思也就是只有碰到[i]是1的时候才真的i++;
你可能有一个问题: 不对啊, conditional increment的做法里面, [i] == 0的时候不是也应该要i++吗? 其实你看看, 你swap0之后, 你不动, 你现在[i]的位置肯定是1了(刚刚[lo]丢过来的), 所以你下一个iteration肯定也是自动i++, 不会出乱子;
// one pass in place solution
void sortColors(int A[], int n) {
int j = 0, k = n-1;
for (int i=0; i <= k; i++) {
if (A[i] == 0)
swap(A[i], A[j++]);
else if (A[i] == 2)
swap(A[i--], A[k--]);
}
}
这个就是把上面那个对1的处理的地方改了一下. 反正第三个方法是比较无聊的, cancel increment这个技巧少量使用, 比如KMP那个算法的时候用过, 还是可以的; 但是像他这里这样, 三个branch, 有两个都用这个cancel, 就很无聊了;
nice ideas, but first method uses only O(1) space, what's more, 2 pass algorithm is actually faster (at least not slower) than all other 1 pass algorithm. Good ideas seem to make little sense here.
有点脑残的观点, 不过大概能理解他的意思; 反正这题只有三个value(range很小), 所以他认为最后这个counts占用的是O(1)空间, 反正说的也没错吧, 不过这种就是有点钻牛角尖了, 这个题目让你设计DNF算法, 考察的就是一个思维;
看起来这个partition问题并不trivial: https://www.geeksforgeeks.org/hoares-vs-lomuto-partition-scheme-quicksort/
Lomuto’s Partition Scheme
partition(arr[], lo, hi)
pivot = arr[hi]
i = lo // place for swapping
for j := lo to hi – 1 do
if arr[j] <= pivot then
swap arr[i] with arr[j]
i = i + 1
swap arr[i] with arr[hi]
return i
不能理解lo和hi的时候, 就用0和N-1来帮助理解;
lo..i-1维护smaller or equal, i..j-1维护greater, j..end维护unprocessed;
again, 这个swap操作实际上就是把greater region head给swap到greater region end append的位置;
他上面代码的意思应该是[hi]是pivot, 所以最后加了一个[i]和[hi]的swap;
Hoare’s Partition Scheme
partition(arr[], lo, hi)
pivot = arr[lo]
i = lo - 1 // Initialize left index
j = hi + 1 // Initialize right index
// Find a value in left side greater
// than pivot
do
i = i + 1
while arr[i] < pivot
// Find a value in right side smaller
// than pivot
do
j = j - 1
while arr[i] > pivot
if i >= j then
return j
swap arr[i] with arr[j]
注意他这里用的是inclusive的风格来维护了: lo..i is smaller region, j..hi is greater region; 上面伪代码少了一个大循环, 看下面的实际代码:
// This function takes last element as pivot, places
// the pivot element at its correct position in sorted
// array, and places all smaller (smaller than pivot)
// to left of pivot and all greater elements to right
// of pivot
int partition(int arr[], int low, int high)
{
int pivot = arr[low];
int i = low - 1, j = high + 1;
while (true)
{
// Find leftmost element greater than or equal to pivot
do
{
i++;
} while (arr[i] < pivot);
// Find rightmost element smaller than or equal to pivot
do
{
j--;
} while (arr[j] > pivot);
// If two pointers met.
if (i >= j)
return j;
swap(arr[i], arr[j]);
}
}
反正现在两种都理解了, 无所谓了;
Comparison:
- Hoare’s scheme is more efficient than Lomuto’s partition scheme because it does three times fewer swaps on average, and it creates efficient partitions even when all values are equal.
- Like Lomuto’s partition scheme, Hoare partitioning also causes Quicksort to degrade to O(n^2) when the input array is already sorted, it also doesn’t produce a stable sort.
- Note that in this scheme, the pivot’s final location is not necessarily at the index that was returned, and the next two segments that the main algorithm recurs on are (lo..p) and (p+1..hi) as opposed to (lo..p-1) and (p+1..hi) as in Lomuto’s scheme.
@dietpepsi said in AC Python in place one pass solution O(n) time O(1) space, no swap no count:
def sortColors(self, nums):
i = j = 0
for k in xrange(len(nums)):
v = nums[k]
nums[k] = 2
if v < 2:
nums[j] = 1
j += 1
if v == 0:
nums[i] = 0
i += 1
# 86 / 86 test cases passed.
# Status: Accepted
# Runtime: 44 ms
# 84.03%
Just like the Lomuto partition algorithm usually used in quick sort. We keep a loop invariant that [0,i) [i, j) [j, k) are 0s, 1s and 2s sorted in place for [0,k). Here ")" means exclusive. We don't need to swap because we know the values we want.
这个就是上面总结的那个人的第二个方法; 没有吹牛逼, 确实没有用swap; 因为swap需要三个assignment, 所以实际上这个算法可能稍微快一点? 其实快的不多;
写法上稍微有点差距: 无论[k]是什么数字, 最后这个位置反正是天生肯定会被侵占的;
@tianyicai2010 said in AC Python in place one pass solution O(n) time O(1) space, no swap no count:
A bit of history: this is "Dutch national flag" problem first proposed by Dijkstra.
https://en.wikipedia.org/wiki/Dutch_national_flag_problem
Quicksort uses this "3-way partition" to handle input with lots of duplicates.
上面提到过一次的:
@xiaohui7 said in C++ solution in 8 lines: an instance of the Dutch national flag problem by Edsger Dijkstra:
A more general problem is the Dutch national flag problem by Edsger Dijkstra, which can be used to solve this problem, as well as partition in quicksort.
class Solution {
public:
void sortColors(int A[], int n) {
int i = 0, lo = 0, hi = n - 1;
// invariants: A[0..lo-1] are less than pivot 1, A[lo..i-1] equal, A[hi+1..end] greater
while (i <= hi)
if (A[i] < 1)
swap(A[i++], A[lo++]);
else if (A[i] > 1)
swap(A[i], A[hi--]);
else
i++;
}
};
submission基本就是Lomuto写法了;
Problem Description
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
- You are not suppose to use the library's sort function for this problem.
click to show follow up.
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space?
Difficulty:Medium
Total Accepted:206.3K
Total Submissions:532.2K
Contributor:LeetCode
Companies
facebookmicrosoftpocket gems
Related Topics
arraytwo pointerssort
Similar Questions
Sort ListWiggle SortWiggle Sort II