Two Pointers: Sort Colors

by Raul Bojalil

HTML

<div class="markdownViewer select-text  markdown-default markdown-table markdown-viewer markdown-viewer-heading" role="none"><h2 class="hover-anchor" id="Statement" data-id="e912159ba4656d694eefa773cabf35b3">Statement<a href="#Statement"><span class="anchor-link">#</span></a></h2>
<p data-id="8e118641b1d3075965917a7406248347">Given an array, <code>colors</code>, which contains a combination of the following three elements:</p>
<ul data-id="e6a5c4c3bc5c04867ae52f641559efd9">
<li>
<p><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>0</mn></mrow><annotation encoding="application/x-tex">0</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">0</span></span></span></span> (representing red)</p>
</li>
<li>
<p><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn></mrow><annotation encoding="application/x-tex">1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span> (representing white)</p>
</li>
<li>
<p><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>2</mn></mrow><annotation encoding="application/x-tex">2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">2</span></span></span></span> (representing blue)</p>
</li>
</ul>
<p data-id="c8d8beb2458395a4aec89004b62d72aa">Sort the array in place so that the elements of the same color are adjacent, with the colors in the order of red, white, and blue. The function should return the same array.</p>

<div class="markdownViewer select-text ...

JavaScript

const RED = 0;
const WHITE = 1;
const BLUE = 2;

function sortColors(colors) {

    let red = 0;
    let white = 0;
    let blue = colors.length - 1;

    while (white <= blue) {
        
        if (colors[white] === RED) {

            if (colors[red] !== RED) {
                [colors[red], colors[white]] = [colors[white], colors[red]];
            }

            white++;
            red++;
        }

        else if (colors[white] === WHITE) {
            white++;
        }

        else {

            if (colors[blue] !== BLUE) {
                [colors[white], colors[blue]] = [colors[blue], colors[white]];
            }

            blue--;
        }
    }

    return colors;
}

// Driver code
const inputs = [
    [0, 1, 0],
    [1, 1, 0, 2],
    [2, 1, 1, 0, 0],
    [2, 2, 2, 0, 1, 0],
    [2, 1, 1, 0, 1, 0, 2]
];

const arrayToString = (array) => {
  return array.map(x => x.toString()).join(",");
}

// Iterate over the inputs and print the sorted array for each
for (let i = 0; i < inputs.length; i++) {

    console.log(i + 1 + ".\tcolors:", arrayToString(inputs[i]),
                "\n\n\tThe sorted array is:", arrayToString(sortColors(inputs[i])));

    console.log("-".repeat(100));
}