# Java 1ms Not-so-fancy Divide-and-conquer solution O(1) space other than the recursion stack

• This is not as smart as the Three Reverses solution or the Cyclic Replacements solution in the editorial solution article. Just throwing something a little more plain-and-easy here to inspire thoughts.

In the example of `[1,2,3,4,5,6]` and `k = 2`:

• First swap `1,2` and `5,6`. (with a call to `reverse`, which is not defined in the same way as the Three Reverses solution).
• Then recurse on the rest `[3,4,1,2]` with `k = 2`.

The code itself should be quite straightforward.

``````public class Solution {
public void rotate(int[] nums, int k) {
rotate(nums, 0, nums.length - 1, k);
}

public void rotate(int[] nums, int lo, int hi, int k) {
int n = hi - lo + 1;
if (k >= n) k = k % n;
if (k <= 0) return;
if (k == n - k) reverse(nums, lo, hi, k);
else if (n - k > k) {
reverse(nums, lo, hi, k);
rotate(nums, lo + k, hi, k);
} else {
reverse(nums, lo, hi, n - k);
rotate(nums, lo, hi - (n - k), k - (n - k));
}
}

public void reverse(int[] nums, int lo, int hi, int k) {
int tmp;
int n = hi - lo + 1;
if (k > n / 2) return;
for (int i = 0; i < k; i++) {
tmp = nums[hi - k + 1 + i];
nums[hi - k + 1 + i] = nums[lo + i];
nums[lo + i] = tmp;
}
}
}
``````

I am not claiming O(1) space for this algorithm because some people feel the definition that excludes recursion stack is controversial. I am only claiming O(1) space and whatever the recursion takes here for the algorithm.

The general idea is kinda similar to a approach in this solution.

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