Hackerrank circular array rotation failed 100,000 rotation test in php

Question

My first solution, POP -> unshift each element in turn, worked fine, but failed due to time out.

So I refactored it and now it fails the 100,000 rotation (with 500 elements) test.

I haven't a clue how to solve this so it works fast.

Any ideas?

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

// n = array length
// k = rotations
// q = # of queries in array
list($n, $k, $q,) = explode(' ', trim(fgets($handle)));

// what's our data
$arr = explode(' ', trim(fgets($handle)));

// pull queries
for($i = 0; $i < $q; $i++) {
    $_pos[] = trim(fgets($handle));
}

// NOTE: This is where the test case of 100k rotations on a
//       500 element array fails
// rotate array
$slice = array_slice($arr, -$k, $k);
$arr = array_slice($arr, 0, (count($arr) - $k));
$arr = array_merge($slice, $arr);

// ask the questions
for($i = 0; $i < $q; $i++) {
    echo $arr[$_pos[$i]] . "\n";
}

?>

Answer 1

Here is my solution:

//Fetch the input.
$handle = fopen("php://stdin", "r");
fscanf($handle, "%d %d %d", $n, $k, $q);

$inputArray = explode(" ", trim(fgets($handle)));
array_walk($inputArray, 'intval');

//Rotate the array
$totalTimesToRotate = ($k < $n) ? $k : ($k % $n);
if ($totalTimesToRotate > 0) {
    $slicedArray = array_splice($inputArray, -$totalTimesToRotate);
    $inputArray = array_merge($slicedArray, $inputArray);
}

//For all the queries, return the o/p
for ($i = 0; $i < $q; $i++) {
    fscanf($handle, "%d", $m);
    echo $inputArray[$m], "\n";
}

Explanation: For the sample use case mentioned on hackerrank here: https://www.hackerrank.com/challenges/circular-array-rotation

3 2 3
1 2 3
0
1
2

So, n (total array items) is 3 k (total rotations to be performed) 2 q ( total queries)

The purpose of this line

$totalTimesToRotate = ($k < $n) ? $k : ($k % $n);

Is to reduce the total rotations. Assume, n as 3 and k as 5

First rotation: [3, 1, 2]
Second rotation: [2, 3, 1]
Third rotation: [1, 2, 3]
Fourth rotation: [3, 1, 2] 
Fifth rotation: [2, 3, 1]

Notice how at the Fifth and Second rotation the outcome is the same. When n number of rotations are performed on an array of length n you get the same output. So, with the mod % operation we avoid the possibility of iterating unwantedly.

array_splice would remove the number of items which is equal to the number of times you want to perform the operation. So you get [2, 3] as the output and the inputArray is [1] And in the next step, [array_merge] will result in [2, 3, 1] which is the desired output.

The reason your solution results in a timeout is because you use array_slice twice whereas the same can be accomplished with array_splice.