# 4 kinds of solution with brief analysis

• 1.Use auxiliary storage to improve the run time. Core idea is to copy the first k elements of result array from original array, then put the first n -k elements to the tail of array.T(n) = O(n+k) , beats 13 % java submission. Not so good. As well it is with S(n) = O(n).

`Solution 1`

``````public void rotate(int[] nums, int k) {
k = k % nums.length;
int[] tmp = new int[k];
for (int i = 0; i< k; i++){
tmp[i] = nums[nums.length-k+i];
}
for (int i = nums.length-k-1 ; i >= 0;i--){
nums[i+k] = nums[i];
}
for (int i = 0; i < tmp.length ; i ++){
nums[i] = tmp[i];
}

}
``````

2.Use system.arraycopy to improve the performance. The core idea is the same with solution 1. It beats 95 % submission. However, Space (n) = O(n)

``````public void rotate(int[] nums, int k) {
k = k % nums.length;
int[] tmp = new int [nums.length];
System.arraycopy(nums, nums.length - k, tmp, 0, k);
System.arraycopy(nums, 0, tmp, k, nums.length - k);
System.arraycopy(tmp, 0, nums, 0, nums.length);
}
``````

3.Use Mod to find the new position, new index = (old index + k)%n.
T(n) = O(2n) when n <<< k, solution 3 is greater than solution 1. Beats 13.8% not so good

``````public void rotate(int[] nums, int k) {
int[] tmp = new int[nums.length];
for (int i = 0 ; i < nums.length; i++){
tmp[i] = nums[i];
}
for (int i = 0 ; i< nums.length;i++){
int index = (i+k)%nums.length;
nums[index] = tmp[i];
}
}
``````

4.With S(n) = O(1) extra storage, use the core idea that is a[(i+k) % length] = a[i] recursively, use the extra storage to keep the temp value. Be caution is that the recursion will be dead loop when the tail meet the head, so I use a boolean value to indicate the first meet.So the T(n) = O(n), beats the 14 % submission, but with least extra storage, which of others is S(n) = O(n)

``````public static void rotate(int[] nums, int k) {
int index = 0;
k = k % nums.length;
int startIndex = 0; // move to right when loop recursively
int tmp = nums[index]; //keep the first value
int tmmp = 0; // used as the temporary value when swap with tmp
int i = 0; // sum number of finding new index, sum is equal to length
while (i < nums.length){
//first time of index = startIndex, indicating loop when meet twice
boolean isFirst = true;
index = startIndex; // init index
tmp = nums[index];
while (index != startIndex || isFirst ){
index = (index + k) % nums.length;
tmmp = nums[index];
nums[index] = tmp;
tmp = tmmp;
isFirst = false;
i++;
}
startIndex ++;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.