# O(n) run time, O(1) space, rotating values in vector

• class Solution {
public:
void rotate(vector<int>& nums, int k) {
int arrLen = nums.size();

``````    if (k >= arrLen){
k = k % arrLen;
}

if (!arrLen){
return;
}

if (k == 0){
return;
}

int firstVal = nums[0];
int firstIndex = 0;

int emptyIndex = firstIndex;

for (int i = 0; i < arrLen; i++){
int correspondingIndex = (emptyIndex + arrLen - k) % arrLen;
if (correspondingIndex == firstIndex){
nums[emptyIndex] = firstVal;
firstIndex++;
firstVal = nums[firstIndex];
emptyIndex = firstIndex;
} else {
nums[emptyIndex] = nums[correspondingIndex];
emptyIndex = correspondingIndex;
}
}
}
``````

};

• can you please explain how you came up with the equation
correspondingIndex = (emptyIndex + arrLen - k) % arrLen ?
thanks!

• It's actually `correspondingIndex = emptyIndex - k (mod arrLen)` adjusted to not be negative by going up one cycle with addition inside the modulo.

• Another way of looking at it, which probably answers jchiang1208's question better, is that the algorithm above rotates left by `k` if:
`correspondingIndex = emptyIndex + k (mod arrLen)`
or right by `k` if:
`correspondingIndex = emptyIndex - k (mod arrLen)`
which is the same as rotating left by `arrLen - k`:
`correspondingIndex = emptyIndex + (arrLen - k) (mod arrLen)`

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