Start learning free

LESSON 258 OF 438 · TWO POINTERS

Rotate Array in Java: 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

    JAVA · TWO POINTERS

    Rotate Array in Java, explained

    Problem overview

    The method rotate(int[] nums, int k) shifts the array k places to the right, in place. One rotation moves every number one position right and brings the last number to the front. The method returns nothing: the caller sees the change because a Java array is passed by reference, so nums is the caller's own array.

    With nums = [1, 2, 3, 4, 5] and k = 2, one rotation gives [5, 1, 2, 3, 4] and the second gives [4, 5, 1, 2, 3]. In the second example, [1, 2, 3, 4, 5, 6, 7, 8] with k = 3 becomes [6, 7, 8, 1, 2, 3, 4, 5]. The statement asks for O(n) time and O(1) extra space, with 1 <= k <= nums.length.

    Approach: move each element straight to its final slot

    Rotating one step at a time, k times, costs O(n * k). Copying into a second array is O(n) but uses O(n) extra memory. Both break the budget.

    A rotation by k has a simple rule: the element at position i ends up at position (i + k) % n. The modulo wraps positions past the end back to the front. So each element can go directly to its destination. The only problem is that the destination is occupied. If you overwrite it, you lose the value that was there.

    The fix is to carry one value in your hand. Take the element at position 0 and put it at (0 + k) % n, picking up the element that was there. That element belongs k places further on, so put it there and pick up the next one, and so on. The hand is just slot startIndex of the array itself, and a swap does both jobs at once: it drops the carried value into its destination and picks up the displaced one. No extra array is needed.

    The chain of positions 0, k, 2k, and so on (all modulo n) eventually returns to its start. That loop is a cycle. When the cycle closes, the carried value belongs exactly where it is, and the swap with itself changes nothing.

    Here is [1, 2, 3, 4, 5] with k = 2. The cycle visits 0, 2, 4, 1, 3 and returns to 0, so one cycle covers every position:

    [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, cycle closed

    When n and k share a factor, one cycle is not enough. With n = 6 and k = 2, the chain 0, 2, 4 returns to 0 after three steps and never touches positions 1, 3 and 5. They form a second cycle, which needs its own starting point. The array [1, 2, 3, 4, 5, 6] goes through these states:

    [3, 2, 1, 4, 5, 6]   index = 2, start = 0
[5, 2, 1, 4, 3, 6]   index = 4, start = 0
[5, 2, 1, 4, 3, 6]   index = 0, start = 0   (cycle closed, move start to 1)
[5, 4, 1, 2, 3, 6]   index = 3, start = 1
[5, 6, 1, 2, 3, 4]   index = 5, start = 1
[5, 6, 1, 2, 3, 4]   index = 1, start = 1   (cycle closed)

    Every swap puts one more element into its final slot, and the self-swap that closes a cycle finishes the carried one. So exactly n swaps are needed in total, whatever the number of cycles. That is why the loop simply runs n times, with no cycle counting and no gcd computation.

    Step by step

    1. Declare the state. n is the length, index is the position of the element about to move, and startIndex is the first slot of the current cycle, which holds the carried value.
    2. Loop exactly n times. Each pass fixes one element, so this is the whole job. The variable c only counts.
    3. Find the destination as nextIndex = (index + k) % n, wrapping past the end.
    4. Swap nums[nextIndex] with nums[startIndex] through tmp. The carried value lands in its slot, and the old occupant becomes the new carried value.
    5. Move on by setting index to nextIndex. The displaced element now sits in the hand, and its own destination is k places after index.
    6. Detect a closed cycle. When index is back at startIndex, move both to the next slot, so the following passes start a fresh cycle. If there was only one cycle, the loop ends right after this anyway.

    The solution in Java

    class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length, index = 0, startIndex = 0;
        for (int c = 0; c < n; c++) {
            int nextIndex = (index + k) % n;
            int tmp = nums[nextIndex];
            nums[nextIndex] = nums[startIndex];
            nums[startIndex] = tmp;
            index = nextIndex;
            if (index == startIndex) {
                startIndex++; index++;
            }
        }
    }
}

    The Java details worth a look:

    • In place means the caller's array. The method receives a copy of the reference, not a copy of the array. Writing into nums[...] changes the array the caller holds, which is why void is enough.
    • One declaration, three variables. int n = nums.length, index = 0, startIndex = 0; declares three int variables in one statement. Each has its own initializer.
    • The swap needs a temporary. Java has no tuple assignment, so tmp holds one value while the other is copied over. It is declared inside the loop, so it exists only during one pass.
    • % and int range. index + k is at most about twice the array length, far from the int limit, and both operands are non-negative, so % never gives a negative result here.
    • startIndex++; index++; on one line is two statements. Both variables must move together, or the next cycle would start from the wrong slot.

    Complexity

    Time: O(n). The loop runs n times, and each pass does a constant amount of work: one modulo, one swap, one comparison.

    Space: O(1). The method uses a handful of int variables whatever the size of nums. The carried value lives inside the array.

    Edge cases and common mistakes

    • A single element. With n = 1, the destination is the element's own slot, the cycle closes at once and the array stays the same.
    • k equal to the length. A full turn changes nothing. Here nextIndex always equals index, so every pass is a self-swap that closes a cycle, and startIndex walks across the array. The array is unchanged.
    • Shared factors. [1, 2, 3, 4, 5, 6] with k = 2 has two cycles. A version without the startIndex restart would never reach positions 1, 3 and 5, so the array would come out wrong.
    • Stopping when index == 0. That ends the first cycle only. Counting passes up to n is what covers every cycle.
    • Rotating the wrong way. The destination is (index + k) % n. Using index - k would rotate left, and could go negative, because Java's % keeps the sign of the dividend.
    • Larger k. The statement keeps k at most the array length. Because of the modulo, [1, 2, 3, 4, 5, 6] with k = 8 also gives [5, 6, 1, 2, 3, 4], the same as k = 2.

    Testing

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