Problem overview
The function rotate receives an IntArray called nums and moves every element one position to the right. The last element wraps around to the front. The change must happen inside nums itself, with no second array, and the function returns nothing.
For [1, 2, 3, 4, 5] the array becomes [5, 1, 2, 3, 4]. For [4, -2, 13, 1] it becomes [1, 4, -2, 13]. The statement asks for O(n) time and O(1) auxiliary space.
Approach: save the last element, shift, then put it first
Copying into a new array would be easy but costs O(n) space, which the statement rules out. Doing it in place has one danger: assigning nums[i] = nums[i - 1] overwrites the old value at i. That's harmless only if the old value has already been moved or saved.
The last element is the one that would be lost first, since nothing to its right takes its place. So the plan has three parts:
- Save the last element in a variable.
- Shift every other element one slot right. Work from right to left, so that each read of
nums[i - 1]happens before that slot is overwritten. - Write the saved value into slot 0.
Going left to right instead would copy the first element over everything: nums[1] = nums[0], then nums[2] = nums[1], which is already the first element, and so on. For [1, 2, 3] the loop would leave [1, 1, 1].
Here is [1, 2, 3, 4, 5] step by step. The saved value is 5. With i = 4, nums[4] = nums[3] gives [1, 2, 3, 4, 4]. Then i = 3 gives [1, 2, 3, 3, 4], i = 2 gives [1, 2, 2, 3, 4], and i = 1 gives [1, 1, 2, 3, 4]. Finally slot 0 receives 5, and the array is [5, 1, 2, 3, 4].
Step by step
- Record the size and the last element.
nisnums.size, andlastisnums[n - 1]. Both arevals because neither changes. The copy oflastis what stops that value from being lost. - Loop from
n - 1down to 1.n - 1 downTo 1is a descending range that includes both ends. Index 0 is excluded because nothing sits to its left. - Shift one slot.
nums[i] = nums[i - 1]moves each element one place right. Because the loop runs right to left,nums[i - 1]still holds its original value when it is read. - Put the saved element first. After the loop, slot 0 still holds the original first element, but a copy of it now lives in slot 1, so slot 0 is free to overwrite with
last.
The solution in Kotlin
class Solution {
fun rotate(nums: IntArray) {
val n = nums.size
val last = nums[n - 1]
for (i in n - 1 downTo 1) {
nums[i] = nums[i - 1]
}
nums[0] = last
}
}
Kotlin details worth knowing:
- Arrays are passed by reference. The function receives the caller's array, not a copy, so writing to
nums[i]changes the caller's data. That is why the function needs no return value. The parameternumsitself is read-only in Kotlin: you can change its elements but you can't assign a new array to the name. downTo.5 downTo 1counts 5, 4, 3, 2, 1. A range written5..1is empty, because..only counts upward. The expressionn - 1 downTo 1is parsed as(n - 1) downTo 1, since arithmetic binds tighter than an infix function call.- The loop variable is a
val. Inside thefor,ican be read but not assigned. - Return type. A function with no declared return type returns
Unit, Kotlin's "nothing useful" value. Noreturnstatement is needed.
Complexity
Time: O(n). The loop does n - 1 assignments, and the rest is constant work.
Space: O(1). The function stores two integers, n and last, plus the loop variable. The array is changed in place.
Edge cases and common mistakes
- One element.
[7]stays[7]. The range0 downTo 1is empty, so the loop doesn't run, andnums[0] = lastwrites the same value back. - Two elements.
[1, 2]becomes[2, 1]. - An empty array.
nums[n - 1]isnums[-1], which throwsArrayIndexOutOfBoundsException. The statement gives no empty input; if you needed to support one, an earlyreturnwhennums.isEmpty()would fix it. - Looping left to right. Every slot in the loop's range ends up holding the first element, as shown above.
- Forgetting to save the last element. Reading
nums[n - 1]after the loop returns the shifted value, not the original, and the wrap-around gives the wrong number. - Starting the loop at
n.nums[n]is outside the array and throws. - Negative values. They move like any other value;
[4, -2, 13, 1]becomes[1, 4, -2, 13].
Testing
[1, 2, 3, 4, 5]becomes[5, 1, 2, 3, 4].[4, -2, 13, 1]becomes[1, 4, -2, 13].[7]stays[7].[1, 2]becomes[2, 1].