Problem overview
The method rotate(nums: Array[Int], k: Int): Unit rotates the array nums to the right k times, in place. One rotation moves every number one position to the right, and the last number moves to the front. The method returns nothing: the caller sees the change in the same array.
For nums = [1, 2, 3, 4, 5] and k = 2 the first rotation gives [5, 1, 2, 3, 4] and the 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 constraints are 1 <= k <= nums.length and up to 30,000 elements. The lesson asks for O(n) time and O(1) extra space, so copying the array into a second one isn't allowed, and neither is doing k separate one-step rotations, which would cost O(n × k).
Approach: follow each element to its destination
Rotating right by k sends the element at position i to position (i + k) % n, where n is the length. The remainder operator wraps positions past the end back to the front. In the first example, the 1 at position 0 ends at position 2, and the 4 at position 3 ends at position (3 + 2) % 5 = 0.
If you move an element to its destination, you overwrite the element that was there, so that one must be moved next, and so on. Following that chain from position 0 visits positions 0, 2, 4, 1, 3 and returns to 0: a cycle. When n and k share a divisor, one cycle doesn't reach every position. With n = 6 and k = 2 the chain from 0 visits only 0, 2, 4. The positions 1, 3 and 5 form a second cycle. In general the number of cycles is the greatest common divisor of n and k, and each has the same length, so together they cover all n positions.
The solution handles this by walking along a cycle and carrying one value with it. The carried value always sits at startIndex. Each step swaps it into its destination nextIndex, and the value that was there becomes the new carried value. When the walk gets back to startIndex, the cycle is closed, and the next cycle starts one position to the right.
Here is [1, 2, 3, 4, 5] with k = 2:
step 1: next=2 [3, 2, 1, 4, 5]
step 2: next=4 [5, 2, 1, 4, 3]
step 3: next=1 [2, 5, 1, 4, 3]
step 4: next=3 [4, 5, 1, 2, 3]
step 5: next=0 [4, 5, 1, 2, 3]
In step 1, the 1 goes to position 2 and the 3 becomes the carried value at position 0. Step 2 puts the 3 at position 4 and carries the 5. Step 3 puts the 5 at position 1, step 4 puts the 2 at position 3, and the carried 4 is left at position 0 in step 5, where the swap exchanges position 0 with itself. The cycle is complete, and every element is in place after exactly n = 5 steps.
With six elements, [1, 2, 3, 4, 5, 6] and k = 2, step 3 closes the first cycle at position 0 and the walk moves to startIndex = 1. Steps 4 to 6 rotate the second cycle, and the result is [5, 6, 1, 2, 3, 4]. The loop count is still n, because every step settles exactly one element, whichever cycle it belongs to.
Step by step
- Record the length and two positions.
nis the length,indexis where the walk is, andstartIndexis where the current cycle began and where the carried value lives. Both positions start at 0. - Loop exactly
ntimes. Each pass settles one element, sonpasses settle all of them. The loop variable isn't used, so it is written_. - Compute the destination.
nextIndex = (index + k) % nis where the element atindexbelongs. The remainder wraps it around. - Swap through a temporary. Put the carried value (at
startIndex) intonextIndexand move the old occupant ofnextIndexintostartIndex. It is the new carried value. - Advance.
index = nextIndexcontinues the walk from the destination just filled. - Detect a closed cycle. When
index == startIndex, the walk has returned to its beginning. Increase bothstartIndexandindexby one to begin the next cycle there. Ifnandkshare no divisor, this happens only after the last step.
The solution in Scala
class Solution {
def rotate(nums: Array[Int], k: Int): Unit = {
val n = nums.length
var index, startIndex = 0
for (_ <- 0 until n) {
val nextIndex = (index + k) % n
val tmp = nums(nextIndex)
nums(nextIndex) = nums(startIndex)
nums(startIndex) = tmp
index = nextIndex
if (index == startIndex) {
startIndex += 1; index += 1
}
}
}
}
The Scala details worth a closer look:
var index, startIndex = 0. This declares two separate variables and gives each the value 0. Both arevarbecause the algorithm reassigns them.for (_ <- 0 until n). The range0 until nexcludesn, so the body runsntimes. The underscore says the loop value is ignored.- Arrays are mutable.
nums(nextIndex) = ...changes the array that the caller passed in, which is how an in-place method with aUnitresult delivers its answer. Reading uses the same parentheses:nums(nextIndex). Square brackets are for types, not indices. - The method's return type is
Unit. There is no value to return. The last expression of the body is theforloop, which has typeUnit. - Two statements on one line.
startIndex += 1; index += 1uses a semicolon to put two statements on one line. Scala normally ends a statement at the line break. - Integer arithmetic.
Intis 32 bits and%keeps the sign of its left operand. Here both operands are non-negative, so the result is between 0 andn - 1.index + kis at most about twice the length of the array, so overflow isn't a concern for this problem.
Complexity
Time: O(n). The loop runs exactly n times, and each pass does a constant amount of work: a remainder, one swap and two comparisons.
Space: O(1). The method uses a handful of integers and one temporary value. The array is modified in place.
Edge cases and common mistakes
- A single element. With
nums = [7]andk = 1,nextIndexis 0, the swap exchanges the element with itself, and the array stays[7]. kequal to the length. A full turn changes nothing. HerenextIndexalways equalsindex, so every step is a self-swap followed by moving to the next start, and[1, 2, 3, 4]withk = 4stays as it is.- A common divisor of
nandk. For[1, 2, 3, 4, 5, 6]withk = 2, ork = 3, one walk doesn't reach every position. Without thestartIndexshift, the second cycle would never be rotated, and the result would be partly unrotated. - Stopping when the walk returns to the start. A
whileloop that ends at the first return handles only one cycle. Countingnplacements covers all cycles with a single loop. - Rotating left by mistake. The destination is
(index + k) % n, not(index - k) % n. The latter is a left rotation and can give negative remainders. - Returning a new array. The method's type is
Unit, so a rotated copy that isn't written back intonumsis lost.
Testing
nums = [1, 2, 3, 4, 5],k = 2gives[4, 5, 1, 2, 3].nums = [1, 2, 3, 4, 5, 6],k = 2gives[5, 6, 1, 2, 3, 4].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 = 4gives[1, 2, 3, 4].nums = [7],k = 1gives[7].
