2757. Generate Circular Array Values

Medium

Problem Description

In this LeetCode problem, we're asked to simulate a circular traversal through an array using a generator function. A circular array means that after reaching the end of the array, the next element is again the first element of the array, and similarly, if we are at the beginning of the array and we need to go back, we should end up at the end of the array.

We are given an array arr and an initial startIndex from where to start yielding elements when the generator's next method is called. For every subsequent call to next, a jump value is provided, which determines the number of steps to move from the current position. If jump is positive, we move forward, and if jump is negative, we move backward. Due to the circular nature of the array, these movements might wrap around the beginning or the end of the array. The problem is to correctly calculate the next index considering these wraps.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key to solving this problem is understanding how to handle the circular aspect of the array traversal. We need to yield the element at startIndex first, then update the index in a circular manner every time we receive a new jump value.

We do this by using modular arithmetic. Adding the jump value to startIndex and then taking the remainder of dividing by the length of the array (n) ensures that we cycle through indices 0 to n-1. However, in JavaScript and TypeScript, if jump is negative, using the modulo operator directly would give us a negative index. To handle the negative indices correctly, we add n to the sum and then take the modulo again. This effectively rotates the indices in a circular fashion while keeping them within the valid range of array indices.

The use of a generator function simplifies the iterative yielding of values, handling state between the yields, and accepting the jump input each time the generator resumes.

Solution Approach

The main algorithm in the solution is based on the concept of a generator function in TypeScript, which allows us to lazily produce a sequence of values on demand using the yield keyword. In our case, the sequence of values is the elements of the array, produced according to the circular traversal defined by the jump values.

Here's a step-by-step breakdown of the solution approach, explaining the algorithm, data structures, and pattern used:

A generator function named cycleGenerator is declared, which takes two parameters: an array arr and a starting index startIndex.
The length of the array is stored in a constant n. We use n for modulo operations to ensure indices are kept within bounds. The array's length will not change during the execution of the generator, so calculating it once is efficient.
The generator enters an infinite while (true) loop. This loop will continue to produce values every time the generator is resumed with a gen.next() call.
Inside the loop, the current element corresponding to startIndex is yielded via the yield statement. When yield is executed, the generator function is paused, and the yielded value (in this case, arr[startIndex]) is returned back to the caller.
On subsequent next calls, a jump value is passed, and the generator function resumes. The next index is calculated by adding the jump to startIndex and then applying modulo n to keep the index within bounds. As JavaScript's modulo can yield negative results, (startIndex + jump) % n is added to n and modulo n is taken again to ensure the index is positive.

startIndex = (((startIndex + jump) % n) + n) % n;

The calculation ((startIndex + jump) % n) can yield a negative index if jump is negative. By adding n and taking the modulo again ((... + n) % n), we guarantee that the final index is in the range [0, n-1].
The updated startIndex value will be used in the next iteration to yield the next element, and the process repeats each time gen.next(jump) is called.

The algorithm leverages the efficiency of generators for state management between yields and the simplicity of modular arithmetic to handle circular indexing. No additional data structures are needed since we directly operate on the given array and modify the index accordingly.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Assume we have an array arr = [10, 20, 30, 40, 50] and we want to start our circular traversal from startIndex = 2, which corresponds to the value 30 in the array.

We create a generator using the cycleGenerator function and initialize it with our array and starting index:

const gen = cycleGenerator([10, 20, 30, 40, 50], 2);

When we first call gen.next().value, it will yield the value at startIndex = 2, which is 30. The generator is now paused at the yield keyword.
Next, we call gen.next(2).value, meaning we want to jump two places forward from index 2. Since our array has 5 elements, index 4 is 50, which is what the generator yields this time.
If we call gen.next(1).value now, we want to jump one more place forward, but since we're at the end of the array, we wrap around to the beginning, so the generator yields the first element of the array which is 10.
To jump backwards, we can pass a negative value to next, such as gen.next(-3).value. If our current position was index 0, we will wrap around to the end of the array and move two places back, ending up at index 2. Given our array, the returned value would be 30.

In terms of the implementation details, here's how each step would operate:

The array's length n is determined (n = 5 in this case).
The infinite while loop begins execution, preparing to yield values upon each next invocation.
Yield the value arr[startIndex] where startIndex = 2 during the first call, then use calculation for subsequent indexes.
For each subsequent call to next, accept a jump value and calculate the new index with the modulo operation outlined in the solution.
If jump is positive, the new position is found easily with (startIndex + jump) % n.
If jump is negative, the modulo operation may yield a negative result. In this case, the expression ((startIndex + jump) % n + n) % n ensures that the resulting index is positive and within the valid range.

The efficiency of this solution is in its simplicity: it uses fundamental programming concepts like loops and modular arithmetic to solve the problem of circular array traversal without the need for complex data structures or additional memory overhead.

Solution Implementation

1# A generator function that creates an infinite cycle over the input list.
2# You can jump to any index in the list by providing the "jump" value when calling next().
3# @param arr The list to be cycled through.
4# @param start_index The index at which to start the cycle.
5# @returns A generator that yields values from the list.
6def cycle_generator(arr, start_index):
7    # Determine the length of the list to handle the cycling logic.
8    n = len(arr)
9  
10    # Start an infinite loop to allow the cycling.
11    while True:
12        # Yield the current element of the list and receive the jump value from the next() call.
13        jump = yield arr[start_index]
14      
15        # Calculate the new start_index by adding the jump value and using modulo operation
16        # to ensure it wraps around the list. The additional +n ensures the result is non-negative.
17        start_index = ((start_index + jump) % n + n) % n
18
19# Example usage:
20# Create an instance of the generator, starting at index 0 of the provided list.
21gen = cycle_generator([1, 2, 3, 4, 5], 0)
22
23# Calling next() without a parameter to retrieve the first value, which will be at the starting index.
24print(next(gen))   # Outputs: 1
25
26# Calling gen.send(jump) with a parameter to jump to the next index in the cycle.
27print(gen.send(1))  # Outputs: 2 (jumps 1 index forward)
28
29# Again calling gen.send(jump) with a different parameter to jump to subsequent indices in the cycle.
30print(gen.send(2))  # Outputs: 4 (jumps 2 indices forward from the current position)
31
32# Demonstrate the cycling behavior with a jump that exceeds the list's length.
33print(gen.send(6))  # Outputs: 5 (jumps 6 indices forward, cycling back to the end of the list)
34

1import java.util.function.IntUnaryOperator;
2
3public class CycleIterator implements IntUnaryOperator {
4    private final int[] array;
5    private int currentIndex;
6
7    // Constructor to initialize the iterator with the array and the starting index.
8    public CycleIterator(int[] array, int startIndex) {
9        this.array = array;
10        // Normalize the start index in case it's negative or greater than the array length.
11        this.currentIndex = ((startIndex % array.length) + array.length) % array.length;
12    }
13
14    // The method to get the next element. Also receives a "jump" value to move the current index.
15    public int next(int jump) {
16        // Retrieve the current element.
17        int currentElement = array[currentIndex];
18        // Update the currentIndex with the jump, making sure it's within the array bounds.
19        currentIndex = (((currentIndex + jump) % array.length) + array.length) % array.length;
20        // Return the current element.
21        return currentElement;
22    }
23
24    // Java's applyAsInt method to adhere to the IntUnaryOperator functional interface.
25    @Override
26    public int applyAsInt(int operand) {
27        return next(operand);
28    }
29}
30
31// Example usage:
32public class CycleGeneratorExample {
33    public static void main(String[] args) {
34        // Create an instance of CycleIterator, starting at index 0 of the provided array.
35        CycleIterator iterator = new CycleIterator(new int[]{1, 2, 3, 4, 5}, 0);
36
37        // Get the first value, which will be at the starting index.
38        System.out.println(iterator.next(0)); // Outputs: 1
39
40        // Next(jump) with a parameter to jump to the next index in the cycle.
41        System.out.println(iterator.next(1)); // Outputs: 2
42
43        // Again, call next(jump) with a different jump value.
44        System.out.println(iterator.next(2)); // Outputs: 4
45
46        // Demonstrate the cycling behavior with a jump that exceeds the array's length.
47        System.out.println(iterator.next(6)); // Outputs: 5
48    }
49}
50

1#include <iostream>
2#include <vector>
3#include <functional>
4
5// A class representing a generator that produces a cycle over the input vector.
6class CycleGenerator {
7private:
8    std::vector<int> arr;  // The vector to be cycled through.
9    size_t startIndex;     // The current starting index within the vector.
10
11public:
12    // Construct the generator with a given vector and a start index.
13    CycleGenerator(const std::vector<int>& arr, size_t startIndex) : arr(arr), startIndex(startIndex) {}
14
15    // Function to get the next value in the cycle.
16    // Optionally, jump to a different index in the vector.
17    int next(int jump = 0) {
18        // Determine the length of the vector to handle the cycling logic.
19        const size_t n = arr.size();
20      
21        // Get the current element to yield.
22        int currentValue = arr[startIndex];
23      
24        // Calculate the new startIndex by adding the jump value.
25        // Using modulo operation to wrap around if necessary.
26        // The additional +n and modulo is used to ensure the result is non-negative.
27        startIndex = (((startIndex + jump) % n) + n) % n;
28      
29        // Return the current value.
30        return currentValue;
31    }
32};
33
34// Example usage:
35int main() {
36    // Create an instance of the generator starting at index 0 of the provided vector.
37    CycleGenerator gen({1, 2, 3, 4, 5}, 0);
38
39    // Retrieve the first value, which will be at the starting index.
40    std::cout << gen.next() << std::endl;  // Outputs: 1
41  
42    // Jump to the next index in the cycle by providing a jump value.
43    std::cout << gen.next(1) << std::endl; // Outputs: 2 (jumps 1 index forward)
44  
45    // Jump to subsequent indices in the cycle with a different jump value.
46    std::cout << gen.next(2) << std::endl; // Outputs: 4 (jumps 2 indices forward from the current position)
47  
48    // Demonstrate the cycling behavior with a jump that exceeds the vector's length.
49    std::cout << gen.next(6) << std::endl; // Outputs: 5 (jumps 6 indices forward, cycling back to the end of the vector)
50  
51    return 0;
52}
53

1// A generator function that creates an infinite cycle over the input array.
2// You can jump to any index in the array by providing the "jump" value when calling next().
3// @param arr The array to be cycled through.
4// @param startIndex The index at which to start the cycle.
5// @returns A generator that yields values from the array.
6function* cycleGenerator(arr: number[], startIndex: number): Generator<number, void, number> {
7    // Determine the length of the array to handle the cycling logic.
8    const n = arr.length;
9  
10    // Start an infinite loop to allow the cycling.
11    while (true) {
12        // Yield the current element of the array.
13        const jump = yield arr[startIndex];
14      
15        // Calculate the new startIndex by adding the jump value and applying modulo operation.
16        // The additional +n and modulo is used to ensure the result is non-negative.
17        startIndex = (((startIndex + jump) % n) + n) % n;
18    }
19}
20
21// Example usage:
22// Create an instance of the generator, starting at index 0 of the provided array.
23const gen = cycleGenerator([1,2,3,4,5], 0);
24
25// Calling next() without a parameter to retrieve the first value, which will be at the starting index.
26console.log(gen.next().value);  // Outputs: 1
27
28// Calling next(jump) with a parameter to jump to the next index in the cycle.
29console.log(gen.next(1).value); // Outputs: 2 (jumps 1 index forward)
30
31// Again calling next(jump) with a different parameter to jump to subsequent indices in the cycle.
32console.log(gen.next(2).value); // Outputs: 4 (jumps 2 indices forward from the current position)
33
34// Demonstrate the cycling behavior with a jump that exceeds the array's length.
35console.log(gen.next(6).value); // Outputs: 5 (jumps 6 indices forward, cycling back to the end of the array)
36

Time and Space Complexity

Time Complexity

The time complexity of each call to gen.next() is O(1), presuming that modular arithmetic and yield operations are constant-time operations. This is because there is only a single step each time the generator resumes after yielding—an update to startIndex using arithmetic operations.

Space Complexity

The space complexity of the generator function is O(1). No additional space is required proportional to the input size or the number of iterations because the state is encapsulated within the generator's internal variables, and no new memory allocation is occurring within the generator function after it's been instantiated.

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

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don't know