Hacker rank - Left rotation - PHP code feedback

Question

Here is the problem description - https://www.hackerrank.com/challenges/ctci-array-left-rotation/problem

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.

I wanted to get some feedback on my solution for this problem, it's a task in the Hackerrank Cracking the Coding Interview series. I am pretty sure the code is working fine, as it passes 7 of the 9 test cases, but is getting timed-out for the last two cases, since these cases are unknown, I wanted to get some expert feedback, as how can I optimize this code.

<?php
    //$handle = fopen ("input_leftR.txt","r");
    $handle = fopen ("php://stdin","r");
    fscanf($handle,"%d %d",$n,$k); //n and k values are available from here
    $a_temp = fgets($handle);
    $a = explode(" ",$a_temp);
    array_walk($a,'intval');

    //My Code from below
    $i; $j; $temp;
    if($n<0 || $n>1000000 || $k<0|| $k>1000000 || count($a) <=0)
        exit;
    for($i=0; $i<$k%$n; $i++){
    //for($i=0; $i<$k; $i++){
        for($j=0; $j<$n-1; $j++){
            $temp = $a[$j];
            $a[$j] = $a[$j+1];
            $a[$j+1] = $temp;
        }
    }
    //array_walk($a,'intval');
    //print implode(" ", $a);
    /*foreach($a as $key=>$value){
        printf("%d", $value);
        if($key<$n-1)
            printf(" ");
    }*/ 

    for($i=0;$i<$n;$i++){
    printf("%d", $a[$i]);

    if($i<$n-1)
        printf(" ");
    }
?>

Answer 1

Performance

Shifting the content of an array is a very expensive operation. Lot's of assignments.

Realize that you don't really need to shift the content. You can shift an offset index, and use that shifted offset to print the desired output:

for ($i = 0; $i < $n; $i++) {
    $shifted = ($i + $k) % $n;
    printf("%d", $a[$shifted]);

    if ($i < $n-1) printf(" ");
}

Unnecessary statements

This is unnecessary, it serves no purpose at all, you can safely delete it:

$i; $j; $temp;

Input validation

Although input validation is a good practice, in an online challenge you can trust that the input will be in the described format, and all values will be within the described ranges. I haven't seen an exception to that yet. So you don't need this kind of code:

if($n<0 || $n>1000000 || $k<0|| $k>1000000 || count($a) <=0)
    exit;

Formatting

The code is very poorly formatted:

• Indentation is inconsistent
• No spaces between operators make it look extremely compact and hard to read

Try to follow the writing style of the snippet in my first point.

Answer 2

• First of all, the rotation algorithm is arguably the slowest possible. It makes \$3n\$ assignments to rotate once, while you can do it in \$n+1\$ assignments:

  $tmp = $a[0];
  for ($i = 1; $i < $n; $i++) {
      $a[$i - 1] = $a[$i];
  }
  $a[$n - 1] = $tmp;
  

• Second, you repeat this \$k\$ times, driving the complexity up to \$O(nk)\$. You can make \$k\$ rotations at a time in just \$O(n)\$ time.

• Finally, as noted by $Janos, you don't need to physically perform rotation at all.

Answer 3

Return the updated array to be printed as a single line of space-separated integers.

If you are meant to return the updated array, then you cannot simply echo the values after picking the correct offsets.

Also, is it possible that the $d ($n in your code) value is exactly 0? (no rotation) If so, have a look at what that would do to some your calculations. $k%$n would encounter a division by zero error. If you are going to design early returns, the if !$d then return $a;.

In modern php, you no longer need to use $temp to swap the position of two elements. You can use array destructuring syntax [a, b] = [b, a].

I don't do hackerrank, so I don't know what is generally expected, but if this was a task in a professional assignment, I probably wouldn't manually loop at all.

$a = range(1, 10);
$d = 4;
echo implode(
         ' ',
         array_merge(
             array_splice($a, $d),
             $a
         )
     );

In context (with better function naming and type declarations):

function leftRotate(array $a, int $d): array {
    return !$d ? $a : array_merge(array_splice($a, $d), $a);
}

array_splice() does two crucial actions here.

1. modifies the array by only retaining elements from the offset and
2. returns the values that were removed.

By simply appending the removed elements to the end of the input array, the job is done.

I didn't test the performance on 3v4l.org (because it prefers not to have its resources abused by huge benchmark tests), but if it does timeout, I'd like to know.

I find this functional coding style to be much more concise, readable, and declarative.

Here is a similar technique that I devised a while back to do the same thing with javascript.

...for the record, these will work too, I just don't personally prefer the temporary variable declaration required by array_push() and I fear prepending data with array_unshift() may result in a higher computational load.

$move = array_splice($a, 0, $d);
array_push($a, ...$move);
echo implode(' ', $a);

Or

array_unshift($a, ...array_splice($a, $d));
echo implode(' ', $a);

Answer 4

function rotateLeft($d, $arr) {
  if($d > 0){
      $d--;
      $num = count($arr);
      $k = $arr[0];
      
      foreach($arr as $key => $val){
         
         if($key == $num-1){
          $arr[$key] = $k; 
         }else{
          $arr[$key] = $arr[$key+1];
         }
         
      }
      
      echo "<pre>";print_r($arr);echo "</pre>";
      rotateLeft($d, $arr);
  }

  
}

$arr = [1,2,3,4,5];

$d = 4;
rotateLeft($d, $arr);