class Solution:
def circularArrayLoop(self, nums: List[int]) -> bool:
# Get the length of the input list
length = len(nums)
# Define a function to find the next index in a circular manner
def get_next_index(current_index):
# Calculate the next index considering wrapping around
return (current_index + nums[current_index]) % length
# Iterate over all elements in the array
for i in range(length):
# Skip if the current element is already marked as 0, indicating it's not part of a loop
if nums[i] == 0:
continue
# Initialize the slow and fast pointers for cycle detection
slow_pointer = i
fast_pointer = get_next_index(i)
# Continue moving pointers while the signs of the elements indicate a potential loop
# This also ensures that we are not mixing cycles of different directions
while nums[slow_pointer] * nums[fast_pointer] > 0 and nums[slow_pointer] * nums[get_next_index(fast_pointer)] > 0:
# If the slow and fast pointers meet, a cycle is detected
if slow_pointer == fast_pointer:
# Check to ensure the loop is longer than 1 element
if slow_pointer != get_next_index(slow_pointer):
return True
# If the loop is just one element, break and mark it as non-looping
break
# Move slow pointer by one step and fast pointer by two steps
slow_pointer = get_next_index(slow_pointer)
fast_pointer = get_next_index(get_next_index(fast_pointer))
# Mark all visited elements as 0 to avoid revisiting and repeated calculations
# This process will also ensure elimination of non-loop elements
index = i
while nums[index] * nums[get_next_index(index)] > 0:
next_index = get_next_index(index)
nums[index] = 0
index = next_index
# If no loop is found, return False
return False
# Intuition
# To address this problem, we need to consider that a cycle can only exist if we're moving consistently in one direction and eventually end up where we started. This naturally brings the "fast and slow pointers" technique to mind, which is often used for cycle detection in linked lists.
# The fast and slow pointers method involves two pointers moving at different speeds, and if there is a cycle, they will eventually meet. We apply the same principle here:
# The slow pointer moves one step at a time.
# The fast pointer moves two steps at a time.
# If slow and fast meet at the same index, and this index is not the same as the next step (to prevent single-element loops, which aren't considered valid cycles), we have found a cycle.
# At each step, we also verify that the direction does not change. If the product of nums[slow] and nums[fast] is positive, they are either both positive or both negative, thus maintaining a consistent direction. If this product is negative or if we reach an element that is already marked as visited (a value of 0), we do not have a valid cycle from that start point.
# For each element, if it does not lead to a cycle, we mark the visited elements as 0 to avoid re-checking them in the future, thereby optimizing our algorithm. This marking also helps to invalidate any non-cycle paths swiftly.
# Overall, the algorithm is to iterate over each element and use the fast and slow pointer method to detect a cycle. If any cycle is found, return true. After checking all possibilities, if no cycle is found, return false.
# Solution Approach
# The implementation of the solution for detecting a cycle in the circular array follows these main steps:
# Array Length Extraction: We start by obtaining the length n of the input array nums. This is crucial since we need to calculate the next index correctly within the circular context:
# n = len(nums)
# Helper Function for Index Calculation: Since the array is circular, we define a function named next() that takes an index i and returns the next index we should move to, according to nums[i], and wraps around the array if necessary:
# def next(i):
# return (i + nums[i]) % n
# We ensure that the result of the movement remains within the bounds of the array indices by taking the modulo with n.
# Main Loop to Check for Cycles: We iterate through each element in the array to check for cycles starting from that index:
# for i in range(n):
# if nums[i] == 0: # Skip already marked elements (no cycle from this point)
# continue
# Fast and Slow Pointers Initialization: For each starting index, we initiate slow and fast pointers, which represent the current position of each pointer:
# slow, fast = i, next(i)
# Cycle Detection Loop: Next, we loop to detect cycles using the following conditions:
# The product of nums[slow] and nums[fast] must be positive, indicating they move in the same direction.
# The product of nums[slow] and nums[next(fast)] must also be positive, ensuring that the fast pointer also continues in the same direction after two moves.
# while nums[slow] * nums[fast] > 0 and nums[slow] * nums[next(fast)] > 0:
# if slow == fast: # Pointers meet, indicating a potential cycle
# if slow != next(slow): # Check to avoid single-length cycle
# return True
# break
# Marking Elements: If not a valid cycle, we need to mark elements associated with the failed attempt to find a cycle to prevent re-processing them in future iterations. This is achieved by setting each involved element to 0:
# j = i
# while nums[j] * nums[next(j)] > 0:
# nums[j] = 0 # Marking the element
# j = next(j)
# Final Return: After exhaustively checking all indices, if no cycle is found, the function returns false.
# This solution leverages the cyclical two-pointer technique to identify cycles and uses in-place marking to improve efficiency by reducing redundant checks. The use of the modulo operator ensures proper index wrapping within the circular array boundaries, and thorough condition checks maintain consistency in direction for cycle validation.