Start learning free

LESSON 265 OF 445 · TWO POINTERS

Rotate Array in Rust: O(n) Time, O(1) Space with Cycles

Practice O(n) Read the full explanation

Given an array of integers nums, rotate it k times to its right, in place, using O(1) extra memory.

One rotation to the right moves every number one position to the right, and the last number moves to the front.

Your function rearranges the numbers inside nums itself, without building a new array: the output in the examples is nums after the call. (In Rust the function takes nums by value, so it returns that same vector, rotated.)

Example 1:

Input: nums = [1, 2, 3, 4, 5], k = 2
Output: [4, 5, 1, 2, 3]
Explanation: After 1 rotation: [5, 1, 2, 3, 4]. After 2 rotations: [4, 5, 1, 2, 3].

Example 2:

Input: nums = [1, 2, 3, 4, 5, 6, 7, 8], k = 3
Output: [6, 7, 8, 1, 2, 3, 4, 5]

Constraints:

  • 1 <= nums.length <= 3 * 104
  • 1 <= nums[i] <= 231 - 1
  • 1 <= k <= nums.length
Note:

Your algorithm should run in O(n) time and use O(1) extra space.

STEP 1 OF 8
    Ctrl + Enter to check

    RUST · TWO POINTERS

    Rotate Array in Rust, explained

    Problem overview

    The function rotate receives a vector nums and an integer k. It rotates the vector k times to the right and returns it. One rotation moves every number one position to the right, and the last number wraps around to the front. The vector has between 1 and 30,000 elements, and k is between 1 and the length.

    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], which is the answer. For [1, 2, 3, 4, 5, 6, 7, 8] with k = 3, the answer is [6, 7, 8, 1, 2, 3, 4, 5].

    The lesson asks for O(n) time and O(1) extra space. That rules out two easy answers: rotating one step at a time k times, which is O(n * k), and building a second vector, which uses O(n) extra space.

    Approach: move each element straight to its final slot

    After k rotations to the right, the element at position i ends up at position (i + k) % n, where n is the length. The remainder makes positions that run past the end wrap around to the front. So every element has one known destination.

    The difficulty is that moving an element into its destination overwrites the element living there. The standard trick is to carry the displaced element along. Take the element at position 0 and put it where it belongs, (0 + k) % n. Pick up the element that was there, and put it where it belongs. Keep going until the chain returns to position 0. Positions visited this way form a cycle.

    A single cycle doesn't always reach every position. With n = 4 and k = 2, the chain visits 0, 2, and back to 0, and never touches 1 or 3. In general, the number of independent cycles is the greatest common divisor of n and k, so when it is more than 1, the algorithm must start a new cycle at the next position when one closes.

    The lesson expresses "carry" with swaps. The slot start_index acts as the hand: it holds the element being carried. A swap between start_index and the destination drops the carried element into place and puts the displaced one into the hand.

    Here is the trace for [1, 2, 3, 4, 5] with k = 2, showing the vector and index after each swap:

    [3, 2, 1, 4, 5] index=2
[5, 2, 1, 4, 3] index=4
[2, 5, 1, 4, 3] index=1
[4, 5, 1, 2, 3] index=3
[4, 5, 1, 2, 3] index=0

    In the last row, the destination is position 0 itself, so the swap does nothing: the element in the hand is already where it belongs. The cycle has closed. The five iterations produced the right answer.

    Step by step

    1. Set up the state. n is the length. index is where the carried element came from, and start_index is the slot that acts as the hand and also marks where the current cycle began. Both are usize and start at 0.
    2. Loop exactly n times. Each iteration places one element, and a swap with itself counts as an iteration. The underscore discards the loop counter, which isn't needed.
    3. Compute the destination. next_index = (index + k as usize) % n. The cast converts k to usize so it can be added to an index.
    4. Swap positions next_index and start_index with the vector's swap method. The carried element lands in its destination, and the displaced one moves into the hand.
    5. Move on. Set index = next_index, since the element now in the hand came from there.
    6. Detect a closed cycle. When index == start_index, the chain is back at the beginning. Add 1 to both index and start_index to start a fresh cycle at the next position.

    The solution in Rust

    impl Solution {
    fn rotate(mut nums: Vec<i32>, k: i32) -> Vec<i32> {
        let n = nums.len();
        let mut index: usize = 0;
        let mut start_index: usize = 0;
        for _ in 0..n {
            let next_index = (index + k as usize) % n;
            nums.swap(next_index, start_index);
            index = next_index;
            if index == start_index {
                index += 1;
                start_index += 1;
            }
        }
        nums
    }
}

    The function returns [4, 5, 1, 2, 3] for the first example, [6, 7, 8, 1, 2, 3, 4, 5] for the second, and [3, 4, 1, 2] for [1, 2, 3, 4] with k = 2, a case with two cycles.

    The Rust details worth a closer look:

    • mut nums in the signature. The parameter is owned and mutable, so swap can change it, and the same vector is returned. No second vector is allocated, which is what keeps the extra space at O(1).
    • swap takes two indices. nums.swap(a, b) exchanges two elements in place, and a == b is allowed and does nothing. The algorithm relies on that for the last step of each cycle. An index out of bounds panics.
    • k as usize. The as cast never fails. For the positive values the constraints allow, it is exact. A negative i32 would wrap to a huge usize, which is one reason the constraints matter here.
    • Mixing integer types. index + k would be a compile error, because usize and i32 don't mix. The cast makes both sides usize.
    • The remainder keeps the index in range. % n yields a value from 0 to n - 1, so swap never panics. After the last iteration, index may equal n, but it is no longer used.
    • A standard-library shortcut. nums.rotate_right(k % n) does the same job in one call. The lesson builds the algorithm by hand to practice cycle-following.

    Complexity

    Time: O(n). The loop runs exactly n times, and each iteration does a remainder, a swap and a comparison, all constant work. Every element is moved once.

    Space: O(1). Only n, index, start_index and next_index are stored, however long the vector is.

    Edge cases and common mistakes

    • One element. [7] with k = 1 gives [7]. The only swap is the element with itself.
    • k equal to the length. [1, 2, 3] with k = 3 returns [1, 2, 3]: a full turn changes nothing. Every destination is the element's own position, and each iteration closes a one-element cycle.
    • Several cycles. [1, 2, 3, 4, 5, 6] with k = 4 has two cycles, since the greatest common divisor of 6 and 4 is 2. The result is [3, 4, 5, 6, 1, 2]. A version that follows only one cycle would leave half of the vector untouched.
    • Two elements. [1, 2] with k = 1 gives [2, 1].
    • Looping until index == start_index only once. That finds one cycle. The loop must run n times in total, restarting at the next position when a cycle closes.
    • Rotating the wrong way. A rotation to the right moves the last element to the front. The destination of position i is i + k, not i - k.
    • Subtracting from a usize. Computing index - k on unsigned numbers underflows. Using + k and %, as the lesson does, avoids any subtraction.

    Testing

    • nums = [1, 2, 3, 4, 5], k = 2 gives [4, 5, 1, 2, 3].
    • nums = [1, 2, 3, 4, 5, 6, 7, 8], k = 3 gives [6, 7, 8, 1, 2, 3, 4, 5].
    • nums = [1, 2, 3, 4], k = 2 gives [3, 4, 1, 2].
    • nums = [1, 2, 3, 4, 5, 6], k = 4 gives [3, 4, 5, 6, 1, 2].
    • nums = [7], k = 1 gives [7].
    • nums = [1, 2, 3], k = 3 gives [1, 2, 3].
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free