Problem overview
The function rotate receives an array of integers nums and a number k. It rotates the array k times to the right, in place. One rotation moves every number one position to the right, and the last number moves to the front. The function returns nothing: the caller's array is changed through an inout parameter.
For nums = [1, 2, 3, 4, 5] and k = 2, one rotation gives [5, 1, 2, 3, 4] and a second gives [4, 5, 1, 2, 3]. For nums = [1, 2, 3, 4, 5, 6, 7, 8] and k = 3, the result is [6, 7, 8, 1, 2, 3, 4, 5].
The lesson asks for O(n) time and O(1) extra space. The constraints keep k between 1 and the length of the array.
Approach: follow the cycles of positions
After k rotations, the number at position p ends up at position (p + k) % n, where n is the length. The modulo wraps positions that run past the end back to the start.
The simple solutions break the time or space limit. Rotating one step at a time, k times, costs O(n × k). Copying into a second array costs O(n) extra space. To avoid both, move each number straight to its final position, and carry along whatever it displaces.
Start at position 0 and follow the chain of destinations: 0, then k % n, then 2k % n, and so on. The chain eventually returns to its start, forming a cycle. When n and k share a common divisor, one cycle doesn't reach every position. For n = 4 and k = 2 the chain is 0, 2, 0, and positions 1 and 3 form a second cycle. Each cycle needs its own starting point.
The trick of the reference solution is to perform each move as a swap with the cycle's starting position. Position startIndex acts as a holder: the number it holds goes to its destination, the destination's old number lands in the holder, and the next swap moves that number on. Repeating this walks the whole cycle with swaps only, with no temporary array. Every swap puts one number into its final place, so exactly n swaps fix all n numbers, and the loop runs n times.
Here it is on [1, 2, 3, 4, 5] with k = 2:
step 1: [3, 2, 1, 4, 5] index=2 start=0
step 2: [5, 2, 1, 4, 3] index=4 start=0
step 3: [2, 5, 1, 4, 3] index=1 start=0
step 4: [4, 5, 1, 2, 3] index=3 start=0
step 5: [4, 5, 1, 2, 3] index=0 start=0
After step 5, index is back at startIndex, so the cycle is complete and the array holds the answer. Because 5 and 2 share no divisor, this one cycle covers everything.
Step by step
- Record the length and the two pointers.
nisnums.count, a constant.indexis the current position in the cycle andstartIndexis where the current cycle began. Both start at 0 and change, so they arevars. - Loop exactly
ntimes.for _ in 0..<nignores the loop value with_, since only the count matters. Each pass places one number. - Compute the destination.
nextIndex = (index + k) % nis where the number atindexbelongs. - Swap. A tuple assignment exchanges
nums[nextIndex]andnums[startIndex]: the holder's number lands in its destination, and the displaced number goes into the holder. - Move forward.
index = nextIndexcontinues the cycle from the destination. - Detect the end of a cycle. When
index == startIndex, the chain has come back to its start. Increase bothstartIndexandindexby one to begin the next cycle at the next position.
The solution in Swift
func rotate(_ nums: inout [Int], _ k: Int) {
let n = nums.count
var index = 0, startIndex = 0
for _ in 0..<n {
let nextIndex = (index + k) % n
(nums[nextIndex], nums[startIndex]) = (nums[startIndex], nums[nextIndex])
index = nextIndex
if index == startIndex {
startIndex += 1; index += 1
}
}
}
The Swift details worth a closer look:
inoutand&. Arrays are values, so a normal parameter is a copy.inoutlets the function change the caller's array, and the caller marks it with an ampersand:rotate(&nums, 2). The array must be avar.- Tuple assignment swaps without a temporary. The right side
(nums[startIndex], nums[nextIndex])is evaluated completely before the left side is assigned, so both numbers are read first and then written. Swift's ownnums.swapAt(i, j)does the same job. - Declaring two variables on one line.
var index = 0, startIndex = 0declares two separate integers, each with its own initial value. - Semicolons are optional.
startIndex += 1; index += 1puts two statements on one line, and the semicolon separates them. - Empty arrays. The constraints promise at least one element. With an empty array the loop body would never run, because
0..<0is empty, so the function would do nothing.
Complexity
Time: O(n). The loop runs exactly n times with a constant amount of work per pass, regardless of k. This is better than the O(n × k) of repeated single rotations.
Space: O(1). The function keeps n, index, startIndex and nextIndex. No second array is created, and the swaps happen inside nums.
Edge cases and common mistakes
- Several cycles. For
[1, 2, 3, 4]andk = 2, the first cycle visits positions 0 and 2, and only then does theifstart a second cycle at position 1. The result is[3, 4, 1, 2]. Without the cycle restart, positions 1 and 3 would never be moved. kequal to the length. The destination(index + k) % nisindexitself, so each swap exchanges a position with itself and each pass starts a new cycle. The array is unchanged, which is right, becausenrotations bring every number back.[1, 2, 3]withk = 3stays[1, 2, 3].- One element.
[7]withk = 1stays[7]. - Rotating right versus left. The destination is
index + k, which moves numbers to the right. With[1, 2, 3, 4, 5, 6]andk = 4the result is[3, 4, 5, 6, 1, 2]. - Forgetting the modulo. Without
% n,index + kruns past the end of the array, and Swift stops the program with an index-out-of-range error. - Looping until
index == 0. That ends after one cycle only. Counting exactlynswaps is what makes the multi-cycle case work. - Large
k. The lesson keepskat mostn. A largerkwould also work with the modulo in place, but reducing it first withk % nis the usual habit.
Testing
nums = [1, 2, 3, 4, 5],k = 2gives[4, 5, 1, 2, 3].nums = [1, 2, 3, 4, 5, 6, 7, 8],k = 3gives[6, 7, 8, 1, 2, 3, 4, 5].nums = [1, 2, 3, 4],k = 2gives[3, 4, 1, 2].nums = [1, 2, 3],k = 3gives[1, 2, 3].nums = [7],k = 1gives[7].
