Adrien Atallah Adrien Atallah - 2 months ago 92
Javascript Question

hackerrank circular array rotation terminated due to timeout in Javascript

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

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")
}
Comments