Lab 01 — Array Fundamentals: Rotate Array In Place

Goal

Master in-place array rotation. The deliverable shows you understand pointer arithmetic, the O(N) reversal trick, dynamic-array memory layout, and edge cases that catch ~70% of candidates on this exact problem.

Background Concepts

Arrays as contiguous memory; index arithmetic mod N; in-place vs auxiliary-space transformations; the “three reversals” identity: rotate(arr, k) == reverse(reverse(arr[:k]), reverse(arr[k:])). Review the Arrays section of the Phase 1 README and the value-vs-reference rules in section 3 of the runtime concepts.

Interview Context

This is the canonical “looks easy, traps everyone” Easy/low-Medium problem. Real interviews from Microsoft, Amazon, Meta, Apple, Google. The interviewer is watching for: do you do the auxiliary-array brute force first? Do you spot the O(N) in-place trick? Do you handle k > N? Do you survive k == 0 and N == 1?

Problem Statement

Given an integer array nums and a non-negative integer k, rotate the array to the right by k steps in place. After the rotation, element originally at index i ends up at index (i + k) % N.

Constraints

• 1 ≤ N ≤ 10^5
• -2^31 ≤ nums[i] ≤ 2^31 - 1
• 0 ≤ k ≤ 10^9
• Must run in O(N) time and O(1) extra space.

Clarifying Questions

1. Can k be greater than N? (Yes — must reduce mod N.)
2. Can k be 0? (Yes — should be a no-op, no array mutation.)
3. Can the array be empty / size 1? (Per the constraints, N ≥ 1. Confirm.)
4. Right rotation, not left? (Confirm direction; getting it backward is a top-3 bug here.)
5. Must it be in place, or is auxiliary memory allowed? (In place — that’s the spirit of the problem.)

Examples

Initial Brute Force

Allocate out[N]; for each i, set out[(i + k) % N] = nums[i]; copy out back into nums.

def rotate_brute(nums, k):
    n = len(nums)
    k %= n
    out = [0] * n
    for i in range(n):
        out[(i + k) % n] = nums[i]
    nums[:] = out

Brute Force Complexity

Time: O(N). Space: O(N) auxiliary. Fails the in-place constraint despite optimal time.

Optimization Path

We need O(1) extra space. Two well-known approaches:

1. Cyclic replacement: start at index 0, jump to (0 + k) % N, place the displaced element, continue. Visits each index exactly once. Tricky when gcd(N, k) > 1 (multiple disjoint cycles). Correctness needs a counter for elements moved.
2. Three reversals: reverse the whole array, reverse the first k, reverse the last N-k. This works because rotation by k is reversal of (reversal of left, reversal of right). Easier to write correctly.

Pick the three-reversal approach for the interview unless the interviewer explicitly asks for cyclic replacement.

Final Expected Approach

Three-reversal in place.

def reverse(nums, l, r):
    while l < r:
        nums[l], nums[r] = nums[r], nums[l]
        l += 1
        r -= 1

def rotate(nums, k):
    n = len(nums)
    k %= n              # normalize
    reverse(nums, 0, n - 1)
    reverse(nums, 0, k - 1)
    reverse(nums, k, n - 1)

Data Structures Used

A single mutable array. No auxiliary structures.

Correctness Argument

Loop invariant for reverse(l, r): at each iteration, elements at positions less than l and greater than r are already correctly placed (i.e., are mirror swaps of each other). Termination at l ≥ r leaves the closed range fully reversed. The three-reversal identity is verifiable with a 2-step example: [A B C D E] k=2 → reverse all → [E D C B A] → reverse first 2 → [D E C B A] → reverse last 3 → [D E A B C]. Equivalent to original rotated right by 2.

Complexity

Time: O(N) (three passes, each touching at most N elements). Space: O(1) (in-place swaps; no allocation).

Implementation Requirements

• Helper reverse(nums, l, r) with explicit bounds (closed interval).
• Always do k %= n first, before any loop or reversal.
• Handle k == 0 and k == n: both reduce to no-op via k %= n.
• No allocation outside the input array (verify by reading your code).
• Clean variable names (l, r, n, k are interview-acceptable).

Tests

• Smoke: the canonical [1,2,3,4,5,6,7] with k=3.
• Unit: k=0 (no-op), k=N (no-op), k=1 (single right shift).
• Edge: N=1, N=2 with k=1, large k=10^9 mod N.
• Large: N=10^5, k=N//2; assert in-place (capture id(nums) in Python).
• Random: generate random arrays and ks; check against brute force as oracle.
• Invalid: negative k (per constraints not allowed; if interviewer extends, decide left rotation semantics).

Follow-up Questions

• “Can you do it without the modulo?” (Yes, but ugly: branch on k <= n.)
• “What if the array is given as a linked list?” (Different problem — find length, find pivot, splice.)
• “What if k can be negative (left rotation)?” (Convert via k = ((k % n) + n) % n.)
• “Solve using a single reverse loop without a helper.” (Inline the swaps three times.)
• “Implement with cyclic replacement instead.” (Demonstrate the gcd cycle counter trick.)

Product Extension

A circular buffer for a metrics dashboard storing the last N seconds of samples. Rotation isn’t done on append — instead, a head index advances mod N. The “three reversals” trick is what you do when the buffer must be flattened to a linear export. Discuss tradeoffs: head-index buffer is O(1) per append but harder to debug; rotation on read is O(N) but storage is always linear.

Language/Runtime Follow-ups

• Python: nums[:] = nums[-k:] + nums[:-k] is one-line and Pythonic but allocates O(N). Acceptable to mention but interviewer may rule it “not in place.” Pure swap version uses no allocation.
• Java: int[] (primitive) avoids boxing. Don’t reach for Collections.rotate; understand it.
• Go: slice indexing, careful with n := len(nums) capture; nums = nums[:] aliasing makes no copy.
• C++: std::reverse(nums.begin() + l, nums.begin() + r + 1); use the standard.
• JS: in-place using [a, b] = [b, a] swap or temp = a. arr.reverse() is in-place.

Common Bugs

1. Forgetting k %= n — when k > n the reversals overlap incorrectly.
2. Off-by-one in reverse(l, r) — using r vs r - 1 as the bound; using < vs ≤.
3. Reversing wrong segments — confusing first-k with last-k. Right rotation: [reverse first k of reversed array] then [reverse last n-k].
4. Allocating in disguise — nums = nums[-k:] + nums[:-k] rebinds the local name and does not mutate the caller’s array (in Python). Use nums[:] = ….
5. Left vs right confusion — re-read the problem statement once before submitting.

Debugging Strategy

• Print the array after each of the three reversals; compare to a hand-traced [1,2,3,4,5,6,7] k=3 walk-through.
• If output is wrong by a constant shift, suspect an off-by-one in segment bounds.
• If output looks reflected ([3,2,1, 7,6,5,4] instead of [5,6,7,1,2,3,4]), one of the three reversals fired in the wrong region.

Mastery Criteria

• Wrote the three-reversal solution in under 4 minutes, no bugs, in-place verified.
• Traced through k > N, k == 0, N == 1 without prompting.
• Stated the loop invariant for reverse aloud.
• Named the cyclic-replacement alternative and acknowledged its gcd complication.
• Identified and avoided the Python nums = nums[-k:] + nums[:-k] allocation trap.