189. Rotate Array

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

!!! attention 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$
  • 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]; 
	} 
}