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

Examples

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]

Solutions

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

/**
 * 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];
    }
  }
}

/**
 * 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);
    }
  }
}

/**
 * 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

Previous188. Best Time to Buy and Sell Stock IV Next190. Reverse Bits

Last updated 5 years ago

Was this helpful?