# Rotate Array

• For solution 3: isn't it n-elements are reversed a total of 2 times?
1st: n-elements
2nd: n-k elements
3rd: k elements
total: = n + n - k + k = 2n ?

• No, it is just one pass as we a have a count variable that keeps tracks of the items replaces so far.

• Let n=7 and k=2.

``````Original List                   : 1 2 3 4 5 6 7
After reversing all numbers     : 7 6 5 4 3 2 1
After reversing first k numbers : 6 7 5 4 3 2 1
After revering last n-k numbers : 6 7 1 2 3 4 5 --> This is not the Result

Solution lacks a step!!
``````

• if (nums.empty() || (k %= nums.size()) == 0) return;
int n = nums.size();
reverse(nums.begin(), nums.begin() + n - k);
reverse(nums.begin() + n - k, nums.end());
reverse(nums.begin(), nums.end());

• I wrote something to help understanding the third Cyclic Replacements approach:interpretation/proof

• var rotate = function(nums, k) {
for (var i = 0; i < k; i++){
nums.unshift(nums.pop())
}
};

In JavaScript

• Consider the following enhanced version of Approach #3 Using Cyclic Replacements in C++.

It first converts the problem into the equivalent rotation to the left of n - (k % n) positions. Then rotate each cycle directly in the vector, storing in the temp variable the first element only.

``````class Solution {
public:

void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = n - (k % n);

int count = 0;
for (int begin = 0; count < n; begin++) {
int temp = nums[begin];

int curr = begin;
for (int next = (curr + k) % n; next != begin; next = (curr + k) % n) {
nums[curr] = nums[next];
curr = next;
count++;
}

nums[curr] = temp;
count++;
}
}
};
``````

• This solution doesn't work for the following condition
Input: array: [1,2,3,4,5] and k = 4
Output: [5,1,2,3,4]
Could anyone tell me what is the issue with this code?

``````def rotateArray(nums, k):

k = k%len(nums)
end = len(nums) - 1

if k is None or k<= 0:
return

reverse(nums, 0, end - k)
reverse(nums, end - k + 1, end)
return reverse(nums, 0, end)

def reverse(nums, start, end):
while start < end:
nums[start], nums[end] = nums[end],nums[start]
start += 1
end -= 1
return nums

print rotateArray([1,2,3,4,5], 4)``````

• class Solution(object):
def rotate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
list=[]
for i in range(k):
nums.insert(0,nums.pop())

• ``````//Example for Rotate Array in C [Accepted]
void rotate(int* nums, int numsSize, int k) {
int *nArry = malloc(numsSize*sizeof(int));
if(numsSize<k)
k %= numsSize;
for(int i=0; i<numsSize; i++)
if(i<(numsSize-k))
nArry[i+k] = nums[i];
else
nArry[i-(numsSize-k)] = nums[i];
for(int i=0; i<numsSize; i++)
nums[i]=nArry[i];
}``````

• So instead of doing a deep copy at the end, I basically set the reference and it did not work:

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

I thought arrays were objects in Java and thus reference types.

• A stupid way
void rotate(vector<int>& nums, int k) {
int n=nums.size();
int count=(k%n==0 ? 0:n-k%n);
for(int i=0;i<count;i++){
nums.push_back(nums[i]);
}
nums.erase(nums.begin(),nums.begin()+count);
}

• @emkk Hey dude, I have the same quesiont with you. Took me some while but check this out https://leetcode.com/playground/new

See how the main class call the solution, it is passing an array to nums, thus any redirect of nums only change what it is points to, we have to make sure the ORIGINAL array object is changed, not redirecting the reference.

• @emkk Update, the link I put in the initial reply not valide. You have to click the >_ icon in the question to enter mode ` Debug Code in playground` and view the code for main class there.

• #include<stdio.h>
void rotate(int* nums, int numsSize, int k) {
int arr[500];
int i=0;
for(i=0;i<numsSize;i++)
arr[i]=nums[i];
for(i=0;i<numsSize;i++)
{
int st=i;
st+=k;
if(st>numsSize-1)
st=st-numsSize;
nums[st]=arr[i];
}

}

whats the problem with this code i have used an extra array it shows runtime exception error????

• I feel do while loop in the solution is not needed. We can just use a while loop.

``````class Solution(object):
def rotate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
k, n = k % len(nums), len(nums)
count = 0
for i in xrange(n):
curr_idx = i
curr_val = nums[i]
loop_started = False
while not loop_started or curr_idx != i:
loop_started =  True
count += 1
next_idx = (curr_idx+k) % n
next_val = nums[next_idx]
nums[next_idx] = curr_val
curr_val = next_val
curr_idx = next_idx
if count == n:
return
``````

• I think this is the fastest way using, but I'm not sure if it is an algorithm;

``````void rotate(int* nums, int numsSize, int k) {
int n = numsSize;
k = k % n;
if(k != 0){
int *buffer = calloc(k, sizeof(int));
memcpy( buffer, &nums[n - k], k * sizeof(int) );
memmove( &nums[k], nums, (n - k) * sizeof(int) );
memcpy( nums, buffer, k * sizeof(int) );
}
}
``````

• I think this is the fastest way using, but I'm not sure if it is an algorithm;
public static void rotate(int[] nums, int k) {

``````    k = k % nums.length;

int[] aux = Arrays.copyOf(nums, nums.length);

System.arraycopy(aux, nums.length - k, nums, 0, k);
System.arraycopy(aux, 0, nums,k, nums.length - k);
}``````

• For this problem, I used queue. pop_back and push to the front.

The complexity is `O(n)`

``````void rotate(vector<int>& nums, int k) {
k %= nums.size();
for(int i = 0; i < k; i++) {
nums.insert(nums.begin(), nums.back());
nums.pop_back();
}
}
``````

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