Left circular rotation on array of integers

Algorithm to perform left circular rotation on an array of integers.
One rotation operation moves the first array element to the last position and shifts all remaining elements left one.

Example

Input 
var arr = [4,5,6];
var k = 2;

Output
           k = 1      k = 2    
[4,5,6] -> [5,6,4] -> [6,4,5]

1. Brute Force Method (Naive Approach) O(k)

Simplest way to solve this is to remove the first element from the array and add it on the last.
We can do this with an Array, As JavaScript has an inbuilt method for this.

function circularArrayRotation(arr, k) {
   //Perform the operations k times
    for(let i = 0; i < k; i++){
        arr.push(arr.shift());
    }    
    return arr;
}

console.log(circularArrayRotation([4,5,6], 2));
console.log(circularArrayRotation([4,5,6], 3));
Output:
[4, 5, 6] -> [5, 6, 4] -> [6, 4, 5]
[4, 5, 6] -> [5, 6, 4] -> [6, 4, 5] -> [4, 5, 6]

Time complexity: O(k).
Space complexity: O(1).

Explanation

  • We remove the first element by arr.shift() and add it on the last by arr.push(), builtin JavaScript array functions.

Time and Space complexity

  • As Array.shift() and Array.push() are inbuilt array function they take O(1) time and we are performing these operations k time so Time complexity is O(K)
  • We are not utilizing any extra space so Space Complexity is O(1)

Leave a Reply

Your email address will not be published. Required fields are marked *