Let the array be - 123456789 and k = 4
Step 1 - 12345 6789 ---> 54321 6789
Step 2 - 54321 6789 ---> 54321 9876
Step 3 - 543219876 ---> 678912345
678912345 !!
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n;
reverse(nums, 0, n - k - 1);
reverse(nums, n - k, n - 1);
reverse(nums, 0, n - 1);
}
void reverse(vector<int>& nums, int a, int b) {
int temp;
for(int i = a; i < (b + a + 1) / 2; i++) {
temp = nums[i];
nums[i] = nums[a + b - i];
nums[a + b - i] = temp;
}
}
};
Python code based on this logic
class Solution(object):
def rotate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
n = len(nums)
k = k % n
print("n: ", n, " k: ", k)
self.reverse(nums, 0, n - k - 1)
self.reverse(nums, n - k, n - 1)
self.reverse(nums, 0, n - 1)
def reverse(self, array, a, b):
while a < b:
array[a], array[b] = array[b], array[a]
a += 1
b -= 1
I used to ask this question in an interview. Whenever a candidate offered this solution, I'd politely say "That's neat. Now let's come up with a different way to solve the problem" :)
If that happened, I'd expect an even better solution from them, since it's now clear that they have seen the problem before.