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