LeetCode Solution

189. Rotate Array

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

Follow up:

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

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 <= 2 * 10^4
• It’s guaranteed that nums[i] fits in a 32 bit-signed integer.
• k >= 0

Solution 1: (Brute-force)

The solution given below is brute force in nature . It is to rotate all the elements of the array by k steps by rotating the elements by 1 unit in each space.

class Solution {
  public void rotate(int[] nums, int k) {
    // speed up the rotation
    k %= nums.length;
    int temp, previous;
    for (int i = 0; i < k; i++) {
      previous = nums[nums.length - 1];
      for (int j = 0; j < nums.length; j++) {
        temp = nums[j];
        nums[j] = previous;
        previous = temp;
      }
    }
  }
}

Time complexity of the above solution is : O(n*k)

Solution 2:(Using an extra array)

We use an extra array in which we place every element of the array at its correct position i.e. the number at index ii in the original array is placed at the index (i + k) { length of array}(i+k)% length of array. Then, we copy the new array to the original one

class Solution {
  public void rotate(int[] nums, int k) {
    int[] a = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
      a[(i + k) % nums.length] = nums[i];
    }
    for (int i = 0; i < nums.length; i++) {
      nums[i] = a[i];
    }
  }
}

Time complexity of the above solution is: O(n)