Hacker rank - Left rotation - PHP code feedback for Timeout

Question

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[0] >= 1 && $a[0] <= 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[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);

insertusernamehere · Accepted Answer · 2018-08-23 14:48:57Z

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);

You can read more about this here:

_{^* macOS 10.13, I7 2.5 GHz, 16GB RAM, MAMP PHP 7.2.1}

Man , the way you solve it is simple , fast , and smart , can you share with me from where u improve your problem solve skills ? — Ayman Elarian
– Ayman Elarian, Commented Aug 23, 2018 at 8:06
@AymanElarian Thanks for your kind feedback. I've updated my answer, with more information about your original code and how to speed it up as well. Hope this is helpful to understand the mechanics better. Also this might answer your question a little bit: What is the single most effective thing you did to improve your programming skills?. — insertusernamehere
– insertusernamehere, Commented Aug 23, 2018 at 8:47

merlyn · Accepted Answer · 2018-08-23 06:33:53Z

Your code is inefficient. The 3 sample test cases your code passes have small inputs. The actual tests typically have larger inputs.

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.

You need to think of a better way to solve the problem. Is there a way to combine multiple rotations somehow?

Stack Exchange Network

Hacker rank - Left rotation - PHP code feedback for Timeout

2 Answers 2

Efficiency

Exponential expression vs. bitwise Operators

Try to avoid globals

You must log in to answer this question.

Hot Network Questions

Hacker rank - Left rotation - PHP code feedback for Timeout

2 Answers 2

Efficiency

Exponential expression vs. bitwise Operators

Try to avoid globals

You must log in to answer this question.

Related

Hot Network Questions