Circular arrays and wraparound

A circular arraycircular arrayAn array whose index wraps from the last element back to the first, usually with the modulo operator.In the glossary wraps around: go past the last element, and you land back on the first, as if the array were bent into a ring. A clock is the everyday version of this: add 5 hours to hour 11 and you land on hour 4, not hour 16, because the hours wrap back to 0 after 11. A round-robin scheduler cycling through workers, and a buffer that holds the most recent items in a stream, work the same way.

Modulo wraparound

The modulo operator, %, does the wrapping for you. For an array of N elements, indices run from 0 to N − 1, and index % N always lands somewhere in that range no matter how large index is.

1arr = [10, 20, 30]2index = 53circular_index = index % 34print(arr[circular_index])

Index 5 wraps to index 2, so this prints 30.

Watch negative numbers, though: -1 % 3 is 2 in Python, not -1, because Python's modulo always returns a non-negative result when the divisor is positive. That is usually exactly the behaviour you want for wrapping backward around a circle, but it is worth knowing rather than assuming.

A worked example

Players sit in a circle, and a token passes from one to the next. Given a number of passes, report who ends up holding the token.

1n, passes = map(int, input().split())2current_player = 03
4for _ in range(passes):5    current_player = (current_player + 1) % n6
7print(current_player)

5 12

2

With 5 players numbered 0 to 4, one pass from player 0 lands on player 1, five passes land back on player 0, and the program's 12 passes land on player 2, since 12 % 5 is 2. Modulo handles every one of those wraps without a special case for when the count runs past the last player.

Circular rotation

Rotating an array is another common circular task. Rotating [1, 2, 3, 4, 5] right by 2 gives [4, 5, 1, 2, 3].

You do not need to build the rotated array by shifting elements one at a time. The element that ends up at position i in the rotated array is the one that sat at position (i - rotation) % N in the original.

1original = [1, 2, 3, 4, 5]2rotation = 23rotated = [original[(i - rotation) % len(original)] for i in range(len(original))]4print(rotated)

Each rotated position is computed directly from the original array, with the modulo doing the wraparound work that a manual shift would otherwise need loops to get right.

Circular sliding windows

Some problems ask about a contiguous stretch of a circular array, such as the maximum sum of any N consecutive elements once the array wraps. Picture unrolling the circle: for [10, 20, 30] with a window of size 2, the windows starting at each position are [10, 20], [20, 30] and [30, 10], the last one wrapping past the end back to the start.

To read a window's elements starting at position start, index with arr[(start + offset) % N] for each offset from 0 up to the window size. The same modulo trick that handles a single wrapped index handles a whole wrapped window, one element at a time.

Circular buffers

A circular buffer applies the same wraparound idea to a stream of data instead of a fixed array. Say you need the average of the last 10 sensor readings at every step, and shifting 10 values on every new reading is too slow to do repeatedly.

Keep a buffer of 10 slots and one "next write" position. When a new reading arrives, write it into that slot, add it to a running total, subtract the value it just overwrote from that total, then advance the write position with next_write = (next_write + 1) % 10. The average is always the running total divided by 10, updated in constant time per reading, with no shifting and no reallocating.

Operating systems use exactly this pattern for I/O buffers, and producer-consumer queues use it to avoid resizing on every push and pop. Wherever data keeps arriving at one end and leaving from the other, a circular buffer avoids the cost a plain array would pay to shift everything down.

Two pointers on a circular array

The two-pointer technique from an earlier lesson still works once an array is circular, as long as every index you compute goes through modulo first. Suppose you are looking for the largest sum of a contiguous circular stretch of exactly K elements, and you want to slide a window of size K all the way around, including windows that wrap past the end. Keep a running sum for the current window, and each step drop the value leaving the window and add the value entering it, exactly as a normal sliding window would, except both the leaving index and the entering index are taken modulo N. After sliding N times, the window has visited every one of the N possible starting positions, wrapped ones included, and the best sum seen along the way is the answer.

The one detail that trips people up here is the stopping condition. A sliding window on a plain array stops once the window's right edge reaches the end; a circular window has no natural end; it stops once it has slid exactly N times, back to where it started, not when some index crosses a boundary that no longer exists.

Getting the modulo right

The most common slip is leaving the modulo out and assuming an index stays in range. Adding 1 to index 4 on a 5-element array gives 5, an out-of-bounds index, unless you wrap it with % 5 first.

If you ever port this pattern to a language where % on a negative number returns a negative result, such as C++ or Java, ((index % N) + N) % N restores the always-non-negative behaviour Python gives you by default.

And check that the modulo value matches the array size exactly. Twelve hours wrap correctly with % 12, since (11 + 1) % 12 is 0; using % 11 or % 13 by mistake breaks the wraparound in a way that only shows up at the one index where it matters, which makes it an easy bug to miss until it fails on exactly the input that exercises it.