Array Transformation Operations

What is this?

Say you want to shift everyone in a line so the last few people move to the front — like rotating who sits in the window seats on a long road trip. The clumsy way is to copy everyone into a brand-new line; the clever way is a little trick: flip the whole line around, then flip the two pieces back. Three quick flips and everybody lands exactly where they belong, with no second line needed. This chapter is about reshuffling an array into a new arrangement without wasting extra space.

💡 Fun fact: This "rotate by flipping pieces" idea isn't just an interview party trick — chips do it in hardware. Bit-rotation instructions are core building blocks inside the encryption that protects your web traffic, including the SHA-2 and ChaCha20 algorithms behind HTTPS.

🔓 The problem in this chapter is free. Sign in with Google or Microsoft to start solving.

The one-line idea: rearranging an array into a new pattern almost never needs a second array. The two power tools — in-place reversal and index arithmetic with % n — let you rotate, flip, and re-order elements in O(1) extra space. Learn the reversal trick once and a whole family of "shift / rotate / reorder" problems falls out.

1. What "transformation" really means

A transformation moves each element from its current index to a new index dictated by a rule — rotate right by k, reverse a range, interleave halves, mirror around the center. The naive instinct is to build the answer in a fresh array; the skill this chapter teaches is doing it in place, by recognising that most rearrangements decompose into a few reversals or a walk along index cycles.

The single most reusable identity:

From that one primitive you get rotation (reverse all → reverse the two blocks), word-order reversal, and palindrome-style mirroring — all without allocating.

⚠️ The beginner trap is proportional extra memory: copying into a new array to "see it clearly," then copying back. It works, but it's the O(n)-space answer an interviewer will immediately ask you to remove. Reach for reversal or cyclic replacement instead.

2. Where you'll actually meet this

Cyclic shifts and reversals are real infrastructure primitives, not worksheet filler:

• Consistent hashing & shard rebalancing (Cassandra, DynamoDB). Reassigning token ranges after a topology change is a rotation of who-owns-what around the ring.
• Round-robin scheduling / load balancing. Advancing "who's next" across a fixed worker pool is a logical rotation — usually done by bumping a start index % n, the O(1)-space form of rotation.
• Ring buffers & streaming offsets (Kafka position, audio/video frame buffers). A rotated view of fixed data is just (i + offset) % n — no data moves at all.
• Cryptography. Bit-rotations (ROTL/ROTR) are this idea at the word level — core steps in SHA-2, ChaCha20, and AES key schedules.
• Networking & displays. DNS round-robin rotates candidate IPs; an LED marquee right-rotates its frame buffer each tick.
• Finance / retail. Rolling windows over a fixed ring, or cycling featured stock to the front of a shelf list.

If a problem says rotate, cyclically shift, reverse, mirror, reorder in place, or by an offset k — this chapter's toolkit applies.

3. The transformation toolkit (patterns to recognise)

1. In-place reversal (two pointers). Crossing pointers swap from both ends inward — the atom of most transformations. O(1) space.
2. The reversal identity for rotation. [A | B] → [B | A] via reverse-all then reverse-each-block, since (Aᴿ Bᴿ)ᴿ = B A. Three reversals = a rotation, no buffer.
3. Index arithmetic with % n. An element's destination is often closed-form (i → (i+k) % n). Reduce offsets with k = k % n so a full turn is a no-op and indices never overflow.
4. Cyclic replacement. Follow each element along its cycle i → (i+k) % n, carrying the displaced value; covers all positions in gcd(n,k) cycles, O(1) space.
5. Move the pointer, not the data. For ring buffers and round-robin, a shifting start index gives a rotated view for free — the senior-level answer.

4. A 30-second worked example (rotation by reversal)

Rotate [3, 8, 1, 9, 6, 2] right by k = 4, in place.

No second array, no step-by-step shifting — three linear flips. That reversal reflex is the heart of the first problem in this chapter.

5. Problems in this chapter

▶ Array Rotation

Rotate an array right by k in place (think: sliding an on-call rota so the tail wraps to the front). Teaches the reduce-k-mod-n habit, the three-reversal identity for O(1)-space rotation, and the senior insight that ring buffers rotate a view, not the data.
Pattern: in-place reversal / block swap. Target: O(n) time, O(1) space.

(More transformation problems — reverse words, rotate a matrix, rearrange by parity, next permutation — slot in here as the chapter grows; they all reuse tools #1–#4 above.)

6. Common pitfalls 🚫

• Forgetting k = k % n — huge k wastes work and out-of-range indices (nums[k-1]) crash.
• Allocating a second array — the O(n)-space copy is the answer you'll be asked to replace; reach for reversal/cyclic replacement.
• Rotating one step at a time — that's O(n·k); move each element straight to its final home instead.
• Direction confusion — left-by-k is right-by-n-k; pick one convention and convert.
• Skipping edge cases — empty array, k = 0, and k % n == 0 must all leave the array untouched (guard before any % n).

7. Key takeaways

1. Transformations rearrange positions by a rule — and almost always can be done in place, not in a fresh array.
2. In-place reversal (two crossing pointers) is the atom; three reversals make a rotation via (Aᴿ Bᴿ)ᴿ = B A.
3. Reduce offsets with % n so full turns vanish and indices stay in range.
4. Cyclic replacement is the alternative O(1)-space route — follow i → (i+k) % n through gcd(n,k) cycles.
5. The sharpest move is often not moving data at all — a shifting start index gives ring buffers and round-robin schedulers a rotated view for free.