Single Cycle Check

Check out this cool algorithm I ran into on AlgoExpert. I like the problem’s apparent simplicity, yet the need to really think it through, with all of its edge cases to be able to successfully solve it. In order to solve it optimally, you have to think outside the box.

Here’s the problem:

You’re given an array of integers where each integer represents a jump of its value in an array. For instance, the integer 2 represents a jump of two indices forward in the array; the integer -3 represents a jump of three indices backward in the array.

If a jump spills past the array’s bounds, it wraps over to the other side. For instance, a jump of -1 at index 0 brings us to the last index in the array. Similarly, a jump of 1 at the past index in the array brings us to index 0.

Write a function that returns a boolean representing whether the jumps in the array form a single cycle. A single cycle occurs if, starting at any index in the array and following the jumps, every element is visited exactly once before landing back on the starting index.

At first glance this doesn’t seem all that complex. Optimal time complexity is O(n) and optimal space is O(1). This fact makes it a little harder, but let’s see the challenges as they arise.

Understanding the problem:

Consider the simple array of [2, 2, -1]. The problem says we can start at any index, so we will pick 0. The value at array[0] is 2, so we will jump two spaces forward, marked in blue.

We have visited array[0] and now array[2] which are marked in green.

We jump one space back and visit array[1]. The only part that is left is to end up back at the index we started on. Since array[1] has a value of 2, we jump two spaces forward. Because that goes out of the bounds of the array, we wrap back to the beginning and end on array[0].

Because we started and ended at array[0] and visited each item exactly once, this is a single cycle. Simple enough.

Let’s look at one that is not a single cycle.

In this case, we would bounce back and forth from array[0] to array[1], and never visit array[2]. Not a single cycle. Make sense?

Non-Optimal Solution

We could create an array to keep track of the number of times we visited each item as the value, and if there is a zero or any number other than 1, it would not be a single cycle. Although this would work, it would not be in O(1) space, and therefore not optimal. So what else can we do?

Optimal Solution

If we think about the input data, the array, we can know exactly how many items we have to visit to complete a cycle. If you consider this, if at any point in time, we end up back at the element we started with, without visiting array.length number of elements, the conditions set in the problem are not satisfied. Alternatively, if we have visited array.length number of elements, and we do not end up back at the element on which we started, again, we know the conditions set in the problem are not satisfied.

Considering this, there are three conditions we need to track.

1. We need to visit n number of elements where n = array.length
2. If, after we have visited every element, we are not back at the starting point, we have a problem
3. If we have visited more than one element, and not yet visited every other element (1<n<array.length), and we find ourselves back at the starting point, we have a problem

With this solution, we are aiming for O(n) time complexity because either we are visiting every element in the input array once, or short-circuiting before then because the data did not meet the criteria. Space complexity will be O(1) because we are not creating any additional arrays or structures that are dependent on the input size, only some variables to keep track of conditions.

Code

Working in JavaScript, we start with writing the algorithm by declaring the variables to keep track of the number of elements we have visited and the current index that we are visiting and initialize them to equal zero.

The next step is to create a loop that will run as long as the number of elements that we have visited is less than the length of the input array. We can start by short-circuiting the loop if we ever get back to the starting index before visiting each element.

So what do we need to do in the loop? As we are looping through, we need to increment the number of items visited, figure out which index we need to visit next, and figure out whether or not we end on the index that we started on. We can do most of this easily and then abstract finding the next index into a helper method and pass the current index and the array as arguments.

Ok so, finding the next index is the hardest part. We have to find how far forward or backward we need to move and handle some edge cases. We can start by declaring a variable that finds the value at the current index, because that tells us where we need to go next. Then we can declare another variable that adds the “leap” to the current index to find the next index.

Great! … but wait… we need to be able to circle back around and start at the beginning to keep going if we reach the end of the array, or circle back to the end if we reach the beginning when leaping to the next index. So if my array.length is equal to 5, and I am at the 4th index, and the value is 5, I would go out of bounds. So what can we do?

The easiest way to solve this problem is to use the modulo operator. We can find the remainder of the currentIndex + leap divided by the length of the array. This remainder will always give us exactly where we need to be, even if the value loops us through the array a gazillion times.

So you might think Great! Let’s just return the next index! We’re done! But, not quite. This is because the values that tell us the size of the leap can be positive or negative, so we need to account for both cases. If the next index is positive we are good to go, but if it is negative we have to do some work. We can add the next index to the length of the array to find the array position we will end up on if the leap is negative.

It’s recognizing these edge cases that make or break this algorithm. So altogether we have the following code:

O(n) time and O(1) space! Single Cycle Check Algorithm solved! Bravo!