Rotate Array
Medium · Arrays & Hashing · Array · Math · Two Pointers
Problem
You are given an integer array nums and a non-negative integer k. Rotate the array to the right by k steps, in place: every element moves k positions to the right, and elements that run off the end wrap around to the front.
Return nothing; the array itself is checked after your function returns. k can be larger than the length of the array.
Examples
Input: nums = [10,20,30,40,50], k = 2 Output: [40,50,10,20,30]
The last two elements wrap around to the front.
Input: nums = [1,2,3], k = 4 Output: [3,1,2]
Rotating by 4 is the same as rotating by 4 % 3 = 1.
Input: nums = [-1,8], k = 0 Output: [-1,8]
Zero steps leave the array as it is.
Constraints
- 1 <= len(nums) <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
- 0 <= k <= 10^5
Approaches
- Baseline: rotate one step at a time — time O(n · k), space O(1)
Follow-up
There is a second O(1)-space method: cyclic replacement, which moves each element straight to (i + k) % n and follows the cycle it starts. How many cycles are there? (The answer is gcd(n, k).)
Related problems
Start free on Cariara · Coding problems · System design studio
