Shift elements in the array forward by k places

Given an array of m elements and an integer k ( total capacity of array >= m+k, but it has only m elements).

Write code to shift all the elements of the array forward by k positions.

For example: If k = 2 and the Input array is as given below, the output array should be:

The extra spaces will have random (garbage) elements, which we are not concerned about.

Solution:

We have done a similar (but not this) question about rotating an array around a pivot earlier. In this case, we are just shifting the elements. One wrong code to shift the elements (and my motivation to write this article, because many of my students attempted it like this in their first attempt) is as below:

// Wrong code
for (int i=0; i<m; i++)
    arr[i+k] = arr[i];

This is wrong because we will lose the element at (i+k)'th position forever. This problem is because we are shifting the elements starting from zero index. We should shift the elements from the last (m-1) element. So the write code should be:

void shiftElements(int *arr, int m, int k)
{
    for (int i=m-1; i>=0; i--)
        arr[i+k] = arr[i];
}

The responsibility of ensuring that arr has sufficient space lies with the caller of the function (like when you call a library function like strcpy, it is your responsibility to ensure that the target array is big enough to store the result).

Time Complexity: O(n)

Extra Space: O(1)

One more solution (not so efficient) can be to shift one element at a time. But that will increase the time complexity to O(n2). Feel free to feedback / comment.