Friday, March 23, 2012

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}.

1 comment:

  1. Another way to think of this is to do N modulo mappings, like so.

    public static void shift(int[] arr,int k) {
    int placeHolder;
    int oldIdx = 0;
    int newIdx;

    placeHolder = arr[oldIdx];

    for(int i=0;i<arr.length;i++) {
    newIdx = (oldIdx+k)%arr.length;
    int temp = arr[newIdx];
    arr[newIdx] = placeHolder;
    placeHolder = temp;
    oldIdx = newIdx;
    }
    }

    ReplyDelete