Reversal algorithm for array rotation
Filed under Microsoft
Free read 3 of 3Understand constraints regarding in-place mutation, negative values, and what happens if k is larger than the array length.
The question
Given an array of integers, rotate the array to the right by k steps in-place using the reversal algorithm.
Constraints
- 1 <= arr.length <= 10^5
- 0 <= k <= 10^9
- Time complexity should be O(N)
- Space complexity should be O(1)
Examples
- Input
- arr = [1, 2, 3, 4, 5, 6, 7], k = 3
- Output
- [5, 6, 7, 1, 2, 3, 4]
- Why
- Rotate 3 steps to the right: [7, 1, 2, 3, 4, 5, 6] -> [6, 7, 1, 2, 3, 4, 5] -> [5, 6, 7, 1, 2, 3, 4].
Approach
Understand constraints regarding in-place mutation, negative values, and what happens if k is larger than the array length.
Shift the array element by element k times, taking O(N * k) time and O(1) space.
Use the reversal algorithm: normalize k, reverse the entire array, reverse the first k elements, and reverse the remaining elements.
Handle empty arrays, arrays with a single element, and k values equal to zero or multiples of array length.
Solution
O(N) time, O(1) space
class Solution:
def rotate(self, nums: list[int], k: int) -> None:
n = len(nums)
k %= n
def reverse(start: int, end: int):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start, end = start + 1, end - 1
reverse(0, n - 1)
reverse(0, k - 1)
reverse(k, n - 1)
Tips
- What they are testing: Tested on understanding of in-place array manipulation and handling edge cases where k is greater than the array length.
- Common mistake: Failing to normalize k using modulo arithmetic (k = k % n) leading to redundant rotations or out-of-bounds errors.
Follow-ups
- Write unit test cases
Related Microsoft questions
Collected from public candidate posts and coding forums. Updated Nov 2026.