Rotate an Array by k Steps

Rotating an array in place is a classic warm‑up that tests your ability to manipulate arrays, handle wrap‑around indexing, and optimize for O(1) extra space. It’s a real‑world pattern you’ll use for circular buffers, scheduling, and more. Here’s how I’d work it out live in a coding interview.

Problem Statement

Given an array A of length n and an integer k, rotate the array to the right by k steps, in place. That is, each element moves k positions to the right (wrapping around to the front). You may not allocate another array of size n—you must modify A directly (O(1) extra space).

1. Clarify Requirements Before Jumping Into Code

So I need to rotate the array to the right by k steps, modifying the array directly. Great.

A few quick checks:

• If k is larger than n, I’ll assume we use k % n.

• Array can be empty or have one element - those should still work.

• Data type is generic, but I’ll code with integers in mind.

• O(1) extra space allowed (just a few variables).

2. Identify the Category of the Question

This is an in‑place array transformation problem with a hint of either a two‑pointer reversal or a cyclic replacement techniques. It’s not sorting or searching - it’s all about shifting elements efficiently and handling wrap‑around indices via modulo arithmetic.

3. Consider a Brute‑Force Approach to Understand the Problem

If I ignore the space constraint, I could: Allocate a new array B of length n. For each index i, set B[(i + k) % n] = A[i]. Copy B back into A. That’s O(n) time but O(n) space, which works logically but violates the in‑place requirement.

4. Brainstorm More Solutions

How can I do this in O(1) space? Two approaches come to mind:

• Reversal Trick (three reversals): reverse the whole array, then reverse the first k elements, then reverse the rest of the array.

• Cyclic Replacement: walk through cycles by moving each element to its final spot (i + k) % n, tracking when you return to a start position.

  
  

The reversal method is straightforward and is always O(n) time and O(1) space, so that solution is looking like a strong contender at this point.

5. Discuss Trade‑Offs Between Your Solutions

Approach	Time	Space	Pros	Cons
Extra array + copy	O(n)	O(n)	Simple, easy to implement	Uses O(n) extra memory
Reversal (3‑step)	O(n)	O(1)	In‑place, consistent runtime	Requires careful index math
Cyclic Replacement	O(n)	O(1)	In‑place, direct placement	More complex cycle tracking

Reversal wins for clarity and minimal logic risk.

6. Write Pseudocode to Structure Your Thoughts

function rotate(A, k):
    n = length(A)
    k = k mod n
    reverse(A, 0, n - 1)
    reverse(A, 0, k - 1)
    reverse(A, k, n - 1)

function reverse(A, start, end):
    while start < end:
        swap A[start], A[end]
        start++, end--

7. Consider Edge Cases

1. Empty array [] → stays [].

2. Single element [x] → stays [x].

3. k = 0 or k % n = 0 → no change.

4. k > n (e.g. k = n + 2) → normalized by k % n.

5. Even vs. odd length → middle element in odd-length array remains in place.

   
   

8. Write Full Code Syntax

def rotate(nums, k):
    n = len(nums)
    if n == 0:
        return  # nothing to do

    k %= n
    # helper to reverse subarray in place
    def reverse(arr, start, end):
        while start < end:
            arr[start], arr[end] = arr[end], arr[start]
            start += 1
            end   -= 1

    # three-step reversal
    reverse(nums, 0, n - 1)
    reverse(nums, 0, k - 1)
    reverse(nums, k, n - 1)

9. Test Your Code

# Normal cases
arr = [1, 2, 3, 4, 5, 6, 7]
rotate(arr, 3)
assert arr == [5, 6, 7, 1, 2, 3, 4]

arr = [1, 2, 3, 4, 5]
rotate(arr, 2)
assert arr == [4, 5, 1, 2, 3]

# Edge cases
arr = []
rotate(arr, 5)
assert arr == []

arr = [42]
rotate(arr, 10)
assert arr == [42]

arr = [1, 2, 3]
rotate(arr, 3)   # k % n = 0
assert arr == [1, 2, 3]

arr = [1, 2, 3]
rotate(arr, 4)   # k % n = 1
assert arr == [3, 1, 2]

print("All tests passed!")

10. Key Lessons to Remember for Future Questions

• Normalize your math: Always do k %= n to handle large k.

• Reversal pattern: The three-step reversal is a go‑to for in‑place rotations and shifts. It's a great technique to have in your back pocket, but remember to talk everything out anyway! Giving them the right answer from the start might seem impressive, but interviewers also need to see and hear you problem solve.

• Edge-case checklist: Empty inputs, single‑element inputs, zero shifts, and wrap‑around shifts.

• Modular helpers: Writing a small reverse helper keeps your main logic clean. Remember that interviewers want to see clean and readable code just as much they want to see the right answer to a question.

  
  

With this approach, you’ll nail any rotation or in‑place shift problem—and demonstrate clear, methodical thinking in your next interview. Happy coding!