Arrays - Rotate Array

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

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]

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1
0 <= k <= 10⁵

Follow up:

Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
Could you do it in-place with O(1) extra space?

Solution 1 - Using a temporary array
Solution 2 - Reverse input array and rearrange elements

In this approach, we will use a temporary array and copy last k elements of nums array into this temporary array first, then copy remaining elements from nums array, i.e. from 0^th index to n-k^th index into the temporary array. Finally replace nums array with the temporary array.

Implementation steps:

First, we will create a temporary array temp with same size as input array nums, also create a variable index and initialize with 0, we will be using it as index pointer for this temporary array.
Then, run a for loop from n-k^th index to end of nums array (last k elements) and copy these into temp array using the index created above, by the end of this loop index will be at a place where the next element can be filled from. For example if we fill 3 elements into the temporary array, then index will be incremented to 3.
Next, run another for loop from 0^th index to n-k-1^th index ( remaining elements in nums array from the beginning) and copy these into temp using the index created above.
By this step, elements in temp array are already rotated by k steps. So, finally, run another for loop to copy temp array into nums input array.

If k is greater than the input array nums length, we will do a mod operation on that, the reason for that is, say if the input array is [1,2] and k =3. After 1^st step, array will become [2,1], after 2^nd step array will become [1,2], and after 3^rd step array will become [2,1], which is same as step 1. So, we will do a mod on k.

import java.util.Arrays; public class RotateArray { static void rotateUsingTempArray(int[] nums, int k) { k %= nums.length; // If k is greater than array length, we just need to rotate mod number of times. //Say if array is [1,2] and k=3, if we rotate 1st time-> [2,1], 2nd time -> [1,2] // 3rd time -> [2,1], this is equivalent to rotate 1st time. int[] temp = new int[nums.length]; int index=0; for(int i=nums.length-k; i<nums.length; i++) { temp[index++] = nums[i]; } for(int i=0;i<nums.length-k;i++) { temp[index++] = nums[i]; } for(int i=0;i< nums.length;i++) { nums[i] = temp[i]; } } public static void main(String[] args) { int[] nums = new int[]{1,2,3,4,5,6,7}; rotateUsingTempArray(nums, 3); System.out.println(Arrays.toString(nums)); nums = new int[]{1,2}; rotateUsingTempArray(nums, 3); System.out.println(Arrays.toString(nums)); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of nums array.
Space complexity: O(n) for the temporary array.

In this approach, we will first reverse the input array nums, then reverse first k elements, then reverse remaining elements.

Example:

Let's consider input array as [1, 2, 3, 4, 5, 6, 7] and k = 3 , after rotating array with 3 steps , resultant array will be [5, 6, 7, 1, 2, 3, 4].
First, let's reverse the array, so the array will become [7, 6, 5, 4, 3, 2, 1].
Then, reverse first k elements, then the array becomes [5, 6, 7, 4, 3, 2, 1].
Now, reverse remaining elements on right side, then the resultant array becomes [5, 6, 7, 1, 2, 3, 4] and this is the final result that we want.
Advantage with this approach is that all operations are done in-place, so it does not require additional space.

import java.util.Arrays; public class RotateArray { static void rotateUsingReverseAndReArrangeApproach(int[] nums, int k) { if(k ==0) { return; } k %= nums.length; reverse(nums, 0, nums.length-1); reverse(nums, 0, k-1); reverse(nums, k, nums.length-1); } static void reverse(int[] nums, int from, int to) { while(from<=to) { int temp = nums[from]; nums[from] = nums[to]; nums[to] = temp; from++; to--; } } public static void main(String[] args) { int[] nums = new int[]{1,2,3,4,5,6,7}; rotateUsingReverseAndReArrangeApproach(nums, 3); System.out.println(Arrays.toString(nums)); nums = new int[]{1,2}; rotateUsingReverseAndReArrangeApproach(nums, 3); System.out.println(Arrays.toString(nums)); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of nums array.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis:

Example:

Complexity Analysis: