LeetCode 2757 - Generate Circular Array Values

LeetCode Problem 2757

Difficulty: 🟡 Medium
Topics: —

Solution

Problem Understanding

The problem asks us to create a generator for a circular array, arr, starting from a given index startIndex. A generator is a construct that yields a value each time it is called. The first call to the generator should return the element at startIndex. Subsequent calls pass an integer jump which specifies how many positions to move in the array. If jump is positive, the index moves forward by that amount, wrapping around to the start if necessary. If jump is negative, the index moves backward, wrapping to the end if it moves past the beginning.

The input arr is a list of integers of length up to 10,000, which means we must handle moderate-size arrays efficiently. The steps list specifies the jumps and contains up to 100 values, meaning the generator will be called a limited number of times. Each jump can range from -10,000 to 10,000, requiring careful handling of circular indexing. The constraints guarantee a valid starting index within array bounds.

Key edge cases include large positive or negative jumps that exceed the array length, a jump of zero, and arrays of length one where all moves will point to the same element.

Approaches

The brute-force approach would maintain a current index and manually iterate through the array for each jump, adjusting the index by 1 repeatedly and wrapping around when needed. While simple, this approach is inefficient for large jumps, as it could require up to O(|jump|) operations for each gen.next() call.

The optimal approach leverages modulo arithmetic. Since the array is circular, any jump can be reduced modulo the array length. This allows direct computation of the next index in constant time without repeated iteration. The key insight is that for a jump k in an array of length n, the new index is (current_index + k) % n if k is positive, or (current_index + k + n) % n if k is negative to ensure a positive index.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(	jump	per call)
Optimal	O(1) per call	O(1)	Uses modulo arithmetic to compute new index directly, constant time

Algorithm Walkthrough

1. Initialize the generator with the array arr and startIndex. Store the current index in a variable current.
2. On the first call to next(), yield arr[current] without changing the index.
3. On subsequent calls, accept a jump value.
4. Compute the new index using modulo arithmetic to handle circular behavior: current = (current + jump) % len(arr). If the result is negative, add len(arr) to wrap correctly.
5. Yield arr[current].
6. Repeat steps 3-5 for every call to next().

Why it works: Modulo arithmetic ensures the index always stays within [0, len(arr)-1], automatically implementing the circular array behavior. This invariant guarantees that every gen.next() call yields the correct array element after the specified jump.

Python Solution

from typing import Generator

def cycleGenerator(arr: list[int], startIndex: int) -> Generator[int, int, None]:
    n = len(arr)
    current = startIndex
    jump = yield arr[current]  # First yield returns startIndex element
    
    while True:
        if jump is None:
            jump = 0
        current = (current + jump) % n
        jump = yield arr[current]

This implementation first yields the element at startIndex. Then it enters a loop where it waits for the next jump value. Using modulo arithmetic ensures the index stays within bounds, wrapping forward or backward as needed. The generator continues indefinitely, producing elements according to circular jumps.

Go Solution

package main

type Generator struct {
	arr    []int
	current int
}

func cycleGenerator(arr []int, startIndex int) *Generator {
	return &Generator{arr: arr, current: startIndex}
}

func (g *Generator) Next(jump ...int) int {
	n := len(g.arr)
	move := 0
	if len(jump) > 0 {
		move = jump[0]
	}
	g.current = (g.current + move) % n
	if g.current < 0 {
		g.current += n
	}
	return g.arr[g.current]
}

In Go, we use a struct to maintain generator state. The Next method takes an optional jump parameter. Modulo arithmetic is used to ensure the index wraps around correctly. A negative index is corrected by adding the array length.

Worked Examples

Example 1: arr = [1,2,3,4,5], steps = [1,2,6], startIndex = 0

Step	Current Index	Jump	Result
first call	0	-	1
next(1)	0 -> 1	1	2
next(2)	1 -> 3	2	4
next(6)	3 -> 4	6	5

Example 2: arr = [10,11,12,13,14,15], steps = [1,4,0,-1,-3], startIndex = 1

Step	Current Index	Jump	Result
first call	1	-	11
next(1)	1 -> 2	1	12
next(4)	2 -> 0	4	10
next(0)	0 -> 0	0	10
next(-1)	0 -> 5	-1	15
next(-3)	5 -> 2	-3	12

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) per call	Each next() call computes the index using arithmetic, no loops
Space	O(1)	Only a few variables are stored; generator itself uses constant memory

Modulo arithmetic avoids iterating through elements, so each jump is handled in constant time regardless of jump size.

Test Cases

arr = [1,2,3,4,5]
gen = cycleGenerator(arr, 0)
assert next(gen) == 1  # startIndex
assert gen.send(1) == 2
assert gen.send(2) == 4
assert gen.send(6) == 5

arr = [10,11,12,13,14,15]
gen = cycleGenerator(arr, 1)
assert next(gen) == 11
assert gen.send(1) == 12
assert gen.send(4) == 10
assert gen.send(0) == 10
assert gen.send(-1) == 15
assert gen.send(-3) == 12

arr = [2,4,6,7,8,10]
gen = cycleGenerator(arr, 3)
assert next(gen) == 7
assert gen.send(-4) == 10
assert gen.send(5) == 8
assert gen.send(-3) == 4
assert gen.send(10) == 10

# edge cases
arr = [1]
gen = cycleGenerator(arr, 0)
assert next(gen) == 1
assert gen.send(1000) == 1
assert gen.send(-1000) == 1

Test	Why
simple jumps	verifies basic forward/backward movement
jumps exceeding array length	tests modulo arithmetic wraparound
jump zero	ensures staying on the same index works
single-element array	ensures circular wrap works for length 1

Edge Cases

A common edge case occurs when the jump magnitude exceeds the array length. Without modulo arithmetic, a naive implementation could index out of bounds. By using (current + jump) % len(arr), the solution handles these large jumps correctly.

Another edge case is when the jump is negative. Python’s modulo operator handles negative numbers differently than some languages, so we must explicitly add the array length to ensure a positive index. The Go implementation addresses this similarly.

A third edge case is an array of length one. All jumps, positive or negative, should return the same element. The modulo operation ensures that (0 + jump) % 1 == 0, which correctly yields the only element in the array.