2757. Generate Circular Array Values

Medium
Leetcode Link

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.

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

In a binary min heap, the maximum element can be found in:

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:

  1. A generator function named cycleGenerator is declared, which takes two parameters: an array arr and a starting index startIndex.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

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

  1. 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].

  2. 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.

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

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

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.

  1. We create a generator using the cycleGenerator function and initialize it with our array and starting index:
1const gen = cycleGenerator([10, 20, 30, 40, 50], 2);

  1. 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.

  2. 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.

  3. 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.

  4. 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
Not Sure What to Study? Take the 2-min Quiz：

Which of these properties could exist for a graph but not a tree?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫