Array Left Rotation Using Javascript and Node.js

I’ve put together some sample solutions to the common array left rotation challenge.

If you have not heard of hackerrank.com, check it out. It allows you to tackle common challenges using a variety of programming languages. The array left rotation challenge involves accepting some basic input via standard input, performing the array left rotation using the input, and then outputting the result as expected.

Here is the overview from hackerrank:

A left rotation operation on an array of size shifts each of the array’s elements 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].

The tests expect an output of each element in the array separated by a single space. So, using the example above the expected output is: 3 4 5 1 2.

Source

You can download the source code and follow along or fork the repository on GitHub:

Input

The first step I took was to create a simple text file that represents the given input:

5 4
1 2 3 4 5

I saved this to a file named data.txt.

I then wrote some code using Node.js to read and parse the data:

//global variables
let n = 0;
let d = 0;
let data = [];

//read standard input
process.stdin.setEncoding('utf8');
process.stdin.resume();

//store input
let input = '';
process.stdin.on('data', function (data) {
  input += data;
});
process.stdin.on('end', function () {
  let linesOfInput = input.split('\n');
  let temp = linesOfInput[0].split(' ');
  temp.map(Number);
  n = temp[0];
  d = temp[1];
  data = linesOfInput[1].split(' ');

  main();
});

//let's do it
function main() {
  //verify values
  if (n <= 0 || d <= 0 || data.length > n || data.length < d) {
    throw Error('The input values are invalid.');
  }

  //get result
  //this is a new array after the left shifts
  let result = getResult();

  //output result
  process.stdout.write(result.join(' '));
}

First, I define some globally available variables:

n = the number of integers
d = the number of shifts
data = the input array

Next, I read in the data from the standard input. When we are finished reading the standard input stream I parse the data to set the value of n, d and data. Finally, I invoke the main() function and we’re off.

First: `for`-loop

The first approach I took was to use the for-loop to iterate the number of shifts, and then to perform a single shift of the array data.

function main() {
  //code omitted

  //get result
  let result = getResultsUsingLoop();

  //code omitted
}

function getResultsUsingLoop() {
  let leftRotate = function (result) {
    let temp = [];
    for (var i = 0; i < n - 1; i++) {
      temp[i] = result[i + 1];
    }
    temp[i] = result[0];
    return temp;
  };

  let result = data.splice(0);
  for (let i = 0; i < d; i++) {
    result = leftRotate(result);
  }

  return result;
}

The main() function as not changed other than invoking the getResultsUsingLoop() function to get the resulting array.

A quick explanation of this approach:

I created a closure function named leftRotate() that does a single left rotation. I create a temporary array that will store the shifted array. I then iterate over each element setting the next element in the array for the current position. The last value will be undefined because it is beyond the boundary of the source data. So, I just set the value of the last position to the value from the first position of the source array.
I create a copy of the data and store it in result.
I then iterate the number for the number of shifts stored in d passing in the result from the previous iteration.
Return the new result array.

My evaluation of this approach:

It’s long.
It’s a bit clunky as we have to correct for going beyond the boundary of the source array.
Time complexity: O(n * d)

Second: `array.map()`

function main() {
  //code omitted

  //get result
  let result = getResultUsingArrayMap();

  //code omitted
}

function getResultUsingArrayMap() {
  let result = data.map(function (value, index) {
    let pos = parseInt(index) + parseInt(d - 1);
    if (pos > n - 1) {
      pos = pos - n;
    }
    return data[pos];
  });

  return result;
}

A quick explanation of this approach:

The getResultUsingArrayMap() function uses the array.map() function to iterate over each element in the array.
Upon each iteration I calculate the position of the element within data given the index and store this in pos.
I return the value in the source data.

My evaluation of this approach:

This is shorter than my first approach.
Calculating the pos for each iteration has to check if we have gone beyond the boundary of the array.
Time complexity: O(n)

Third: `array.shift()`

function main() {
  //code omitted

  //get result
  let result = getResultsUsingArrayShift();

  //code omitted
}

function getResultsUsingArrayShift() {
  let temp = data.splice(0);
  for (let i = 0; i < d - 1; i++) {
    let first = temp.shift();
    temp.push(first);
  }
  return temp;
}

As I thought more about the problem I realized that I was not taking advantage of Array.prototype methods like shift() and push().

A quick explanation of this approach:

The getResultsUsingArrayShift() function makes a copy of the source data and stores it in a variable named temp.
I then iterate the number of rotations given by n.
Within each iteration I invoke array.shift() and store the first element in the variable first. I then push() the first element onto the end of the array.

My evaluation of this approach:

This is very short and very simple.
Taking advantage of the shift() and push() methods reduce complexity and time.
Time complexity: O(n)

Source

You can download the source code or fork the repository on GitHub:

Executing

Executing the solution is easy:

$ node array-left-rotation.js < data.txt

Source

Input

First: for-loop

Second: array.map()

Third: array.shift()

Source

Executing

First: `for`-loop

Second: `array.map()`

Third: `array.shift()`