Solution: Circular Array Loop

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:

• $1 \leq$ nums.length $\leq 10^3$
• $-5000 \leq$ nums[i] $\leq 5000$
• nums[i] $!= 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(n^2)$. The space complexity is $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