Solution: Circular Array Loop

Let's solve the Circular Array Loop problem using the Fast and Slow Pointers pattern.

Statement

We are given a circular arrayA circular array is a type of array, where the last element is followed by the first element, forming a loop or circle. of non-zero integers, nums, where each integer represents the number of steps to be taken either forward or backward from its current index. Positive values indicate forward movement, while negative values imply backward movement. When reaching either end of the array, the traversal wraps around to the opposite end.

The input array may contain a cycle, which is a sequence of indexes characterized by the following:

  • The sequence starts and ends at the same index.
  • The length of the sequence is at least two.
  • The loop must be in a single direction, forward or backward.

Note: A cycle in the array does not have to originate at the beginning. It may begin from any point in the array.

Your task is to determine if nums has a cycle. Return TRUE if there is a cycle. Otherwise return FALSE.

Constraints:

  • 11 \leq nums.length 104\leq 10^4
  • 5000-5000 \leq nums[i] 5000\leq 5000
  • nums[i] !=0!= 0

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which to follow based on considerations such as time complexity and implementation constraints.

Naive approach

The naive approach involves iterating through each element of the input array. In each iteration, we start from the current element and check for cycles in both forward and backward directions. We also keep an additional array to track visited elements. If a cycle is detected during this process, we return TRUE. However, if the direction of the cycle changes at any point, we’ll move to the next iteration. We’ll repeat this until we find the cycle or traverse the complete array.

For each element in the outer loop, there is an inner loop that explores potential cycles, resulting in a time complexity of O(n2)O(n^2). The space complexity is O(n)O(n) because we use extra space to keep track of the visited elements. This makes it an inefficient approach for large input arrays.

Optimized approach using fast and slow pointers

The cycle in the circular array can be found efficiently using the fast and slow pointers technique without requiring any extra memory. Traverse the input array and in each iteration:

  • Move the slow pointer once as per the value it is pointing to.
  • Move the fast pointer twice. First, according to the value it is currently pointing to, and then once again based on the new value it is now pointing to.

After each movement, check if a valid cycle can be formed. A valid cycle can exist if:

  • It consists of at least two elements.
  • It is unidirectional.

After the slow pointer has been advanced by one step and the fast pointer by two steps, check if they are at the same index. If they are, it indicates that the cycle is detected. Since the fast pointer will cover twice the distance as the slow pointer, it is guaranteed that the fast pointer will meet the slow pointer at some index if the cycle exists.

However, if moving a pointer takes it back to its current position, it indicates that the cycle will have only a single element, which is not valid. Additionally, if the values at the array indexes of the slow and fast pointers have different signs, i.e., one pointer is pointing to a positive value, and the other is pointing to a negative value, a valid cycle cannot be formed. In both scenarios, move to the next iteration.

The algorithm involves iterating through each index of nums. For every index, i, perform the following steps:

  1. Initialize fast and slow pointers to the current index i.

  2. Move the slow pointer, either forward or backward, depending on the current value it is pointing to, nums[i]. For example, if the value is 3-3, the slow pointer is moved three indexes backward. Similarly, if the value is 22, the slow pointer is moved two indexes forward.

  3. Now, check if a valid cycle can be formed. For this, we have two primary checks:

    • If the index of the new value pointed to by slow is the same as the index of the previous value pointed to by slow, that is, the pointer is forming a self-loop, then the next iteration starts.

    • Observe the sign of the previous value pointed to by slow and the sign of the new value it points to. If both values have different signs, that is, the pointer is not moving in a single direction, then the next iteration starts.

    If any of the conditions above fail, move to step 44.

  4. Move the fast pointer twice in a similar fashion, and after every move, check for the validity of the cycle using the same checks as above. If a valid cycle can’t be formed, move to the next index of nums.

  5. Now, check for the existence of the cycle. If the slow and fast pointers meet at the same index, a cycle is detected. Return TRUE in this case. Otherwise, continue moving the pointers until we determine whether or not a cycle exists.

Note: We only move to the next index if a valid cycle cannot be formed with the current index.

If no cycle is detected for any index, return FALSE.

Here’s the demonstration of the steps above:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.