stefanjarina
3/7/2017 - 7:47 AM

Left Rotation Challenge

Left Rotation Challenge

Instructions.md
content_copyfile_download
  • Rendered
  • Source

Description

A left rotation operation on an array of size shifts each of the array's elements unit to the left.

Question

Given an array of integers and a number, perform left rotations on the array. Then return the updated array.

Given the 4 as a number of rotations applied to an array [1, 2, 3, 4, 5, 6] the expected result would be [5, 6, 1, 2, 3, 4]

Explanation

When we perform num = 4 left rotations, the array undergoes the following sequence of changes:

[1, 2, 3, 4, 5, 6] --> [2, 3, 4, 5, 6, 1] --> [3, 4, 5, 6, 1, 2] --> [4, 5, 6, 1, 2, 3] --> [5, 6, 1, 2, 3, 4]

Examples for testing

leftRotation(4, [1, 2, 3, 4, 5])        // [5, 1, 2, 3, 4]
leftRotation(8, [1, 2, 3, 4, 5])        // [4, 5, 1, 2, 3]
leftRotation(202, [1, 2, 3, 4, 5, 6])   // [5, 6, 1, 2, 3, 4]
leftRotation(200, [1, 2, 3, 4, 5])      // [1, 2, 3, 4, 5]
leftRotation(15123, [1, 2, 3, 4, 5,
                 6, 7, 8, 9, 10,
                 11, 12, 13, 14, 
                 15, 16, 17, 18,
                 19, 20]));             // [4, 5, 6, 7, 8, 9,
                                        //  10, 11, 12, 13,
                                        //  14, 15, 16, 17, 18,
                                        //  19, 20, 1, 2, 3]

Hint

This example have several possible solutions within the O(1) to O(n^2). Try to calculate with increasing number of rotations and increasing size of an array. Optimize algorithm accordingly.

possibleSolutions.js
content_copyfile_download
function leftRotation1(num, arr) {
    // solution1 - linear brute-force solution - slow for big number of rotations
    for(var i = 0; i < num; i++){
        var lastElement = arr.shift();
        arr.push(lastElement);
    }
    return arr;
} 

function leftRotation1(num, arr) {
    // solution2 - much faster
    if(num >= arr.length && num % arr.length === 0) {
      return arr;
    }
    if(num > arr.length) {
      return arr.concat(arr.splice(0, num % arr.length))
    } else {
      return arr.concat(arr.splice(0, num))
    }
}

function leftRotation(rotation, arr) {
  // solution3 - fast
  var i = rotation % arr.length;
  return arr.slice(i).concat(arr.slice(0, i));
}