Start learning free

LESSON 261 OF 441 · TWO POINTERS

Rotate Array in C#: In Place with O(1) Space

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 6
    Ctrl + Enter to check

    C# · TWO POINTERS

    Rotate Array in C#, explained

    Problem overview

    The method Rotate receives an int[] named nums and an int named k. It rotates the array k times to the right, in place: one rotation moves every item one position to the right, and the last item moves to the front. The method returns nothing, because it changes the caller's array. It must run in O(n) time and use O(1) extra space. The array has between 1 and 30,000 items, and k is between 1 and its length.

    With 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]. With [1, 2, 3, 4, 5, 6, 7, 8] and k = 3, the result is [6, 7, 8, 1, 2, 3, 4, 5].

    Approach: move each item straight to its final place

    Rotating one step at a time k times costs O(n × k), and building a second array to copy into costs O(n) extra space. Both are ruled out. But the final position of every item is known without any intermediate rotations: the item at index i ends up at index (i + k) % n. The remainder operator wraps indices past the end back to the front.

    Moving an item to its target would overwrite whatever is there, so that item has to be moved on in turn to its own target, and so on. The indices 0, k, 2k, ... (all modulo n) form a cycle: following the moves eventually returns to where it started. When n and k share a common factor, a single cycle doesn't reach every position. For n = 6 and k = 2 the cycle from index 0 visits only 0, 2 and 4, and a second cycle through 1, 3 and 5 is needed. The number of cycles is the greatest common divisor of n and k, and every position belongs to exactly one cycle.

    The lesson handles this with a trick: nums[startIndex] acts as a hand holding the item in transit. Each step swaps the held item into its target slot and picks up the item that was there, which is the next one to move. When the walk returns to startIndex, the cycle is closed and the walk starts again from the next index.

    Here is [1, 2, 3, 4, 5] with k = 2. The array after each of the five steps is [3, 2, 1, 4, 5], [5, 2, 1, 4, 3], [2, 5, 1, 4, 3], [4, 5, 1, 2, 3] and, after a final self-swap that closes the cycle, [4, 5, 1, 2, 3] again. Here n and k share no common factor, so there is one cycle.

    Step by step

    1. Declare three int variables: n is nums.Length, index is the position the walk is at, and startIndex is where the current cycle began. Both positions start at 0.
    2. Loop exactly n times. Every step puts one item in its final place, and there are n items, so n steps are enough whatever the cycle structure.
    3. Compute nextIndex as (index + k) % n. It is the slot the held item belongs in.
    4. Swap nums[nextIndex] and nums[startIndex]. The held item lands in its final slot, and the item that was there is now held at startIndex.
    5. Move on: set index = nextIndex.
    6. Detect a closed cycle. When index == startIndex, the walk has come back to its start, and the last swap was a swap of a slot with itself that put the held item home. Increment both startIndex and index to begin the next cycle from the neighbouring slot. If there is no next cycle, the loop ends right after.

    The solution in C#

    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;
            (nums[nextIndex], nums[startIndex]) = (nums[startIndex], nums[nextIndex]);
            index = nextIndex;
            if (index == startIndex) {
                startIndex++; index++;
            }
        }
    }
}

    The C# details worth knowing:

    • Tuple assignment as a swap. (a, b) = (b, a) evaluates the right side first, then assigns, so no temporary variable is needed. It works on array elements like nums[nextIndex] too. When both elements are the same slot, it assigns a value to itself and changes nothing.
    • Arrays are reference types. nums is a reference to the caller's array, so the method changes the caller's data and has return type void. Assigning a new array to nums inside the method would not change the caller's array.
    • One declaration, three variables. int n = nums.Length, index = 0, startIndex = 0; declares three ints of the same type in one statement.
    • Remainder and indices. % on non-negative int values gives the wrapped index. Here index and k are never negative, so there is no negative remainder to worry about.
    • Integer bounds. index + k is below 2n here, far from the int limit. Because the remainder is taken, a k larger than n also works.

    Complexity

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

    Space: O(1). The method uses five int variables and swaps within the array. It allocates no second array.

    Edge cases and common mistakes

    • One item. [1] with k = 1: nextIndex is 0, the swap changes nothing, and index equals startIndex, so both increase and the loop ends. The array stays [1].
    • k equals the length. A full turn gives the original array. [1, 2, 3] with k = 3 stays [1, 2, 3]. Every cycle has length 1 here, and each step is a self-swap.
    • Several cycles. [1, 2, 3, 4, 5, 6] with k = 2 gives [5, 6, 1, 2, 3, 4]. Without the startIndex restart, the walk would only touch indices 0, 2 and 4.
    • Rotating left by mistake. The target of index i is (i + k) % n. Using - k rotates the other way and can give a negative remainder.
    • Looping until index == startIndex. That stops after the first cycle. The counted loop of n steps is what covers all of them.
    • Allocating a new array. Copying each item to (i + k) % n in a new array is correct, but it uses O(n) space and breaks the lesson's limit.

    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], k = 2 gives [3, 4, 1, 2].
    • [1], k = 1 gives [1].
    • [1, 2, 3], k = 3 gives [1, 2, 3].
    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