Start learning free

LESSON 230 OF 344 · TWO POINTERS

Rotate Array by One in Java: In Place with O(1) Space

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

    JAVA · TWO POINTERS

    Rotate Array 1 in Java, explained

    Problem overview

    The method rotate receives an int[] called nums and moves every element one position to the right. The last element wraps around to the front. The method returns nothing: it must change the array it was given, without building a second array.

    For nums = [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, meaning a fixed number of extra variables, whatever the array's size.

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

    Every element except the last moves one slot right, to the place its right neighbour occupies. The last element has no slot to its right, so it goes to index 0. The difficulty is the order of the writes: moving an element onto its neighbour's slot overwrites the neighbour.

    Two decisions solve it:

    • Save the last element in a variable before anything is overwritten, since its slot is the first one to be reused.
    • Do the shifting from right to left. Copying nums[i - 1] into nums[i] overwrites nums[i], and by then that value has already been copied one slot further right, or was saved at the start. Nothing is lost.

    Tracing [1, 2, 3, 4, 5]: save last = 5. Then the array goes through [1, 2, 3, 4, 4], [1, 2, 3, 3, 4], [1, 2, 2, 3, 4] and [1, 1, 2, 3, 4]. Finally index 0 gets the saved 5, giving [5, 1, 2, 3, 4].

    Step by step

    1. Record the length in n and save the last element in last, using nums[n - 1]. This is the only value that would otherwise be lost.
    2. Loop backwards with i from n - 1 down to 1. The condition i > 0 stops the loop before index 0, because index 0 has no left neighbour to copy from.
    3. Copy each neighbour to the right. Assign nums[i] = nums[i - 1]. The right-to-left order guarantees that nums[i - 1] still holds its original value when it is read.
    4. Place the saved value. After the loop, set nums[0] = last. The old first element was already copied to index 1 in the final iteration, so index 0 is free to overwrite.

    The solution in Java

    class Solution {
    public void rotate(int[] nums) {
        int n = nums.length;
        int last = nums[n - 1];
        for (int i = n - 1; i > 0; i--) {
            nums[i] = nums[i - 1];
        }
        nums[0] = last;
    }
}

    The Java details worth a closer look:

    • Arrays are passed by reference. The method gets a reference to the caller's array, so writes to nums[i] change the caller's data. That is why a void method can deliver its result. Assigning a new array to the parameter, such as nums = new int[n], would change only the local variable and the caller would see no rotation.
    • Primitive values are copied. int last = nums[n - 1] copies the number into its own variable. Later writes to the array do not affect it.
    • length has no parentheses. For arrays it is a field, nums.length, while String and collections use methods such as length() and size().
    • Indexes are checked. Java throws ArrayIndexOutOfBoundsException for an index outside 0 to length - 1 rather than touching other memory.

    Complexity

    Time: O(n). The loop runs n - 1 times and does one assignment each time.

    Space: O(1). The code uses n, last and i, three integers, whatever the length of the array.

    Edge cases and common mistakes

    • One element. For [7] the loop body never runs, and nums[0] = last writes back the same value. The array is unchanged, which is correct.
    • Two elements. [1, 2] becomes [2, 1].
    • An empty array. nums[n - 1] is nums[-1], which throws ArrayIndexOutOfBoundsException. The lesson's tests don't use an empty array, but a version meant for general use would begin with if (n == 0) return;.
    • Shifting left to right. A loop that runs upwards and copies nums[i] = nums[i - 1] smears the first value across the whole array: [1, 2, 3, 4, 5] turns into [1, 1, 1, 1, 1].
    • Forgetting to save the last element. Without last, the value 5 is overwritten by the first copy and there is nothing to put at index 0.
    • Looping down to i >= 0. The final iteration would read nums[-1] and throw.
    • Allocating a new array. A copy gives the right values, but it uses O(n) extra space, which the statement forbids.

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