# 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.

<?php

function rotateOnce($a) { if ($a >= 1 && $a <= 1000000) {$left = array_shift($a);$a[] = $left; } return$a;

}

function checkConstrains($d,$n)
{
if ($d >= 1 &&$d <= $n &&$n >= 1 && $n <= 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 < $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);$d = intval($nd); 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(&$a) {}  or simply include the two lines in your original function: function rotLeft($a, $d) {$n = count($a); for ($i = 0; $i <$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 <= 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);


array_shift function needs to re-index the entire array every time you use it. Suppose an array has $10^5$ elements. And you have to rotate it $10^5$ times. Every single rotation will need $10^5$ operations due to array_shift. Thus, total number of operations is $10^{10}$ which is too high.