Start learning free

LESSON 233 OF 347 · TWO POINTERS

Rotate Array by One in C#: In-Place Shift 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

    C# · TWO POINTERS

    Rotate Array 1 in C#, explained

    Problem overview

    The method Rotate receives an int[] nums and rotates it one position to the right, in place. The last element wraps around to the front and every other element slides one slot to the right. The method returns void: the result is the modified array itself.

    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 no second array is allowed.

    Approach: save the last element, then shift from the right

    Copying into a new array would be easy, but the problem forbids it. We have to move elements inside the same array, and the order of the moves matters.

    Suppose you tried to shift left to right: nums[1] = nums[0], then nums[2] = nums[1], and so on. The first assignment overwrites the old nums[1] before anyone has read it, and the next assignment then copies the value that was just written. The array ends up filled with copies of the first element.

    The fix is to go from right to left. Each assignment nums[i] = nums[i - 1] overwrites a slot whose old value has already been copied one place to the right, so nothing is lost. The one value that would be overwritten without being copied is the last element, because the very first assignment, nums[n - 1] = nums[n - 2], destroys it. So it is saved in a variable first and written to index 0 at the end.

    On [1, 2, 3, 4, 5]: save last = 5. Then the array goes [1, 2, 3, 4, 4], [1, 2, 3, 3, 4], [1, 2, 2, 3, 4], [1, 1, 2, 3, 4]. Finally index 0 receives 5, giving [5, 1, 2, 3, 4].

    Step by step

    1. Store the length and the last element. n is nums.Length, and last is nums[n - 1]. This copy is the only extra storage the method needs.
    2. Loop from n - 1 down to 1. The loop variable i goes right to left, and the condition i > 0 stops before index 0, which has no left neighbour to copy from.
    3. Copy each element one slot right. nums[i] = nums[i - 1] reads the old value at i - 1, which no earlier iteration has touched, and writes it into slot i.
    4. Place the saved element. After the loop, index 0 still holds its original value, which was already copied to index 1. So it is free to be overwritten with last.

    The solution in C#

    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;
    }
}

    Details about C# worth knowing here:

    • Arrays are reference types. The parameter nums refers to the caller's array, not a copy. Writing into nums[i] changes the array the caller sees, which is why the method can return void. Assigning a new array to the parameter itself (nums = new int[...]) would only change the local variable and would not rotate anything for the caller.
    • Index errors throw. C# checks every index at run time. Reading nums[-1] or nums[nums.Length] throws IndexOutOfRangeException rather than silently reading other memory.
    • Length is a property of arrays: no parentheses.
    • i-- decrements the loop variable after each pass, so the loop visits n - 1, n - 2, ..., 1.

    Complexity

    Time: O(n). The loop makes n - 1 assignments, and the rest is a fixed number of operations.

    Space: O(1). Only n, last and i are extra, whatever the array size.

    Edge cases and common mistakes

    • A single element. With [7], n - 1 is 0, so the loop body never runs, and nums[0] = last writes the same value back. The array stays [7].
    • Two elements. [1, 2] becomes [2, 1]: last is 2, the loop copies nums[0] into nums[1], and then index 0 gets 2.
    • An empty array. This code reads nums[n - 1] with n = 0, which is nums[-1], and throws IndexOutOfRangeException. If empty input were possible, a guard such as if (n == 0) return; would be needed before reading last.
    • Looping left to right. As explained above, it overwrites values before they are copied and fills the array with one repeated value.
    • Forgetting to save last. Without it, the final value to write at index 0 is already gone.
    • Looping down to 0. With i >= 0 the last iteration reads nums[-1] and throws.

    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 C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free