Tristan's Collection of Interview Questions: Graceful Way to Shift an Array

Tristan's Collection of Interview Questions: Graceful Way to Shift an Array

Problem: We have an array of integers (or other type), given an integer k,  we want to shift the array elements by k. For example, if a[] = {1, 2, 3, 4, 5} and k = 2, the resulting array will be a[] = {4, 5, 1, 2, 3} .

Solution: This is an easy problem but a graceful solution is not that straightforward. When I mean "graceful", I mean a solution of O(n) time complexity and O(1) space complexity. The trick is try to reverse the array twice. The detail is as follow:

• First, reverse the whole array. If a[] = {1, 2, 3, 4, 5}, after reversing, we have a[] = {5,4,3,2,1}.
• Then reverse the subarray from idx 0 to idx k-1, with the previous example we have a[] = {4,5,3,2,1}. Then reverse the subarray from idx k to idx n-1, after this, we get a[] = {4, 5, 1, 2, 3}.

Read full article from Tristan's Collection of Interview Questions: Graceful Way to Shift an Array