Problem Description

You are given an integer array nums and a non-negative integer k. Your task is to rotate the array to the right by k steps.

When rotating an array to the right by k steps, each element moves k positions to the right. Elements that go beyond the last position wrap around to the beginning of the array.

For example:

• If nums = [1, 2, 3, 4, 5, 6, 7] and k = 3
• After rotating right by 3 steps, the array becomes [5, 6, 7, 1, 2, 3, 4]
• The last 3 elements [5, 6, 7] moved to the front
• The first 4 elements [1, 2, 3, 4] shifted to the right

The solution uses a clever approach with three reversal operations:

1. First, reverse the entire array
2. Then reverse the first k elements
3. Finally, reverse the remaining n - k elements

Since k could be larger than the array length, we use k % n to get the effective rotation count. This handles cases where rotating by n steps (or multiples of n) results in the original array.

The operation should be done in-place, modifying the original array directly without using extra space for another array.

Intuition

Let's think about what happens when we rotate an array to the right by k steps. The last k elements need to move to the front, and the first n - k elements need to shift to the back.

One straightforward approach would be to use extra space to copy elements, but can we do it in-place?

Let's observe what the final result looks like. If we have [1, 2, 3, 4, 5, 6, 7] and rotate by 3, we get [5, 6, 7, 1, 2, 3, 4]. Notice that:

• The last 3 elements [5, 6, 7] are now at the front
• The first 4 elements [1, 2, 3, 4] are now at the back
• Both groups maintain their internal order

The key insight is that we can achieve this rearrangement using reversals. When we reverse an array, elements from the end move to the beginning and vice versa. But how do we preserve the internal order of each group?

Let's trace through the reversal approach:

1. If we reverse the entire array [1, 2, 3, 4, 5, 6, 7], we get [7, 6, 5, 4, 3, 2, 1]

   • Now the last k elements are at the front (but in reversed order)
   • The first n - k elements are at the back (also in reversed order)

2. To fix the order of the first group, we reverse the first k elements: [7, 6, 5] becomes [5, 6, 7]

3. To fix the order of the second group, we reverse the last n - k elements: [4, 3, 2, 1] becomes [1, 2, 3, 4]

The beauty of this approach is that three simple reversal operations achieve the rotation without any extra space. Each reversal can be done in-place by swapping elements from both ends moving towards the center.

This works because reversing puts elements in the right groups (last k at front, first n-k at back), and the subsequent targeted reversals restore the correct order within each group.

Solution Approach

The implementation uses the three-reversal technique to rotate the array in-place. Here's how the solution works:

Step 1: Handle edge cases with modulo operation

k %= n

Since rotating an array by its length n results in the same array, we take k mod n to get the effective rotation count. This handles cases where k > n.

Step 2: Define a helper function for reversing

def reverse(i: int, j: int):
    while i < j:
        nums[i], nums[j] = nums[j], nums[i]
        i, j = i + 1, j - 1

This function reverses elements between indices i and j (inclusive) using the two-pointer technique:

• Start with pointers at both ends of the segment
• Swap elements at the pointers
• Move pointers towards each other
• Continue until they meet or cross

Step 3: Apply three reversals

Following the algorithm described in the reference approach:

1. First reversal - Reverse the entire array:

   reverse(0, n - 1)

   This moves the last k elements to the front (in reversed order) and the first n - k elements to the back (also reversed).

2. Second reversal - Reverse the first k elements:

   reverse(0, k - 1)

   This restores the correct order for the k elements that should be at the front.

3. Third reversal - Reverse the last n - k elements:

   reverse(k, n - 1)

   This restores the correct order for the remaining elements.

Example walkthrough with nums = [1, 2, 3, 4, 5, 6, 7], k = 3:

• Initial: [1, 2, 3, 4, 5, 6, 7]
• After reversing entire array (0 to 6): [7, 6, 5, 4, 3, 2, 1]
• After reversing first 3 elements (0 to 2): [5, 6, 7, 4, 3, 2, 1]
• After reversing last 4 elements (3 to 6): [5, 6, 7, 1, 2, 3, 4]

Time Complexity: O(n) - Each element is reversed at most twice Space Complexity: O(1) - Only using a constant amount of extra space for the pointers

Example Walkthrough

Let's walk through a small example with nums = [1, 2, 3, 4, 5] and k = 2.

Goal: Rotate the array to the right by 2 steps, moving the last 2 elements to the front.

Step 1: Calculate effective rotation

• k = 2 % 5 = 2 (no change since k < array length)

Step 2: Reverse the entire array (indices 0 to 4)

• Original: [1, 2, 3, 4, 5]
• Swap positions 0 and 4: [5, 2, 3, 4, 1]
• Swap positions 1 and 3: [5, 4, 3, 2, 1]
• Position 2 stays (middle element)
• Result: [5, 4, 3, 2, 1]

Step 3: Reverse the first k elements (indices 0 to 1)

• Current: [5, 4, 3, 2, 1]
• Swap positions 0 and 1: [4, 5, 3, 2, 1]
• Result: [4, 5, 3, 2, 1]

Step 4: Reverse the last n-k elements (indices 2 to 4)

• Current: [4, 5, 3, 2, 1]
• Swap positions 2 and 4: [4, 5, 1, 2, 3]
• Position 3 stays (middle element of this segment)
• Result: [4, 5, 1, 2, 3]

Final Result: [4, 5, 1, 2, 3]

We can verify this is correct:

• The last 2 elements [4, 5] moved to the front
• The first 3 elements [1, 2, 3] shifted to the back
• Both groups maintained their internal order

The three reversals efficiently rearranged the array in-place without using extra space.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array. The algorithm performs three reversal operations:

• First reversal: reverses the entire array from index 0 to n-1, which takes O(n) time
• Second reversal: reverses elements from index 0 to k-1, which takes O(k) time
• Third reversal: reverses elements from index k to n-1, which takes O(n-k) time

The total time complexity is O(n) + O(k) + O(n-k) = O(n).

The space complexity is O(1). The algorithm only uses a constant amount of extra space for:

• The variables i and j in the reverse function
• The variables n and k for storing array length and rotation count

No additional data structures are created that scale with the input size. The rotation is performed in-place by swapping elements directly in the original array.

Common Pitfalls

1. Forgetting to Handle k Greater Than Array Length

One of the most common mistakes is not using the modulo operation when k is larger than the array length. Without k % n, the algorithm will try to access indices out of bounds.

Incorrect approach:

def rotate(self, nums: List[int], k: int) -> None:
    def reverse(start: int, end: int) -> None:
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1
  
    n = len(nums)
    # Missing: k = k % n
  
    reverse(0, n - 1)
    reverse(0, k - 1)  # This will fail if k >= n
    reverse(k, n - 1)   # This will also fail if k >= n

Why it fails: If k = 10 and n = 7, trying to reverse from index 0 to 9 will cause an index out of bounds error.

Solution: Always normalize k using modulo:

k = k % n  # Ensures k is always within valid range [0, n-1]

2. Empty Array or Single Element Edge Cases

Another pitfall is not handling edge cases where the array is empty or has only one element. While the current solution handles these gracefully, explicitly checking can prevent unexpected behavior.

Potential issue:

def rotate(self, nums: List[int], k: int) -> None:
    n = len(nums)
    k = k % n  # Division by zero if n = 0

Solution: Add an early return for edge cases:

def rotate(self, nums: List[int], k: int) -> None:
    n = len(nums)
    if n <= 1:  # No rotation needed for empty or single-element arrays
        return
  
    k = k % n
    if k == 0:  # No rotation needed if k is multiple of n
        return
  
    # Continue with the reversal logic...

3. Incorrect Reversal Boundaries

A subtle but critical mistake is using wrong indices for the reversal operations, especially mixing up inclusive vs exclusive boundaries.

Common mistakes:

# Mistake 1: Using k instead of k-1
reverse(0, k)      # Wrong! This reverses k+1 elements
reverse(k+1, n-1)  # Wrong! This skips the element at index k

# Mistake 2: Off-by-one errors
reverse(0, n)      # Wrong! n is out of bounds
reverse(k, n)      # Wrong! n is out of bounds

Solution: Remember that the reversal boundaries are inclusive:

• First reversal: reverse(0, n-1) - entire array
• Second reversal: reverse(0, k-1) - first k elements
• Third reversal: reverse(k, n-1) - remaining elements

4. Misunderstanding the Direction of Rotation

Sometimes developers confuse rotating right with rotating left, leading to incorrect reversal order.

Wrong approach for right rotation:

# This would actually rotate LEFT by k positions
reverse(0, k - 1)     # Reverse first k elements first
reverse(k, n - 1)     # Then reverse remaining elements
reverse(0, n - 1)     # Finally reverse entire array

Solution: For right rotation, the correct order is:

1. Reverse entire array first
2. Reverse first k elements
3. Reverse last n-k elements

For left rotation, you would use the opposite order or adjust k to n - k and use the same right rotation logic.