Algorithms and Data Structures · Middle · Question 74 of 75
How do you rotate an array right by k positions in place with O(1) extra memory?
// [1, 2, 3, 4, 5, 6, 7], k = 3 -> [5, 6, 7, 1, 2, 3, 4]- 1Call
arr.unshift(arr.pop())k times in a loop - ✓Correct answer: Reverse the whole array, then reverse the first k and the rest
- 3Copy the last k elements into a new array and concatenate
Explanation
Three reversals put every element in place in O(n) time and O(1) memory. unshift(pop()) is O(n) per step, so O(n × k) in total, and copying needs O(n) memory. Use k % n for k larger than the length.