Rotating array elements →
Here is a very simple problem. Given an array of n elements and an integer d (less than n) how would you write a program to rotate (around) the elements of the array to the left by d elements? For example, if the input array (of size 7) is {1, 2, 3, 4, 5, 6, 7 }
and d is 2, the output array would be { 3, 4, 5, 6, 7, 1, 2 }
.
Let’s start simple. How would you rotate by 1? We would essentially move all the array elements to the left by one position, while moving the first element to the position of the last element. Essentially we would be moving n elements. Let’s write a function to do that:
The time complexity of the above solution is O(n) while the space complexity is O(1) (one variable to store the initial element). Now, rotating by d is just rotating by 1 done d times.
Now, the time complexity of the above function is O(nd). Can we do better than this?