Leetcode diary: 75. Sort Colors
Tags: javascript, algorithms, devjournal, motivation
Published: 2022-02-20 08:35:28

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.  

[link](url)  

This question is a good medium question. It probably leans on the easier side of medium, but still needs some head scratching to get it right. 

Given an array of 0,1,2 for any size. 
arrange them such that all of them are in the 0,1,2 order:
```
ex:     [1,1,1,0,0,2,2,1,2,0,1,2,0]
answer: [0,0,0,0,1,1,1,1,1,2,2,2,2]
```

you have to do this in place... otherwise the algorithm is too easy by just filtering out the 0s and put them back in, then filter out the 2s and put them to the back lol ...

Looking at this, I realized that
1.) we move all the 0s to left
2.) all the 2s to the right
3.) the 1s will just stay middle as result of 1 and 2

so what we needed is to find a way to move the 0s and 2s accordingly and not have to worry about the 1s.

The algorithm needs to do:
1.) with points: zeroIndex, nonZeroIndex
zeroIndex = pointer from nums.length-1. Its purpose is to locate the 0s that are located on the right side of the array
nonZeroIndex = pointer starting from index 0. It locates the first leftest non-zero index so that we can swap with 0 found on the right

2.) master while loop (zeroIndex > nonZeroIndex) 
3.) nested while (nums[zeroIndex] !== 0) {zeroIndex--}; this logic is kinda confusing because this means we break out of loop when nums[zeroIndex] === 0, idk if there is a better way to write, but if you do know, please comment below;
4.) nested while (nums[nonZeroIndex] === 0) {nonZeroIndex++}
5.) once both loops are done, we swap the values in place.
6.) repeats until master while loop ends

7.) repeat 1-6 for the 2s

the full code is below:

```
var sortColors = function(nums) {
    let zeroIndex, nonZeroIndex, nonTwoIndex, twoIndex, lastI;
    lastI = nums.length-1

    zeroIndex = lastI;
    nonZeroIndex = 0;  
    while (zeroIndex > nonZeroIndex) {
        while (zeroIndex >= 0 && nums[zeroIndex] !== 0)    {zeroIndex--;}
        while (nonZeroIndex <= lastI && nums[nonZeroIndex] === 0) {nonZeroIndex++;}
        if(zeroIndex <= nonZeroIndex) break;
        
        swap (nums,zeroIndex,nonZeroIndex);
        zeroIndex--; nonZeroIndex++;
    };

    nonTwoIndex = nums.length-1;
    twoIndex = 0;    
    while (nonTwoIndex > twoIndex) {
        while (nonTwoIndex >= 0 && nums[nonTwoIndex] === 2)  {nonTwoIndex--;}
        while (twoIndex <= lastI && nums[twoIndex] !== 2)     {twoIndex++;}
        if(nonTwoIndex <= twoIndex) break;
        
        swap (nums,nonTwoIndex,twoIndex);
        nonTwoIndex--; twoIndex++;
    };
    
    return nums;
};

function swap (nums,i,j) {
    const temp = nums[i];
    nums[i] = nums[j]
    nums[j] = temp;
}
```
There were two things I did not mention in the pseudo code cause it isn't obvious and did not realize until there were some failed test cases.

1.) it is possible for zeroIndex <= nonZeroIndex in the after the two nested while loop, so you'd need to break out of the master the loop when it is true. This means that the sorting is already done.

2.) you'll also need to do boundary checks on the nested while loops too. It is possible for tests cases like = [0,0,0,0,0,0,0] to be in infinite loop other wise

if you are still confused, watch this video:
https://www.youtube.com/watch?v=aayNRwUN3Do

Let me know anything on your mind after reading through this, THANKS!