Start learning free

LESSON 257 OF 414 · TWO POINTERS

Rotate Array by One to the Right in Scala: In Place in O(n)

Practice O(n) Read the full explanation

Given an array of integers nums, rotate it in-place by one position to its right.

Do not allocate extra space for another array. You must do this by modifying directly the input array with O(1) auxiliary space.


Example 1:

Input: nums = [1, 2, 3, 4, 5]
Output: [5, 1, 2, 3, 4]

Example 2:

Input: nums = [4, -2, 13, 1]
Output: [1, 4, -2, 13]

Note:

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


STEP 1 OF 4
    Ctrl + Enter to check

    SCALA · TWO POINTERS

    Rotate Array 1 in Scala, explained

    Problem overview

    The method rotate(nums: Array[Int]) must rotate the array 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: the caller's array is the output.

    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, so building a second array is not allowed.

    Approach: save the last element, shift, then place it

    The element at the end has no slot to move into, so it is saved in a variable first. Then every other element moves one slot to the right. Finally the saved value goes into slot 0.

    The order of the shifts matters. Moving elements to the right means each slot receives the value from its left neighbour. If you go from left to right, nums(1) = nums(0) overwrites the second element before it has been moved, and the copy keeps spreading: [1, 2, 3, 4, 5] would end up as [5, 1, 1, 1, 1]. If you go from right to left, each assignment overwrites a value that has already been copied one slot further right, so nothing is lost.

    [1, 2, 3, 4, 5]   last = 5
[1, 2, 3, 4, 4]   nums(4) = nums(3)
[1, 2, 3, 3, 4]   nums(3) = nums(2)
[1, 2, 2, 3, 4]   nums(2) = nums(1)
[1, 1, 2, 3, 4]   nums(1) = nums(0)
[5, 1, 2, 3, 4]   nums(0) = last

    Step by step

    1. Save what you need. val n = nums.length records the length, and val last = nums(n - 1) keeps a copy of the final element before the shifting overwrites it.
    2. Shift from right to left. A for loop runs i from n - 1 down to 1, using the descending range n - 1 until 0 by -1.
    3. Copy the left neighbour. Inside the loop, nums(i) = nums(i - 1) moves one element a slot to the right. Because the loop goes right to left, nums(i - 1) hasn't been overwritten yet when it is read.
    4. Place the saved element. After the loop, nums(0) = last wraps the old last element to the front. Slot 0 is free to overwrite, since the loop's final iteration already copied its old content to slot 1.

    The solution in Scala

    class Solution {
    def rotate(nums: Array[Int]): Unit = {
        val n = nums.length
        val last = nums(n - 1)
        for (i <- n - 1 until 0 by -1) {
            nums(i) = nums(i - 1)
        }
        nums(0) = last
    }
}

    The Scala details worth knowing:

    • Descending ranges. until excludes its end, and by -1 makes the range count down. For n = 5, the range 4 until 0 by -1 contains 4, 3, 2, 1. Leaving out by -1 gives an empty range, because 4 until 0 counts upward and has no elements.
    • Arrays are mutable. The method changes the array it receives, and the caller sees the change. That is why the return type is Unit, Scala's "nothing useful" result.
    • nums(i) = x is the syntax for storing into an array element. Reading uses the same parentheses: nums(i - 1).
    • val versus var. n and last never change after they are set, so they are vals. The loop variable i is created fresh for each iteration.
    • Operator precedence. n - 1 until 0 by -1 reads as ((n - 1) until 0) by -1, so no extra parentheses are needed.

    Complexity

    Time: O(n). The loop runs n - 1 times and each iteration does one read and one write.

    Space: O(1). The only extra memory is n, last and the loop variable. The array itself is modified rather than copied.

    Edge cases and common mistakes

    • One element. [9] stays [9]. The range 0 until 0 by -1 is empty, and nums(0) = last writes the same value back.
    • Two elements. [1, 2] becomes [2, 1].
    • An empty array. nums(n - 1) becomes nums(-1), which throws an ArrayIndexOutOfBoundsException. The statement does not describe empty input, so the lesson's code does not guard against it. Add a check on nums.length if you need one.
    • Looping left to right. The first value is copied over the whole array, as in the [5, 1, 1, 1, 1] result above.
    • Forgetting to save the last element. It is overwritten by the first assignment, and nothing is left to put at the front.
    • Allocating a second array. It works, but it breaks the O(1) space limit.

    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].
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free