Circular Array Operations

What is this?

Imagine a clock face: after 12 comes 1 again — the numbers loop back instead of running off the edge. A circular array works the same way: the last slot connects back to the first, so you can keep stepping forward forever and you'll just go round and round. This is exactly how a running track, a carousel, or "whose turn is next" in a board game behaves, and it shows up constantly in real software like the buffers that smooth out streaming audio.

💡 Fun fact: The "wrap around with a remainder" trick (modular arithmetic) was formalized by Carl Friedrich Gauss in 1801, more than a century before computers existed. The very same idea now powers the consistent-hashing rings that let services like Cassandra and DynamoDB spread data across thousands of machines.

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

The one-line idea: a circular array is just an ordinary array whose ends are glued together. Learn two reflexes — index with % n, and always consider "the other way around" — and a whole family of problems collapses into easy ones.

1. What "circular" really means

In a normal array, index 0 is the start and n‑1 is the end — fall off either edge and you're out of bounds. In a circular array, the element after n‑1 is 0 again. Bend the line into a ring:

Two tiny tools handle 95% of the wrap-around:

⚠️ In many languages -1 % n is negative (-1, not n‑1). Always normalise with (i - 1 + n) % n. (Python's % is non-negative, but write it the safe way out of habit — interviews are polyglot.)

2. Where you'll actually meet this

Circular arrays aren't a toy — they're how real systems reuse fixed memory and bounded structure:

• Ring buffers / circular queues. Audio & network I/O buffers, Linux kernel ring buffers, Kafka-style append-with-wrap logs, lock-free SPSC queues — a fixed array with head/tail indices that wrap with % n.
• Consistent-hashing rings (Cassandra, DynamoDB). Nodes and keys sit on a ring; ownership and replica walks go around it, often choosing the shorter direction.
• Round-robin scheduling / load balancing. Pick the next worker with (i + 1) % n — CPU schedulers, nginx upstreams, task queues.
• Ring network topologies (SONET/SDH, Token Ring). Traffic between two nodes can travel either arc; pick the shorter healthy one.
• Games & UI. Circular tracks, carousels, turn order that wraps back to player 0.

If a problem says circular, ring, wrap around, cyclic, rotate, or next … going around — this chapter is the toolkit.

3. The circular toolkit (patterns to recognise)

1. Two directions, then min. Between two points on a ring there are exactly two arcs. Their lengths sum to the whole loop, so other = total − arc. Compute one, subtract, take the smaller. (This is the bus-stops problem below.)
2. "Double it" to linearise. Many circular problems (max circular subarray, next-greater-element-in-a-circular-array) become linear if you imagine the array written twice back-to-back — or iterate 2n times using % n instead of actually copying.
3. Prefix sums on a ring. Range sums that wrap = total − (sum of the non-wrapping middle).
4. Head/tail with modulo (ring buffer). Enqueue at tail = (tail + 1) % n, dequeue at head = (head + 1) % n; track size to tell "full" from "empty".

4. A 30-second worked example (wrap-around distance)

Ring of 5 segment costs gap = [4, 3, 9, 2, 6] (so total = 24). Shortest way from stop 1 to stop 4?

No second loop, no modular gymnastics — just one arc and a subtraction. That single trick is the heart of the first problem in this chapter.

5. Problems in this chapter

▶ Minimum Distance Between Bus Stops

A circular metro loop; find the shorter of the clockwise / counter-clockwise distance between two stations. Teaches the other = total − arc reflex and why reaching for Dijkstra is overkill on a ring.
Pattern: two-directions → min. Target: O(n) time, O(1) space.

(More circular problems — circular subarray, ring-buffer design, next greater element II — slot in here as the chapter grows; they reuse tools #2–#4 above.)

6. Common pitfalls 🚫

• Negative modulo when stepping backward — use (i - 1 + n) % n.
• Double-counting the full loop — the two arcs already sum to total; don't add the shared endpoints twice.
• Forgetting start == dest — distance is 0, not the whole loop.
• Actually copying the array to "double" it — usually you can just iterate 2n times with % n and save the O(n) space.
• Off-by-one between "edges" and "nodes" — gap[i] is the segment between i and i+1, not a stop itself.

7. Key takeaways

1. Circular = linear + % n. Master forward/backward stepping and most boundary bugs vanish.
2. On a ring, there are two arcs; other = total − arc turns two traversals into one.
3. "Double the array" linearises cyclic window / next-greater problems.
4. Ring buffers are this pattern in production — fixed memory, head/tail with modulo.
5. Recognise the trigger words (circular, wrap, ring, cyclic, rotate) and reach for the toolkit above.