Skip to content

189. Rotate Array

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

There are at least three different ways to solve this problem. Try to do with $\text{O}(1)$ space complexity.

Approach

  • Reverse the all the \(n\) elements.
  • Reverse the first \(k\) elements.
  • Reverse the remaining \(n-k\) elements.

Complexity

  • Time complexity : \(\text{O}(n)\)
  • We iterate the whole array only once
  • Space complexity : \(\text{O}(1)\)
  • No extra space is needed

Code

public void rotate(int[] nums, int k) { 
    k %= nums.length; 
    reverse(nums, 0, nums.length - 1); 
    reverse(nums, 0, k - 1); 
    reverse(nums, k, nums.length - 1); 
}

public void reverse(int[] nums, int start, int end) { 
    while (start < end) { 
        int temp = nums[start]; 
        nums[start] = nums[end]; 
        nums[end] = temp; 
        start++; 
        end--; 
    } 
}

Another Approach

Intuition

  • If we double the array (e.g [1,2,3] will become [1,2,3,1,2,3])
  • Rotating array simply means start reading the array after skipping certain step.

Approach

  • First create a new array double the size and copy the complete array twice onto it.
  • Amount of rotation can be simplified by \(minRotation = toatalRotation%(arraySize)\)
  • This is equivalent to \(toatalRotation = arraySize + arraySize + .... + x\)
  • Now rotating to right means start reading \(arraySize\) elements from index \(arraySize - minRotation\)

Complexity

  • Time complexity : \(\text{O}(n)\)
  • We iterate the array twice only
  • Space complexity : \(\text{O}(n)\)
  • We create a new array double the size.

Code

public void rotate(int[] nums, int k) { 
    int [] numsDoubled = new int[2*nums.length]; 
    for(int i = 0; i < nums.length; ++i) { 
        numsDoubled[i] = nums[i]; 
        numsDoubled[nums.length+i] = nums[i]; 
    } 
    k = k % nums.length; 
    for(int i = 0; i < nums.length; ++i) { 
        nums[i] = numsDoubled[ (nums.length - k) + i]; 
    } 
}

Comments