4 Oct 2014

Algo #114: Rotate Array

Problem Statement:
         Rotate array by K with constraints
                           Time Complexity: O(n)
                           Space Complexity : O(1)

For K=3

Notice that 1 is poped out and pushed at the back of 10 , similar thing happened for 2 and 3 as well.

Solution: 

Our approach will consist of three steps.
1. Reverse (0 to K )
2. Reverse (K+1 to len-1)
3. Reverse Entire array.

Lets See this by fig.
Fig : Step wise transformation of array.

Implementation of the above approach:


/**
  * Rotate array by k
  */
  void rotate2(int[] arr, int k) {
  if(k<=0 || arr==null || arr.length==0)
   return ;
  int[] old = Arrays.copyOf(arr, arr.length);
  k--;
  
  int i=0,j=k,len=arr.length;
  for (; i <=k/2 ; i++,j--)
   swap(arr, i, j);
  
  int temp=  i + (len-i)/2;
  for (i=k+1,j= arr.length-1; i <= temp ; i++,j--)
   swap(arr, i, j);
  
  
  for (i=0,j= len-1; i "+ Arrays.toString(arr));
 }

Please post your comments and suggestions
Happy Coding !! :)

No comments:

Post a Comment