The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

Problem

Given an array A 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.

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. Do it in O(n+m) time.

Example 1:
Input: A = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2:
Input: A = [2,0,1]
Output: [0,1,2]

Constraints:

    n == A.length
    1 <= n <= 300
    A[i] is either 0, 1, or 2.

Strategy

- Produce the frequency-of-occurrences array, count.
- From the count array, read the frequency for the given element zero, and print those number of zeros; read the frequency for the given element 1, and print those number of 1's; and read the frequency for the given element 2, and print those number of 2's.

The Program

The program is (read through the code and comments):

<?php

    function sortColors($A, $m) {
        // Determine dimension automatically
        $n = count($A);
    
        $count = array_fill(0, $m+1, 0);    //initializing count array

        //give frequencies to count array
        for ($i=0; $i < $n; $i++)
            $count[$A[$i]] = $count[$A[$i]] + 1;
    
        //print
        for ($i=0; $i < $m+1; $i++) {    //0 is an element in given array
            $frequency = $count[$i];
            for ($j=0; $j < $frequency; $j++)
                echo($i . ", ");
        }
        echo PHP_EOL;
    } 

  // main area
    $A1 = [2,0,2,1,1,0];
    $m1 = 0;    //for max number in A1
    for ($i=0; $i < count($A1); $i++)
        if ($A1[$i] > $m1)
            $m1 = $A1[$i];
    sortColors($A1, $m1);
    
    $A2 = [2,0,1];
    $m2 = 0;    //for max number in A1
    for ($i=0; $i < count($A2); $i++)
        if ($A2[$i] > $m2)
            $m2 = $A2[$i];
    sortColors($A2, $m2);

?>

The output is:

    0, 0, 1, 1, 2, 2, 
    0, 1, 2, 

The official time complexity for the called function is O(n+m), with n for iterating over the given array and producing the count array, and m for for iterating over the count array and producing the sorted print. The time to initialize the count array to 0's is ignored (PHP declares such arrays in O(1) time).

The space complexity for the called function is O(n) for the given array.

Thanks for reading.