We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Circular Array Loop

Difficulty: Medium

Problem Description

You are playing a game involving a circular array of non-zero integers nums. Each nums[i] denotes the number of indices forward/backward you must move if you are located at index i. If nums[i] is positive, move nums[i] steps forward, and if nums[i] is negative, move nums[i] steps backward. A cycle in the array consists of a sequence of indices seq of length k where following the movement rules results in a repeating index sequence, every nums[seq[j]] is either all positive or all negative, and k > 1. Return true if there is a cycle in nums, or false otherwise.

Key Insights

  • The array is circular, meaning you can wrap around from the last element back to the first and vice versa.
  • A valid cycle must consist of indices that all move in the same direction (all positive or all negative).
  • The problem can be solved using a modified version of Floyd's Tortoise and Hare algorithm for cycle detection.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To detect a cycle in the circular array, we can utilize a two-pointer approach similar to Floyd's Tortoise and Hare algorithm. We traverse the array using a slow pointer and a fast pointer. The slow pointer moves one step at a time, while the fast pointer moves two steps. If we ever meet, it indicates the presence of a cycle. However, we must ensure that all elements in this cycle move in the same direction, which can be checked by the sign of the values. If a cycle is detected, we return true; otherwise, we continue until all indices have been checked.

Code Solutions

def circularArrayLoop(nums):
    n = len(nums)
    
    for i in range(n):
        slow, fast = i, i
        direction = nums[i] > 0  # Check the direction of the first element
        
        while True:
            slow = (slow + nums[slow]) % n
            fast = (fast + nums[fast]) % n
            fast = (fast + nums[fast]) % n
            
            if slow == fast:  # Cycle detected
                if slow == (slow + nums[slow]) % n:  # Check if the cycle length > 1
                    break
                return False
            
            if (nums[slow] > 0) != direction or (nums[fast] > 0) != direction:  # Direction mismatch
                break
        
        # Mark all elements along the path as visited
        if slow == fast:
            slow = i
            while True:
                next_index = (slow + nums[slow]) % n
                nums[slow] = 0  # Mark as visited
                slow = next_index
                if slow == fast:
                    break
    
    return False
← Back to All Questions