1. Rotate Array 189

189. Rotate Array

Medium

Given an array, rotate the array to the right by k steps, where k is non-negative.

 

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

 

Constraints:

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

 

Follow up:

• Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

Accepted

1,159,251

Submissions

2,990,724

Seen this question in a real interview before?

Solution :

Approach 1 - Intermediate Array:

1. Take an array
2. Start from kth position in original array and copy to new array in first part
3. In second part, start with 0th position up to k to new array after kth position 

4. Copy the resultant new array to old array

Code 1: 

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

Space is O(n) and time is O(n). We can check out the difference between System.arraycopy() and Arrays.copyOf().

Approach 2 - Copy Previous:

1. Store the last element

2. Move previous element to current position from last to first (for all elements)

3. Copy the stored value of last element in first

4. Do step 2 and step 3 in loop till kth time

Code 2: 

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

Space is O(1) and time is O(n*k). 

Approach 3 - Bubble sort:

1. Outer loop up to k

2. Inner loop from n-1 to 1

3. Swap with previous element

4. Eventually after each outer loop one element will be rotated

Code 3: 

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        if (k > n)
            k = k % n;
        
        for(int i=0; i<k; i++) {
            for(int j=n-1; j>0; j--) {
                int temp = nums[j];
                nums[j] = nums[j-1];
                nums[j-1] = temp;
            }
        }
    }
}

However, the time is O(n*k)

Approach 4 - Reverse:

1. Check for illegal arguments and throw exception

2. Divide the array two parts: 1,2,3,4 and 5, 6

3. Reverse first part: 4,3,2,1,5,6

4. Reverse second part: 4,3,2,1,6,5

5. Reverse the whole array: 5,6,1,2,3,4

Code 4: 

class Solution {
    public void rotate(int[] nums, int k) {
        if (nums == null || nums.length==0 || k < 0) 
            throw new IllegalArgumentException("Illegal argument!");
        int n = nums.length;
        if (k > n)
            k = k % n;
        int mid = n-k;
        reverse(nums,0,mid-1);
        reverse(nums,mid,n-1);
        reverse(nums,0,n-1);
    }
    public void reverse(int arr[], int left, int right) {
        if(arr==null || arr.length==1) {
            return;
        }
        while(left<right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
}

Here, the time is O(n), the space is O(1)