2757. Generate Circular Array Values 🔒

Medium

Problem Description

You need to create a generator function that traverses a circular array with the ability to jump forward or backward based on input.

Given:

A circular array arr (where the last element connects back to the first)
A starting index startIndex

The generator should:

First call: When gen.next() is called for the first time (without any argument), yield the value at arr[startIndex]
Subsequent calls: When gen.next(jump) is called with an integer jump parameter:
- If jump is positive: Move forward by jump positions in the array
  - If this would go past the last index, wrap around to the beginning (circular behavior)
- If jump is negative: Move backward by |jump| positions in the array
  - If this would go before the first index, wrap around to the end (circular behavior)

The solution uses the modulo operation (((startIndex + jump) % n) + n) % n to handle both positive and negative jumps while maintaining the circular nature of the array. This formula ensures:

Positive jumps wrap around when exceeding array length
Negative jumps wrap around when going below index 0
The result is always a valid index between 0 and n-1

Example walkthrough with arr = [1,2,3,4,5] and startIndex = 0:

gen.next() → yields 1 (at index 0)
gen.next(1) → jumps to index 1, yields 2
gen.next(2) → jumps to index 3, yields 4
gen.next(6) → jumps 6 positions forward from index 3, wraps around to index 4, yields 5

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is recognizing that we need a stateful function that remembers its current position between calls - this naturally leads us to use a generator function in JavaScript/TypeScript.

When dealing with circular arrays, we need to handle wrapping around both ends. The challenge is handling both positive and negative jumps elegantly. Let's think through what happens:

For positive jumps: If we're at index 3 in a 5-element array and jump by 3, we'd go to index 6, which doesn't exist. We need to wrap around, so index 6 becomes index 1 (6 % 5 = 1).
For negative jumps: If we're at index 1 and jump by -3, we'd go to index -2. In a circular array, this should wrap to index 3 (counting backward from the end).

The standard modulo operator % in most languages doesn't handle negative numbers the way we need for circular indexing. For example, -2 % 5 gives -2, not 3 as we'd want.

To handle both cases uniformly, we use the formula (((startIndex + jump) % n) + n) % n:

First, (startIndex + jump) % n handles the basic wrapping for positive numbers
Adding n ensures the result is positive even for negative jumps
The final % n ensures we stay within bounds after adding n

This double modulo trick is a common pattern for circular array indexing that works for both positive and negative offsets.

The generator's yield expression is perfect here because it:

Pauses execution and returns the current value
Accepts the next jump value as input when resumed
Maintains state (the current index) between calls automatically

Solution Approach

We implement the solution using a TypeScript generator function with the following structure:

function* cycleGenerator(arr: number[], startIndex: number): Generator<number, void, number>

The implementation consists of these key components:

Store array length: We first capture const n = arr.length to use for modulo operations throughout the function.
Infinite loop with yield: The generator runs in a while (true) loop since it needs to continuously yield values without terminating. This is appropriate for a generator that should keep producing values as long as next() is called.
Yield current value and receive jump: The critical line is:
```
const jump = yield arr[startIndex];
```
This does two things simultaneously:
- Yields the value at the current startIndex position
- Receives the next jump value passed to gen.next(jump)
Update index with circular wrapping: After yielding, we update the index:
```
startIndex = (((startIndex + jump) % n) + n) % n;
```
Let's break down this formula step by step:
- (startIndex + jump): Calculate the raw new position
- First % n: Get the remainder, which could be negative
- + n: Add the array length to ensure a positive value
- Second % n: Normalize back to the valid range [0, n-1]
Example with negative jump: If startIndex = 1, jump = -3, and n = 5:
- (1 + (-3)) = -2
- -2 % 5 = -2
- -2 + 5 = 3
- 3 % 5 = 3 (final index)

The generator maintains state between calls - the startIndex variable persists across multiple next() invocations, allowing the generator to remember its current position in the circular array. This stateful behavior combined with the modulo arithmetic provides an elegant solution for circular array traversal with arbitrary jumps.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's trace through an example with arr = [10, 20, 30] and startIndex = 1:

Initial state: arr = [10, 20, 30], startIndex = 1, n = 3

First call - gen.next():

We're at index 1, so we yield arr[1] = 20
No jump value provided (undefined), so we treat it as 0
Update index: (((1 + 0) % 3) + 3) % 3 = 1
Current index remains 1

Second call - gen.next(2):

We're at index 1, so we yield arr[1] = 20
Jump value is 2
Update index: (((1 + 2) % 3) + 3) % 3 = 0
- 1 + 2 = 3
- 3 % 3 = 0
- 0 + 3 = 3
- 3 % 3 = 0
Current index is now 0

Third call - gen.next(-4):

We're at index 0, so we yield arr[0] = 10
Jump value is -4
Update index: (((0 + (-4)) % 3) + 3) % 3 = 2
- 0 + (-4) = -4
- -4 % 3 = -1 (in most languages)
- -1 + 3 = 2
- 2 % 3 = 2
Current index is now 2

Fourth call - gen.next(1):

We're at index 2, so we yield arr[2] = 30
Jump value is 1
Update index: (((2 + 1) % 3) + 3) % 3 = 0
- 2 + 1 = 3
- 3 % 3 = 0
- 0 + 3 = 3
- 3 % 3 = 0
Current index wraps back to 0

The circular wrapping ensures we always stay within valid array indices, regardless of whether we jump forward (positive) or backward (negative) by any amount.

Solution Implementation

1def cycle_generator(arr, start_index):
2    """
3    Generator function that cycles through an array based on jump values.
4  
5    Args:
6        arr: The array to cycle through
7        start_index: The initial index to start from
8      
9    Yields:
10        The current element at the index
11      
12    Returns:
13        A generator that yields array elements based on jump navigation
14    """
15    # Store the length of the array for modulo operations
16    array_length = len(arr)
17  
18    # Continue cycling indefinitely
19    while True:
20        # Yield the current element and receive the jump value for next iteration
21        jump_value = yield arr[start_index]
22      
23        # Calculate the next index using modulo to handle:
24        # 1. Positive jumps that wrap around the end
25        # 2. Negative jumps that wrap around the beginning
26        # The formula ((index % n) + n) % n ensures proper handling of negative indices
27        start_index = (((start_index + jump_value) % array_length) + array_length) % array_length
28
29
30# Example usage:
31# gen = cycle_generator([1, 2, 3, 4, 5], 0)
32# next(gen)        # 1 - Initial yield at index 0
33# gen.send(1)      # 2 - Jump 1 position forward to index 1
34# gen.send(2)      # 4 - Jump 2 positions forward to index 3
35# gen.send(6)      # 5 - Jump 6 positions forward (wraps around) to index 4
36

1import java.util.Iterator;
2import java.util.NoSuchElementException;
3
4/**
5 * Generator class that cycles through an array based on jump values
6 */
7class CycleGenerator implements Iterator<Integer> {
8    private int[] arr;
9    private int currentIndex;
10    private int arrayLength;
11    private Integer nextJumpValue;
12    private boolean isFirstCall;
13  
14    /**
15     * Constructor for CycleGenerator
16     * @param arr - The array to cycle through
17     * @param startIndex - The initial index to start from
18     */
19    public CycleGenerator(int[] arr, int startIndex) {
20        this.arr = arr;
21        this.currentIndex = startIndex;
22        this.arrayLength = arr.length;
23        this.nextJumpValue = 0;
24        this.isFirstCall = true;
25    }
26  
27    /**
28     * Check if there is a next element (always true for infinite cycling)
29     * @return true since the generator cycles indefinitely
30     */
31    @Override
32    public boolean hasNext() {
33        return true;
34    }
35  
36    /**
37     * Get the next element in the cycle
38     * @return The current element at the index
39     */
40    @Override
41    public Integer next() {
42        if (!hasNext()) {
43            throw new NoSuchElementException();
44        }
45      
46        // Store the current element to return
47        int currentElement = arr[currentIndex];
48      
49        // If not the first call, apply the jump
50        if (!isFirstCall) {
51            // Calculate the next index using modulo to handle:
52            // 1. Positive jumps that wrap around the end
53            // 2. Negative jumps that wrap around the beginning
54            // The formula ((index % n) + n) % n ensures proper handling of negative indices
55            currentIndex = (((currentIndex + nextJumpValue) % arrayLength) + arrayLength) % arrayLength;
56            currentElement = arr[currentIndex];
57        }
58      
59        isFirstCall = false;
60        return currentElement;
61    }
62  
63    /**
64     * Set the jump value for the next iteration
65     * @param jumpValue - The number of positions to jump
66     * @return The current element after applying the jump
67     */
68    public Integer nextWithJump(int jumpValue) {
69        // Calculate the next index using the jump value
70        currentIndex = (((currentIndex + jumpValue) % arrayLength) + arrayLength) % arrayLength;
71      
72        // Return the element at the new index
73        return arr[currentIndex];
74    }
75  
76    /**
77     * Example usage:
78     * CycleGenerator gen = new CycleGenerator(new int[]{1, 2, 3, 4, 5}, 0);
79     * gen.next()           // 1 - Initial yield at index 0
80     * gen.nextWithJump(1)  // 2 - Jump 1 position forward to index 1
81     * gen.nextWithJump(2)  // 4 - Jump 2 positions forward to index 3
82     * gen.nextWithJump(6)  // 5 - Jump 6 positions forward (wraps around) to index 4
83     */
84}
85

1#include <vector>
2#include <coroutine>
3#include <optional>
4
5/**
6 * Coroutine generator for cycling through an array based on jump values
7 * This implements a generator pattern using C++20 coroutines
8 */
9template<typename T>
10class Generator {
11public:
12    struct promise_type {
13        T current_value;
14        T jump_value = 0;
15      
16        Generator get_return_object() {
17            return Generator{std::coroutine_handle<promise_type>::from_promise(*this)};
18        }
19      
20        std::suspend_always initial_suspend() { return {}; }
21        std::suspend_always final_suspend() noexcept { return {}; }
22      
23        std::suspend_always yield_value(T value) {
24            current_value = value;
25            return {};
26        }
27      
28        void return_void() {}
29        void unhandled_exception() { std::terminate(); }
30    };
31  
32    using handle_type = std::coroutine_handle<promise_type>;
33  
34private:
35    handle_type coro;
36  
37public:
38    explicit Generator(handle_type h) : coro(h) {}
39    ~Generator() {
40        if (coro)
41            coro.destroy();
42    }
43  
44    // Move constructor and assignment
45    Generator(Generator&& other) noexcept : coro(std::exchange(other.coro, {})) {}
46    Generator& operator=(Generator&& other) noexcept {
47        if (this != &other) {
48            if (coro)
49                coro.destroy();
50            coro = std::exchange(other.coro, {});
51        }
52        return *this;
53    }
54  
55    // Delete copy operations
56    Generator(const Generator&) = delete;
57    Generator& operator=(const Generator&) = delete;
58  
59    // Get next value with optional jump parameter
60    std::optional<T> next(T jump = 0) {
61        if (!coro || coro.done())
62            return std::nullopt;
63          
64        coro.promise().jump_value = jump;
65        coro.resume();
66      
67        if (coro.done())
68            return std::nullopt;
69          
70        return coro.promise().current_value;
71    }
72};
73
74/**
75 * Generator function that cycles through an array based on jump values
76 * @param arr - The array to cycle through
77 * @param startIndex - The initial index to start from
78 * @returns A generator that yields array elements based on jump navigation
79 */
80Generator<int> cycleGenerator(const std::vector<int>& arr, int startIndex) {
81    // Store the length of the array for modulo operations
82    const int arrayLength = static_cast<int>(arr.size());
83  
84    // Continue cycling indefinitely
85    while (true) {
86        // Yield the current element and receive the jump value for next iteration
87        co_yield arr[startIndex];
88      
89        // Get the jump value from the promise
90        int jumpValue = co_await std::suspend_always{};
91      
92        // Calculate the next index using modulo to handle:
93        // 1. Positive jumps that wrap around the end
94        // 2. Negative jumps that wrap around the beginning
95        // The formula ((index % n) + n) % n ensures proper handling of negative indices
96        startIndex = (((startIndex + jumpValue) % arrayLength) + arrayLength) % arrayLength;
97    }
98}
99
100/**
101 * Alternative implementation without C++20 coroutines for compatibility
102 * Uses a class-based approach to maintain state between calls
103 */
104class CycleGeneratorClass {
105private:
106    const std::vector<int>& arr;
107    int currentIndex;
108    int arrayLength;
109  
110public:
111    /**
112     * Constructor initializes the generator with array and starting index
113     * @param array - The array to cycle through
114     * @param startIndex - The initial index to start from
115     */
116    CycleGeneratorClass(const std::vector<int>& array, int startIndex) 
117        : arr(array), currentIndex(startIndex), arrayLength(static_cast<int>(array.size())) {}
118  
119    /**
120     * Get next value and advance by jump amount
121     * @param jumpValue - Number of positions to jump (can be negative)
122     * @returns The element at the current index before jumping
123     */
124    int next(int jumpValue = 0) {
125        // Store current element to return
126        int currentElement = arr[currentIndex];
127      
128        // Calculate the next index using modulo to handle:
129        // 1. Positive jumps that wrap around the end
130        // 2. Negative jumps that wrap around the beginning
131        // The formula ((index % n) + n) % n ensures proper handling of negative indices
132        currentIndex = (((currentIndex + jumpValue) % arrayLength) + arrayLength) % arrayLength;
133      
134        return currentElement;
135    }
136};
137
138/**
139 * Example usage:
140 * std::vector<int> array = {1, 2, 3, 4, 5};
141 * 
142 * // Using coroutine version (C++20):
143 * auto gen = cycleGenerator(array, 0);
144 * auto val1 = gen.next(0);  // 1 - Initial yield at index 0
145 * auto val2 = gen.next(1);  // 2 - Jump 1 position forward to index 1
146 * auto val3 = gen.next(2);  // 4 - Jump 2 positions forward to index 3
147 * auto val4 = gen.next(6);  // 5 - Jump 6 positions forward (wraps around) to index 4
148 * 
149 * // Using class-based version:
150 * CycleGeneratorClass gen2(array, 0);
151 * int val1 = gen2.next(0);  // 1 - Initial value at index 0
152 * int val2 = gen2.next(1);  // 2 - Jump 1 position forward to index 1
153 * int val3 = gen2.next(2);  // 4 - Jump 2 positions forward to index 3
154 * int val4 = gen2.next(6);  // 5 - Jump 6 positions forward (wraps around) to index 4
155 */
156

1/**
2 * Generator function that cycles through an array based on jump values
3 * @param arr - The array to cycle through
4 * @param startIndex - The initial index to start from
5 * @yields The current element at the index
6 * @returns A generator that yields array elements based on jump navigation
7 */
8function* cycleGenerator(arr: number[], startIndex: number): Generator<number, void, number> {
9    // Store the length of the array for modulo operations
10    const arrayLength = arr.length;
11  
12    // Continue cycling indefinitely
13    while (true) {
14        // Yield the current element and receive the jump value for next iteration
15        const jumpValue = yield arr[startIndex];
16      
17        // Calculate the next index using modulo to handle:
18        // 1. Positive jumps that wrap around the end
19        // 2. Negative jumps that wrap around the beginning
20        // The formula ((index % n) + n) % n ensures proper handling of negative indices
21        startIndex = (((startIndex + jumpValue) % arrayLength) + arrayLength) % arrayLength;
22    }
23}
24
25/**
26 * Example usage:
27 * const gen = cycleGenerator([1, 2, 3, 4, 5], 0);
28 * gen.next().value     // 1 - Initial yield at index 0
29 * gen.next(1).value    // 2 - Jump 1 position forward to index 1
30 * gen.next(2).value    // 4 - Jump 2 positions forward to index 3
31 * gen.next(6).value    // 5 - Jump 6 positions forward (wraps around) to index 4
32 */
33

Time and Space Complexity

Time Complexity: O(1) per iteration

Each call to next() performs a constant amount of work:

Yielding a value: O(1)
Computing the next index using modulo operations: O(1)
Array access: O(1)

The generator itself runs indefinitely (infinite loop), but each individual iteration has constant time complexity.

Space Complexity: O(1)

The generator maintains only a fixed amount of state regardless of input size:

The startIndex variable: O(1)
The n variable storing array length: O(1)
No additional data structures are created
The generator does not create a copy of the input array, it only references it

Note that this analysis excludes the space used by the input array itself, as it's passed by reference and not created by the generator function.

Common Pitfalls

1. First `next()` Call Handling

The most common pitfall is forgetting that the first call to next() on a generator doesn't accept any argument (or the argument is ignored). This leads to confusion when trying to pass a jump value on the first call.

Pitfall Example:

gen = cycle_generator([1, 2, 3, 4, 5], 0)
# Attempting to jump on first call - this won't work as expected!
result = gen.send(2)  # Raises TypeError: can't send non-None value to a just-started generator

Solution: Always use next() for the first call to initialize the generator:

gen = cycle_generator([1, 2, 3, 4, 5], 0)
first_value = next(gen)  # Properly initialize the generator
second_value = gen.send(2)  # Now you can send jump values

2. Uninitialized Jump Value

When yield receives no value (like in the first next() call), it returns None. If not handled, this causes a TypeError when trying to add None to an integer.

Pitfall Example:

def cycle_generator(arr, start_index):
    array_length = len(arr)
    while True:
        jump_value = yield arr[start_index]
        # This will fail on second iteration if jump_value is None
        start_index = (((start_index + jump_value) % array_length) + array_length) % array_length

Solution: Provide a default value for when jump_value is None:

def cycle_generator(arr, start_index):
    array_length = len(arr)
    while True:
        jump_value = yield arr[start_index]
        # Handle None case (when next() is called without argument)
        if jump_value is None:
            jump_value = 0  # Default to no jump
        start_index = (((start_index + jump_value) % array_length) + array_length) % array_length

3. Incorrect Modulo Formula for Negative Numbers

A simpler but incorrect approach might use just (start_index + jump_value) % array_length, which fails for negative jumps in Python.

Pitfall Example:

# Incorrect implementation
start_index = (start_index + jump_value) % array_length
# If start_index = 1, jump_value = -3, array_length = 5
# Result: (1 + (-3)) % 5 = -2 % 5 = -2 (invalid index!)

Solution: Use the double modulo formula to ensure positive results:

# Correct implementation
start_index = (((start_index + jump_value) % array_length) + array_length) % array_length
# Result: ((-2 % 5) + 5) % 5 = (-2 + 5) % 5 = 3 (valid index)

4. Not Validating Input Parameters

Failing to validate the starting index or empty array can cause immediate failures.

Pitfall Example:

gen = cycle_generator([], 0)  # Empty array
next(gen)  # IndexError: list index out of range

gen = cycle_generator([1, 2, 3], 5)  # Invalid start index
next(gen)  # IndexError: list index out of range

Solution: Add validation at the beginning of the generator:

def cycle_generator(arr, start_index):
    if not arr:
        raise ValueError("Array cannot be empty")
  
    array_length = len(arr)
    if not (0 <= start_index < array_length):
        raise ValueError(f"Start index {start_index} out of bounds for array of length {array_length}")
  
    while True:
        jump_value = yield arr[start_index]
        if jump_value is None:
            jump_value = 0
        start_index = (((start_index + jump_value) % array_length) + array_length) % array_length

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don't know

2757. Generate Circular Array Values 🔒

Problem Description

Intuition

Solution Approach

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Example Walkthrough

Solution Implementation

Time and Space Complexity

Common Pitfalls

1. First next() Call Handling

2. Uninitialized Jump Value

3. Incorrect Modulo Formula for Negative Numbers

4. Not Validating Input Parameters

Recommended Readings

1. First `next()` Call Handling