# 3 lines of C++ in one pass using swap

• Every swap will put one number into its correct position, so the running time is O(n)

For example,

at first, `nums[]` is `[1,2,3,4,5,6,7]`, n is 7, k is 3

after first outer loop, `nums[]` is `[4,1,2,3]`, n is 4, k is 3

after second outer loop, `nums[]` is `[4]`, n is 1, k is 0

loop ends.

``````void rotate(int nums[], int n, int k) {
for (; k %= n; n -= k)
for (int i = 0; i < k; i++)
swap(*nums++, nums[n - k]);
}``````

• It is a good solution. However, can the array increase like a point?
I am quite confused about "nums++".

• @bblsummer In C/C++, the name of an array is just a pointer to the array.

• This post is deleted!

• Amazing solution!

I have read the source code of the stl::rotate function,while using Random Access Iterator,STL has almost the same algorithm like yours,but your code is more simplified.

• brilliant idea! Use of characteristics of C makes the code shorter and elegant.

• Great solution. The code is simple and the algorithm is difficult to understand.

• Could you please give some hints (or materials, links) for us to better understand how this works?

• Elegant solution! However, the fourth results in undefined behavior. The side effect of `nums++` may (or not, which is what you saw) happen before evaluating `nums[n-k]`.

• Thanks for pointing out, here is a version without undefined behavior and probably easier to understand.

``````void rotate(int nums[], int n, int k) {
for (; k %= n; n -= k, nums += k)
for (int i = 0; i < k; i++)
swap(nums[i], nums[n - k + i]);
}``````

• Yeah, the new solution is much easier to understand. Thank you, sen.

• This post is deleted!

• You are wrong! In the "rotate" function, nums is just a point that points to an integer, so nums++ is quit reasonable. Of course the array name should not be used like nums++.

• Great solution! For those who may have difficulties appreciating the C flavor of the code, I rewrite it in C++, simply using a variable `start` to record the starting position of `nums`.

``````class Solution {
public:
void rotate(vector<int>& nums, int k) {
int start = 0, n = nums.size();
for (; k %= n; n -= k, start += k)
for (int i = 0; i < k; i++)
swap(nums[start + i], nums[start + n - k + i]);
}
}; ``````

• I have no idea the reason why your code works right ! Cound you give more detailed explaination！

Update ! I have got your idea !

``````class Solution
{
public:
void rotate(int nums[], int n, int k)
{
for (; k = k%n; n -= k, nums += k)
{
// Swap the last k elements with the first k elements.
// The last k elements will be in the correct positions
// but we need to rotate the remaining (n - k) elements
// to the right by k steps.
for (int i = 0; i < k; i++)
{
swap(nums[i], nums[n - k + i]);
}
}
}
};
``````

• I have no idea why the judgement is `k = k % n`. Can some one explain this for me?

• the judgement is not only executing k=k%n, but also check if the k should not be equal to 0.
If k is equal to 0, no need to swap (shift zero step does not do any change) , or it will be in the infinite loop.

• Java solution:

`````` public void rotate(int nums[], int k) {
int n = nums.length;
k=k%n;
for (int start=0; start<nums.length && k!=0 ; k = k%n){
for (int i = 0; i < k; i++) {
swap(nums, start+i, nums.length-k+i);
}
n=n-k;
start=start+k;
}
}

private static void swap(int[] nums, int a, int b){
int temp = nums[b];
nums[b]= nums[a];
nums[a]=temp;
}``````

• I cannot understand the condition `k %= n`

A example that is related to this condition.

k n nums
3 8 1,2,3,4,5,6,7,8
3 5 6,7,8,4,5,1,2,3
1 2 6,7,8,1,2,3,5,4
0 1 6,7,8,1,2,3,4,5
```````` `````````

I expect [6,7,8,4,5,1,2,3] becomes [6,7,8,1,2,3,4,5],
but due to `swap`, it has to become [6,7,8,1,2,3,5,4] first,
but `k = 1`, handles this case subtly.

Any one can explain this ?

• This is such a mysterious solution. Fascinating but convoluted.

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