Rotate Array

Problem:

Given an integer array and a number k , rotate the array by k positions to the right.

For example,

If the given array is

[1,2,3,4,5,6,7,8]

and k = 4

Then the output is

[5,6,7,8,1,2,3,4]

Pushing an element out of the array makes it land in the beginning of the array.

Try out the solution here:

https://leetcode.com/problems/rotate-array/

Solution:

Approach 1 – Use additional memory

The solution is fairly straightforward using additional memory.

Create an array of the same size as the input.

Copy the last k elements in the first k positions in the result array.

Then copy the first n – k elements (n is the size of the array) into the remaining positions.

Once the result array is ready copy back the elements to the original array.

Here is the code:

class Solution {
    public void rotate(int[] nums, int k) {
        
        
        if(k > nums.length) k = k % nums.length ;
        
        int[] result = new int[nums.length];
        int index=0;
        
        int start = nums.length - k;
        
        
        
        for(int i=start;i<nums.length;i++){
            
            
            result[index++] = nums[i];
            
        }
        
        
        for(int i=0;i<start;i++){
            
            
            result[index++] = nums[i];
        }
        
        for(int i=0;i<result.length;i++){
            
            
            nums[i] = result[i];
        }
        
    }
}

Notice that rotating an array of size n , n times places the elements in the same position as before.

So if k is greater than n , then we should find the modulus of k % n and perform that many number of rotations.

The time complexity in this approach is O(n) .

And space complexity is also O(n).

Approach 2 – Using k additional memory

Instead of using O(n) space complexity we can use constant space O(1).

In this approach we create an additional array of size k.

We will copy all the last k elements of the input array to this array.

Then we will move the remaining elements of the array to the end , making space for the k elements.

After this we copy the elements from the k array to the first k positions.

By doing this our space complexity is reduced.

Time complexity remains the same.

here is the code:

class Solution {
    
    
    
    
    public void rotate(int[] nums, int k) {
        
     if(k > nums.length ) k = k % nums.length;
        
        int[] karray = new int[k];
        
        int index = 0;
        
        for(int i= nums.length - k ;i<nums.length;i++){
            
            karray[index++] = nums[i];
            
        }
      
        
        int last = nums.length - k - 1;
        
        
        int end = nums.length - 1;
        
        
        while(last >=0){
            
            
            nums[end] = nums[last];
            end--;
            last--;
        }
        
        
        for(int i=0;i<k;i++){
            
            nums[i] = karray[i];
        }
        
    }
}

Approach 3 – In place rotation

In this approach , we are going to get rid of the k array as well.

There is no additional memory required.

Below is the algorithm:

  • Reverse the entire array
  • Reverse the first k elements of the reversed array
  • Reverse the last n – k elements of the reversed array.

That gives us the required output.

Here is the code:

class Solution {
    
    int[] nums;
    
    
    public void rotate(int[] nums, int k) {
        
        
        this.nums = nums;
        
        if(k > nums.length) k = k % nums.length ;
      

       reverse(0,nums.length-1);
       reverse(0,k-1);
       reverse(k,nums.length-1);
        
    }
    
    
    public void reverse(int first,int last){
        
        
              
        while(first < last){
            
            
            int t = nums[first];
            nums[first] = nums[last];
            nums[last] = t;
            
              first++;
              last--;
        }
        
      
        
        
    }
}

Time complexity is O(n) and space complexity is O(1)

That’s it!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s