hackerrank circular array rotation terminated due to timeout in Javascript

Question

I'm stuck on the circular array rotation algorithm on hackerrank with timeout issues and having trouble making it more efficient.

I'm using javascript:

  function processData(input) {

    var arr = new Array(4);

    var arrInt = [];

    var n, k, q, index, temp;



    arr = input.split(" ", 3); //input is a string, get n,k,q from this



    arrInt = input.split("\n");



    n = parseInt(arr[0]);

    k = parseInt(arr[1]);

    q = parseInt(arr[2]);



    var arrIntI = new Array(n);



    arrIntI = arrInt[1].match(/\d+/g); //read in integer array

    arrInt.shift();

    arrInt.shift();



   for(i = 0; i < k; i++){ //rotate array k times

        arrIntI.unshift(arrIntI.pop()); //Timeout on cases: 5, 9, 10, 12, 13, 14; passes all others!!!!!!



       //********************** Manual rotation: 

       //Timeout on cases: 5, 7, 9, 10, 12, 13, 14; Worse that Pop/unshift!!

       //temp = arrIntI[n-1];

       //for(l = n; l > 0; l--){

       //    arrIntI[l] = arrIntI[l - 1]; 

       //}

       //arrIntI[0] = temp;

       //delete arrIntI[n];

       //*******************************

    }    



    for(j = 0; j < q; j++){

        index = arrInt[j];

        console.log(arrIntI[index]);        

    }    



} 



process.stdin.resume();

process.stdin.setEncoding("ascii");

_input = "";

process.stdin.on("data", function (input) {

    _input += input;

});



process.stdin.on("end", function () {

   processData(_input);

});

I tried replacing the unshift/pop to rotate the array with a for loop but it didn't help the time out cases.

Thanks in advance!!

Answer 1

You don't need to actually rotate the Array at all, you can compute everything by just playing with the indices.

function int(v){ return v|0 }

function processData(input) {
    var rows = input.split("\n");
    var values = rows[1].split(" ");
    var [n,k,q] = rows[0].split(" ").map( int );

    if(values.length !== n || rows.length-2 !== q) 
        throw new Error("inconsistent imput");

    var offset = n - k%n;
    return rows.slice(2)
        .map(m => values[ ( int(m) + offset )%n ])
        .join("\n")
}

hackerrank circular array rotation terminated due to timeout in Javascript

Sign up