Problem overview
rotate(nums, k) receives an IntArray and a number k, and must rotate the array k times to the right, in place. One rotation moves every element one position to the right, and the last element jumps to the front. The function returns nothing: the caller sees the change in the same array. Here 1 <= k <= nums.size.
For nums = [1, 2, 3, 4, 5] and k = 2, one rotation gives [5, 1, 2, 3, 4] and the second gives [4, 5, 1, 2, 3]. The budget is O(n) time and O(1) extra space, so the code can't make a copy of the array and can't run k separate one-step rotations, which would cost O(n × k).
Approach: move each element straight to its final position
After k rotations, the element at index i ends up at index (i + k) % n, where n is the array's size. The remainder operator wraps indexes that run past the end back to the start. So the final position of every element is known up front.
The obstacle is that placing an element at its destination overwrites whatever lives there. The way around it is to carry that overwritten element along: hold one element, drop it in its target slot, pick up the element that was there, drop that one in its target slot, and so on. Following this chain visits indexes i, (i + k) % n, (i + 2k) % n, and eventually returns to i. That closed loop is a cycle.
One cycle doesn't always cover the whole array. When n and k share a common divisor greater than 1, the indexes split into several separate cycles. For n = 6 and k = 4 the chain from index 0 goes 0 → 4 → 2 → 0 and never touches indexes 1, 3 or 5. After a cycle closes, the algorithm starts the next one at the next index.
The solution does this with swaps instead of a separate "held" variable. The slot at startIndex plays the role of the hand: it always contains the element currently being carried. Each step swaps it with the target slot, which puts the carried element where it belongs and brings the displaced one into the hand.
Here is nums = [1, 2, 3, 4, 5, 6] with k = 4:
step 1: next = 4 [5, 2, 3, 4, 1, 6]
step 2: next = 2 [3, 2, 5, 4, 1, 6]
step 3: next = 0 [3, 2, 5, 4, 1, 6] cycle closed, start moves to 1
step 4: next = 5 [3, 6, 5, 4, 1, 2]
step 5: next = 3 [3, 4, 5, 6, 1, 2]
step 6: next = 1 [3, 4, 5, 6, 1, 2] cycle closed, start moves to 2
The result, [3, 4, 5, 6, 1, 2], is the original array rotated four places to the right. Each step settles one element for good, and there are n elements, so n steps are enough.
Step by step
- Set up three values.
nis the size,indexis the slot whose element is being moved, andstartIndexis where the current cycle began, which is also where the carried element sits. Both indexes start at 0. - Repeat
ntimes. Each pass puts one element in its final position, sonpasses handle the whole array, however many cycles it splits into. - Find the destination.
(index + k) % nis where the element atindexmust go. - Swap through a temporary. Exchange
nums[nextIndex]andnums[startIndex]usingtmp. The carried element lands in its target slot, and the displaced element takes its place in the carrier slot. - Advance the cycle. Set
index = nextIndex, because the element now in the hand is the one that came from there, and it must move on. - Detect the end of a cycle. If
index == startIndex, the chain has come back to its beginning. Increase bothstartIndexandindexto start a new cycle at the next position.
The solution in Kotlin
class Solution {
fun rotate(nums: IntArray, k: Int) {
val n = nums.size
var index = 0
var startIndex = 0
repeat(n) {
val nextIndex = (index + k) % n
val tmp = nums[nextIndex]
nums[nextIndex] = nums[startIndex]
nums[startIndex] = tmp
index = nextIndex
if (index == startIndex) {
startIndex++; index++
}
}
}
}
Kotlin details worth a look:
- In-place by default. An
IntArrayparameter refers to the caller's array, so writing tonums[...]changes it for the caller. Parameters can't be reassigned, so there is no way to hand back a new array from a function that returnsUnit. Any copy would be invisible to the caller. repeat(n) { ... }runs its blockntimes. It is a function call with a lambda, not a loop statement, and the lambda is allowed to read and changeindexandstartIndex, which arevardeclarations outside it.valandvar.n,nextIndexandtmpnever change after being set, so they areval. The two indexes change, so they arevar.- The semicolon.
startIndex++; index++puts two statements on one line. In Kotlin, a semicolon is only needed to separate statements that share a line. %and negative values. Here every operand is non-negative, so the remainder is a valid index. For negative operands, Kotlin's%can return a negative number, which would not be a valid index.
Complexity
Time: O(n). The loop runs exactly n times and each pass does a constant amount of work: one remainder, one swap and a comparison.
Space: O(1). The function stores a few integers and one temporary value. All data movement happens inside the input array.
Edge cases and common mistakes
k == nums.size. A full turn changes nothing. Here(index + k) % nequalsindex, so every step swaps a slot with itself and then moves on to the next start.[1, 2, 3]withk = 3stays[1, 2, 3].- A single element. With
n = 1, the destination is the same slot, and the array is unchanged. - Several cycles. When
nandkshare a divisor, as withn = 6andk = 4, the checkindex == startIndexis what keeps the algorithm from stopping after the first cycle. Without it, indexes 1, 3 and 5 would never be moved. - A
kpast the size. The constraints keepkat or belown, but the formula copes with larger values anyway, since%wraps the sum:[1, 2, 3, 4, 5]withk = 7becomes[4, 5, 1, 2, 3], the same ask = 2. - Rotating the wrong way. The expected answer for
[1, 2, 3, 4, 5]andk = 2is[4, 5, 1, 2, 3]. A left rotation would give[3, 4, 5, 1, 2]. - Building a new array. Copying each element to
(i + k) % nin a fresh array is easy, but it usesO(n)extra space and, as noted, the caller wouldn't see the result.
Testing
[1, 2, 3, 4, 5],k = 2gives[4, 5, 1, 2, 3].[1, 2, 3, 4, 5, 6, 7, 8],k = 3gives[6, 7, 8, 1, 2, 3, 4, 5].[1, 2, 3, 4, 5, 6],k = 4gives[3, 4, 5, 6, 1, 2].[1, 2, 3],k = 3gives[1, 2, 3].[7],k = 1gives[7].
