2757. Generate Circular Array Values
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.
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 arrayarr
and a starting indexstartIndex
. -
The length of the array is stored in a constant
n
. We usen
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 agen.next()
call. -
Inside the loop, the current element corresponding to
startIndex
is yielded via theyield
statement. Whenyield
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, ajump
value is passed, and the generator function resumes. The next index is calculated by adding thejump
tostartIndex
and then applying modulon
to keep the index within bounds. As JavaScript's modulo can yield negative results,(startIndex + jump) % n
is added ton
and modulon
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 ifjump
is negative. By addingn
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 timegen.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 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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 atstartIndex = 2
, which is30
. The generator is now paused at theyield
keyword. -
Next, we call
gen.next(2).value
, meaning we want to jump two places forward from index2
. Since our array has 5 elements, index4
is50
, 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 is10
. -
To jump backwards, we can pass a negative value to
next
, such asgen.next(-3).value
. If our current position was index0
, we will wrap around to the end of the array and move two places back, ending up at index2
. Given our array, the returned value would be30
.
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 eachnext
invocation. - Yield the value
arr[startIndex]
wherestartIndex = 2
during the first call, then use calculation for subsequent indexes. - For each subsequent call to
next
, accept ajump
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.
Which data structure is used to implement priority queue?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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 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
Want a Structured Path to Master System Design Too? Donāt Miss This!