LeetCode: RotateArray

Problem:

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Analysis:

First think about the problem which rotates the array to the right by 1 step. In this case, if we start from the end of the array, we only need to store the first element since only that number will be overwritten when rotation (nums[n01] will overwrite nums[0]). Now let us come back to the problem. We need to rotate k steps. We still start from the end of the array and we need to store the first k elements in a temporary array since these elements will be overwritten before they are rotated. This is just the same as the 1 step case we need to store the first element. 

C++:

void rotate(int nums[], int n, int k) {

        k = k%n; //we only need to rotate the array within k%n steps if k is greater than n

        int *temp = new int[k];

        for(int i=n-1; i>=0; i--){

            int offset = (i+k)%n;

            if(offset<k){

                temp[offset] = nums[offset]; //for the first k elements, we need to store them

            }

            if(i>=k){

                nums[offset] = nums[i]; //for the elements whose indices are greater or equal to k, we can just use the initial value in the array to rotate

            }

            else{

                nums[offset] = temp[i]; //for the elements whose indices are less than k, since they were already overwritten, we will use the temp array to rotate them

            }

            

        }

        

        

        delete []temp;

}

Cost:

O(n) for time and O(1) for space.