Dutch National Flag

Problem

Given some balls of three colors arranged in a line, rearrange them such that all the red balls go first, then green and then blue ones.

Do rearrange the balls in place. A solution that simply counts colors and overwrites the array is not the one we are looking for.

This is an important problem in search algorithms theory proposed by Dutch computer scientist Edsger Dijkstra. Dutch national flag has three colors (albeit different from ones used in this problem).

Example

{
"balls": ["G", "B", "G", "G", "R", "B", "R", "G"]
}

Output:

["R", "R", "G", "G", "G", "G", "B", "B"]

There are a total of 2 red, 4 green and 2 blue balls. In this order they appear in the correct output.

Solution

function swap(arr, i, j){
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
} 
function dutch_flag_sort(balls) {
    // Write your code here.
    var first=0;
    var last = balls.length-1;
    var i=0;
    
    while(i <= last){
        if(balls[i] == 'G'){
            i++;
        } else if(balls[i] == 'R'){
            swap(balls, i, first);
            first++;
            i++;
        } else {
            swap(balls, i, last);
            last--;
        }
    }
    
    return balls;
}

Time and Space Complexity

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