# Interesting O(n) time O(1) space solution without Swap() with detailed comments

• //Time complexity O(n), extra space cost O(1)

``````public class Solution {
public void rotate(int[] nums, int k) {
k %= nums.length;
if(k<=0) return;
int index = k, loopHead = 0, curr = nums[0];
//1. index is the index of the element we will update in each iteration.
//2. loopHead is head of a loop (if exist) for index since each time we
// move index k steps further.
//3. curr is the value got from previous iteration nums[preIndex] and
//for updating nums[index]
for(int count=0;count<nums.length;count++){
nums[index] = curr; //set the value of loopHead.
loopHead++; //move 1 step further to jump out of loop
curr = nums[++index]; //This is the head of new loop
index = (index+k)%nums.length;
}
else{ //each time go k steps further
int tmp = nums[index];
nums[index] = curr;
curr = tmp;
index = (index+k)%nums.length;
}
}
}
}``````

• Thanks for sharing! It's interesting.

• {
int tmp = nums[index];
nums[index] = curr;
curr = tmp;
} this is just swap(). why do you say that " O(1) space without Swap()" ?

• Hi rabbitlxf, I mean I didn't swap between two elements compared to other's solution using swap between two elements, in each step, I just set i+k th element to the value of i th element and didn't set ith element to the value of i+k th element. For example the array is [3,4,7,2] and k = 1, my solution did it in the following order: Set Array[1] = 3, Array[2] =4, Array[3] = 7, Array[0] = 2. Surely you could just treat it as swap among N elements. For the O(1) space complexity, clearly it's O(1), since the extra tmp variable is only alive in one iteration of for loop. Or you can put it outside the for loop.

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