Problem overview
The method rotate receives an array of integers, nums, and must rotate it by one position to the right, in place. Every element moves one slot to the right, and the last element wraps around to the front. The method returns nothing: it changes the array it was given. It may not allocate a second array, so the extra space is O(1), and the time is O(n).
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].
Approach: save the last element, shift, then drop it in front
Copying into a new array would be easy, but the lesson forbids it. The in-place version has one trap: if you copy each element to the right slot, you may overwrite a value before you have used it.
Take [1, 2, 3] and try shifting left to right. Writing nums[1] = nums[0] gives [1, 1, 3], and the original 2 is gone. The fix is to go the other way, from the right end to the left. Then the slot you overwrite is always one whose old value has already been moved on.
That leaves the last element, which has nowhere to go because the first move would overwrite it. So save it in a variable before the loop, and write it into slot 0 afterwards.
On [1, 2, 3, 4, 5]: save last = 5. Then nums[4] = nums[3] gives [1, 2, 3, 4, 4], nums[3] = nums[2] gives [1, 2, 3, 3, 4], and so on down to nums[1] = nums[0], which gives [1, 1, 2, 3, 4]. Finally nums[0] = last gives [5, 1, 2, 3, 4].
Step by step
- Record the size and the last element.
nisnums.count, andlastisnums[n - 1], both constants withlet. This copy is the only value that would be lost. - Loop from the right. The loop variable
igoes fromn - 1down to 1. - Shift one slot. Inside the loop,
nums[i]takes the value ofnums[i - 1]. Each read happens before anything overwrites that slot. - Wrap around. After the loop, slot 0 is free, since its old value was copied to slot 1. Assign
lastto it.
The solution in Swift
class Solution {
func rotate(_ nums: inout [Int]) {
let n = nums.count
let last = nums[n - 1]
for i in stride(from: n - 1, to: 0, by: -1) {
nums[i] = nums[i - 1]
}
nums[0] = last
}
}
Swift details worth knowing:
inout. Arrays are value types in Swift, so a plain parameter would be a copy and changes to it would not reach the caller.inout [Int]makes the method work on the caller's array, and the caller writessolution.rotate(&nums). The array must be declared withvar.stride(from:to:by:). A range like1..<ncan't count downward.stridecan:stride(from: n - 1, to: 0, by: -1)producesn - 1,n - 2, and so on, and stops beforeto. Becausetois excluded, the last value ofiis 1. Forn = 5the values are 4, 3, 2, 1. The inclusive form isstride(from:through:by:).- A one-element array. With
n = 1the stride has no values (from 0 to 0 excluded), so the loop doesn't run, andnums[0] = lastwrites the same value back. - Bounds are checked. Reading
nums[-1]stops the program with a run-time error, which matters for the next section.
Complexity
Time: O(n). The loop makes n - 1 assignments, and everything else is constant work.
Space: O(1). The extra memory is n, last and the loop variable, however long the array is.
Edge cases and common mistakes
- Looping left to right. This copies the first value across the whole array:
[1, 2, 3]would turn into[1, 1, 1]before the wrap-around line runs. - Not saving the last element. Without
last, the wrap-around has nothing to write. - Two elements.
[1, 2]becomes[2, 1]. - One element.
[9]stays[9]. - An empty array.
nums[n - 1]isnums[-1], which crashes the program at run time. The code assumes at least one element. A guard such asif n == 0 { return }at the top would make it safe. - Stopping the stride one step early or late. With
to: 1the element at index 1 is never written, and withto: -1the loop readsnums[-1]and crashes. - Negative values. They are moved like any other number, as in the second example.
Testing
[1, 2, 3, 4, 5]becomes[5, 1, 2, 3, 4].[4, -2, 13, 1]becomes[1, 4, -2, 13].[1, 2]becomes[2, 1].[9]stays[9].
