Leetcode 189: Rotate Array to the Right by K Times

$\mathtt{REFERENCE}$ @ LeetCode

Problem Definition

You are given an array and integer $k$ (>= 0). The problem is to rotate the input array to the right by $k$ times. Details can be found at LeetCode.

Example

Input: [1,2,3,4,5,6,7] and k = 3

Output: [5,6,7,1,2,3,4]

Solution 1 : Using Auxiliary Array of Size Same as Input Array.

In this method we go on saving the elements to the new rotated location in the auxiliary array. Finally when all elements are rotated to their proper indices, all elements are copied back to the original array in the same order as they appear after rotation.

Complexity

This method takes $\cal{O(n)}$ Time and $\cal{O(n)}$ Space.

Implementation

	//-------------------------------------------------------------------------------------
	//------------- METHOD 1 --------------------------------------------------------------
	/**
	* Rotation method that uses an auxiliary array to store the result
	* of rotation. Once the rotation is done, each element is copied to
	* the original array.
	*
	* The method requires O(n) time and O(n) space.
	*
	* @param nums input array to rotate.
	* @param k number of times to ratate the array.
	*/
	public void rotate(int[] nums, int k) {
	int N = nums.length;
	k = k % N;
	if (k == 0 || N < 2) return;
	int[] auxiliary = new int[N];
	for (int i = 0; i < k; i++) {
	int idx = N - 1 - i;
	int temp = nums[idx];
	while (idx - k >= 0) {
	auxiliary[idx] = nums[idx - k]; // push element from left to right
	idx -= k;
	}
	auxiliary[k - 1 - i] = temp; // bring element in the end section to front
	}
	for (int i = 0; i < N; i++) {
	nums[i] = auxiliary[i];
	}
	} // rotate

view raw ArrayRotation.java hosted with ❤ by GitHub

Solution 2 : Using Auxiliary array of size k

In the first solution we have used auxiliary array of size same as input to store rotated elements. If we look carefully, we can move in place those elements which can be pushed to right from left. Only those rightmost $k$ elements which can not be moved right cannot be moved in place because they have potential to replace the elements which have not been moved.

So it is sufficient to save only the right most $k$ elements in the auxiliary space. This will reduce the space requirement from ${O(n)}$ to ${O(k)}$.

In this method we use auxiliary array of size $k$ only. Rotation of the first $(N - k)$ elements will be done in place. Rotation of the last $k$ elements is stored in the auxiliary array. Once all elements are done, elements from the auxiliary array are copied in the front of input array.

Complexity

This method takes $\cal{O(n)}$ Time and $\cal{O(k)}$ Space.

Implementation

	//-------------------------------------------------------------------------------------
	//------------- METHOD 2 --------------------------------------------------------------
	/**
	* Rotation method that uses only a partial auxiliary array of size k.
	* Rotation mechanism is similar to first method difference being the beginning (n-k)
	* elements are rotated in place, only the last k elements are rotated and saved in
	* auxiliary array. Once the rotation is done, result is copied the be beginning of
	* original array.
	*
	* This method requires O(n) Time and O(k) space *
	*
	* @param nums input array to rotate.
	* @param k number of times to ratate the array.
	*/
	public void rotate2(int[] nums, int k) {
	k = k % nums.length;
	if (k == 0) return;
	int N = nums.length;
	int[] prefix = new int[k];
	for(int i = 0; i < k; i++) {
	int idx = N - 1 - i;
	int temp = nums[idx];
	while (idx - k >= 0) {
	//if (idx - k > 0) continue;
	nums[idx] = nums[idx - k]; // push element from left to right
	idx -= k;
	}
	prefix[k-1-i] = temp; // elements which cannot be pushed right. Save in prefix array
	}
	for (int i = 0; i < k; i++) {
	nums[i] = prefix[i]; // save elements from prefix array to original array
	}
	} // rotate2

view raw ArrayRotation.java hosted with ❤ by GitHub

Solution 3 : Using Reversal Algorithm

The solutions we discussed above uses auxiliary array of some size to solve the problem. Hence they have certain extra space requirement.

Here we are going to discuss a solution that does not use any extra space. So this is a constant space solution.

Here we divide the input array into two parts

1. First $(N - k)$ elements
2. and Last $k$ elements

Now,

1. Reverse the first part of the array.
2. Reverse the second part.
3. Reverse the whole array. Result will the required rotation of the array by $k$ times to the right.

Complexity

In this method we have managed to reduce the space complexity from O(n) to a constant space. This method still takes $\cal{O(n)}$ Time but $\cal{O(1)}$ Space.

Implementation

	//-------------------------------------------------------------------------------------
	//------------- METHOD 3 --------------------------------------------------------------
	/**
	* This method first reverses first N - k and last k elements separately.
	* Finally reverse the whole array to give the required output array.
	*
	* This method requires O(n) time and O(1) space.
	*
	* @param nums input array to reverse.
	* @param k number of times to rotate the intput.
	*/
	public void rotate3(int[] nums, int k) {
	k = k % nums.length;
	if (k == 0 || nums.length < 2) return;
	int N = nums.length;
	reverse(nums, 0, N - k);
	reverse(nums, N - k, N);
	reverse(nums, 0, N);
	} // rotate3
	//-------------------------------------------------------------------------------------
	/**
	* Reverses the array from index start (inclusive) to index end (exclusive)
	* @param nums input array
	* @param start start index
	* @param end end index
	*/
	private void reverse(int[] nums, int start, int end) {
	while (start < end) {
	swap(nums, start, end-1);
	start++;
	end--;
	}
	} // reverse
	//-------------------------------------------------------------------------------------
	/**
	* Swaps two elements in an array at index i and j.
	* @param nums input array
	* @param i index i
	* @param j index j
	*/
	private void swap(int[] nums, int i, int j) {
	int temp = nums[i];
	nums[i] = nums[j];
	nums[j] = temp;
	} // swap

view raw ArrayRotation.java hosted with ❤ by GitHub

---

---

---