Arrays: Left Rotation

  • + 1 comment

    Because it is O(n*k), if you have a big n and a big k, it could timeout. See if you can think of an algorithm that would visit each array element only once and make it o(n). Also, is there any optimization you can make? For example: if k is bigger than n, then you don't need to do k rotations you just need to do k % n rotations and k will be much smaller, smaller than n. Example:

    [ 1, 2, 3, 4, 5 ]

    K=2, K=7=(1*5)+2, K=12=(2*5)+2, they are all equivant, leading the array to be:

    [3, 4, 5, 1, 2]