Month: December 2021

An operation to rotate an array will shift each element to the left. We can perform this function X number of times depending on the input parameters. Since the lowest index element moves to the highest index upon rotation, this is called a circular array.

All we need to do is remove the first element of the array, save it in a variable, and then attach it to the end of the array. This can be done inside of a loop that iterates the number of times that we want to rotate the data. The function can take in the original array and the number of rotations. It returns the newly rotated array:

function rotateLeft($array, $rotations) {     
    for($i=0;$i<$rotations;$i++){
        $firstElement = array_shift($array);
        array_push($array, $firstElement);
    }
    return $array;
}

Although this code will work, and gets the job done, it is slow. When I tried this as a solution on HackRank (a code challenge website) it passed 9/10 test cases. It failed once, citing “time limit exceeded”.

The problem is with array_shift. It’s a PHP function that removes “the first value of an array off and returns it.” This shortens the array by a single element, moving everything else down one index. The algorithmic efficiency (expressed in Big-O notation) of array_shift() is O(n). That means, the larger the input array, the more time it will take to complete.

Next, I tried using array_reverse and array_pop. I figured that since array_pop() has a constant algorithmic efficiency, noted as O(1), it would help. Regardless of the size of the input, it would always take the same amount of time.  But, due to the use of array_reverse (twice!) it was even slower:

function rotateLeft($array, $rotations) {
    for($i=0;$i<$rotations;$i++){
        $array = array_reverse($array);
        $firstElement = array_pop($array);
        $array = array_reverse($array);
        array_push($array, $firstElement);
    }
    return $array;
}

Finally, I found a solution that was performant:

function rotLeft($array, $rotations) {
        $remaining = array_slice($array, $rotations);
        array_splice($array, $rotations);
        return array_merge($remaining, $array);
}

This code does not need to use any kind of loop, which helps to speed things up. First, array_slice() grabs the elements up to the point that the data should be rotated, and saves them to the variable $remaining. Next, array_splice() removes those same elements. Lastly, array_merge() glues the elements back together in the expected, rotated order.

This sort of computer science programming challenge can commonly be found during software engineering job interviews. When coming up with an answer, it is important to consider speed and performance. Understanding computing cost-effectiveness and Big-O can be a deciding factor in how your coding skills are judged.