189. Rotate Array

Description

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?

Constraints

• 1 <= nums.length <= 2 * 10^4

• It's guaranteed that nums[i] fits in a 32 bit-signed integer.

• k >= 0

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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]

Solutions

Solution 1

/**
 * Time complexity : O(n×k). All the numbers are shifted by one step(O(n)) 
 *    k times(O(n)).
 * Space complexity : O(1). No extra space is used.
 */

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

Solution 2

/**
 * Time complexity : O(n). One pass is used to put the numbers in the new array. 
 *    And another pass to copy the new array to the original one.
 * Space complexity : O(n). Another array of the same size is used.
 */
 
 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];
    }
  }
}

Solution 3

/**
 * Time complexity : O(n). Only one pass is used.
 * Space complexity : O(1). Constant extra space is used.
 */
 
 class Solution {
  public void rotate(int[] nums, int k) {
    k = k % nums.length;
    int count = 0;
    for (int start = 0; count < nums.length; start++) {
      int current = start;
      int prev = nums[start];
      do {
        int next = (current + k) % nums.length;
        int temp = nums[next];
        nums[next] = prev;
        prev = temp;
        current = next;
        count++;
      } while (start != current);
    }
  }
}

Solution 4

/**
 * Time complexity : O(n). n elements are reversed a total of three times.
 * Space complexity : O(1). No extra space is used.
 */
 
 class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        reverse(nums, 0, n-1);
        reverse(nums, 0, k-1);
        reverse(nums, k, n-1);
    }
    
    private void reverse(int[] nums, int left, int right) {
        while(left < right) {
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
            left++;
            right--;
        }
    }
}

Follow up