Hacker rank - Left rotation - PHP code feedback for Timeout Here is the problem description: https://www.hackerrank.com/challenges/ctci-array-left-rotation


  A left rotation operation on an array of size \$n\$ shifts each of the array's elements 1 unit to the left. For example, if 2 left rotations are performed on array \$[1,2,3,4,5]\$, then the array would become \$[3,4,5,1,2]\$.
  
  Given an array of \$n\$ integers and a number, \$d\$, perform \$d\$ left rotations on the array. Then print the updated array as a single line of space-separated integers.


My code passes all test cases but is stuck on Hacker rank timeout.  I want to know where is the part that takes too long to execute, in order to optimize my code.

&lt;?php


function rotateOnce($a)
{
    if ($a[0] &gt;= 1 &amp;&amp; $a[0] &lt;= 1000000) {
        $left = array_shift($a);
        $a[] = $left;
    }
    return $a;

}

function checkConstrains($d, $n)
{
    if ($d &gt;= 1 &amp;&amp; $d &lt;= $n &amp;&amp; $n &gt;= 1 &amp;&amp; $n &lt;= 10 ^ 5)
        return true;

    return false;
}

// Complete the rotLeft function below.
function rotLeft($a, $d)
{
    global $n;
    if (checkConstrains($d, $n)) {
        for ($i = 0; $i &lt; $d; $i++) {
            $a = rotateOnce($a);
        }
    }
    return $a;

}

$fptr = fopen(getenv("OUTPUT_PATH"), "w");

$stdin = fopen("php://stdin", "r");

fscanf($stdin, "%[^\n]", $nd_temp);
$nd = explode(' ', $nd_temp);

$n = intval($nd[0]);

$d = intval($nd[1]);

fscanf($stdin, "%[^\n]", $a_temp);

$a = array_map('intval', preg_split('/ /', $a_temp, -1, PREG_SPLIT_NO_EMPTY));

$result = rotLeft($a, $d);

fwrite($fptr, implode(" ", $result) . "\n");

fclose($stdin);
fclose($fptr);
Efficiency

You do a lot of manual shifting and pushing with your array. This is ok for small inputs, but as soon, as the distance $d and the size of your array $n grow, this becomes inefficient.

The main overhead however is coming from calling rotateOnce. Parameters are passed by value by default. That means the array is copied every time the function is called. You could pass it by reference:

function rotateOnce(&amp;$a) {}


or simply include the two lines in your original function:

function rotLeft($a, $d) {
    $n = count($a);

    for ($i = 0; $i &lt; $d; $i++) {
        $left = array_shift($a);
        $a[] = $left;
    }

    return $a;
}


I would guess that constraints on HackerRank mean, that you can expect values in that range and don't need to test inputs yourself.

This is now significant faster, but still slow especially for large distances $d.



That being said, I would take a look at PHP's internal array functions and think of a way, how to use them in combination to increase performance.

My naive approach would be something like this


if d is 0 or the same as the array's size, return the original
else split the array into two chunks at index $d
combine both arrays and return the result


The function could look like this Don't hover if you don't want to get spoiled:


   
 function rotLeft($a, $d) {
     if (count($a) == $d || $d === 0) {
         return $a;
     }

     $chunk1 = array_slice($a, 0, $d);
     $chunk2 = array_slice($a, $d);

     return array_merge($chunk2, $chunk1);
 }
 


For this input:

$a = range(1, 100000);
$n = count($a);
$d = 500;


… I've measured these times on my local machine*:


original: 1.8130s
optimized: 0.4294
rewritten: 0.0054s




Exponential expression vs. bitwise Operators

Your program has a flaw. It won't calculate the result correctly for large array sizes, because of this:


$n &lt;= 10 ^ 5



^ is bitwise Xor and not pow:

pow(10, 5);
10 ** 5;




Try to avoid globals

I can see, that n is an input parameter that is not part of the function's given signature. However, I would try to avoid globals and get the value manually, if needed:

$n = count($a);


You can read more about this here:


PHP global in functions

Are global variables in PHP considered bad practice? If so, why?




* macOS 10.13, I7 2.5 GHz, 16GB RAM, MAMP PHP 7.2.1