Interview Question: Shift elements in the array forward by k places

Given an array of m elements and an integer k ( total size of array >= m+k), . Write code to shift all the elements of array forward by k positions. For example: If k = 2 and the Input array is as given below, the the output array should be:

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

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 loose the element at (i+k)'th position for ever.

The problem is because we are shifting the elements starting from zero index. We should shift the elements from the last (m-1) index. So the write code is:

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 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(n²).

Interview Questions Archive:

         To see all the questions in the category Click Here...