# Java solution with O(1) space

• ``````public class Solution {
public void rotate(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return;
}
k = k % nums.length;
reverse(nums, 0, nums.length-k-1);
reverse(nums, nums.length-k, nums.length-1);
reverse(nums, 0, nums.length-1);
}
private void reverse(int[] num, int left, int right) {
while (left < right) {
int t = num[left];
num[left] = num[right];
num[right] = t;
left++;
right--;
}
}
}``````

• can you explain what is the underlying concept/theory of this algorithm?

• you could easily understand this algorithm by following the algorithm by hand :)

• Sure, we can. but it will be better if you can share "the way how" you figure it out, since this is not a straightforward thought

1. Reverse the first n - k elements, the last k elements, and then all the n elements.

Time complexity: O(n). Space complexity: O(1).

``````class Solution
{
public:
void rotate(int nums[], int n, int k)
{
k = k%n;

// Reverse the first n - k numbers.
// Index i (0 <= i < n - k) becomes n - k - i.
reverse(nums, nums + n - k);

// Reverse tha last k numbers.
// Index n - k + i (0 <= i < k) becomes n - i.
reverse(nums + n - k, nums + n);

// Reverse all the numbers.
// Index i (0 <= i < n - k) becomes n - (n - k - i) = i + k.
// Index n - k + i (0 <= i < k) becomes n - (n - i) = i.
reverse(nums, nums + n);
}
};``````

• Hi, shanxin136. Great explanations using changes of indexes :-) But I think you may have made some off-by-1 errors, the first should be `i` to `n - k - 1 - i`, the second should be `n - k - i` to `n - 1 - i`, and the last reverse should be `i` to `n - 1 - i`, which gives the same result as yours.

• Yes,your code is the best that I have saw!

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