Leetcode 457. Circular Array Loop

Problem

You are given an array of non-zero integers where the array is conceptually circular (the element after the last element is the first element). Each integer in the array represents the number of positions to move from the current index:

• A positive value means move forward (to the right)
• A negative value means move backward (to the left)

Your task is to determine if there exists a valid cycle in this array. A valid cycle must satisfy these conditions:

1. The cycle contains more than one element (length > 1)
2. All movements in the cycle must be in the same direction (either all forward or all backward)
3. Following the jump pattern from any element in the cycle will eventually return to that element

Requirements

1. Return true if a valid cycle exists, false otherwise
2. Handle the circular nature of the array correctly (wrapping around at boundaries)
3. A cycle of length 1 (an element pointing to itself) is NOT valid
4. All elements in a cycle must move in the same direction

Constraints

• 1 ≤ nums.length ≤ 5000
• -1000 ≤ nums[i] ≤ 1000
• nums[i] ≠ 0
• Challenge: Can you solve this in O(n) time with O(1) extra space?

Examples

Example 1:

Input: nums = [2, -1, 1, 2, 2] Output: true Explanation: Starting at index 0: 0 → 2 → 3 → 0 (forms a cycle) All jumps are positive (forward direction) Cycle length is 3 (more than 1)

Example 2:

Input: nums = [-1, 2] Output: false Explanation: From index 0: 0 → 1 → 0 (mixed directions: backward then forward) From index 1: 1 → 0 → 1 (mixed directions: forward then backward) No valid unidirectional cycle exists

Example 3:

Input: nums = [-2, 1, -1, -2, -2] Output: false Explanation: No valid cycle exists where all movements are in the same direction

Example 4:

Input: nums = [1, 1, 2] Output: false Explanation: From index 0: 0 → 1 → 2 → 1 (reaches index 1 again) Index 1 points to itself (cycle of length 1), which is invalid

Hint 1: Detecting Cycles Think about using a slow and fast pointer approach (similar to Floyd's cycle detection algorithm). From each starting position, use two pointers moving at different speeds to detect if they meet, which would indicate a cycle.

Hint 2: Direction Consistency Before entering the cycle detection loop, check if the current move and the next move are in the same direction. If at any point the directions differ, you know this path cannot form a valid cycle. You can check direction by examining the signs of the values.

Hint 3: Avoiding Single-Element Cycles A cycle of length 1 occurs when an element points to itself. You can check this by calculating the next index and seeing if it equals the current index. These should be immediately rejected.

Hint 4: Marking Visited Elements For O(1) space solution, mark elements that you've proven cannot be part of a valid cycle by setting them to 0 (or using another strategy that doesn't require extra arrays). This prevents redundant checking.

Full Solution `` Explanation:

The solution uses Floyd's cycle detection algorithm (slow/fast pointers) with modifications for this problem:

1. Next Index Calculation: We handle the circular nature by using modulo to wrap around the array boundaries.

2. Direction Checking: We ensure all elements in a potential cycle move in the same direction by comparing signs of values.

3. Cycle Detection: For each starting index, we use two pointers:

   • Slow pointer moves one step at a time
   • Fast pointer moves two steps at a time
   • If they meet, a cycle exists

4. Validations: At each step, we check:

   • Direction consistency with the starting direction
   • Not a single-element cycle (element pointing to itself)

5. Optimization: After exploring a path that doesn't lead to a valid cycle, we mark all visited elements as 0. This prevents redundant checking in future iterations.

Time Complexity: O(n) - Each element is visited at most a constant number of times due to the marking strategy.

Space Complexity: O(1) - Only using a few pointer variables, modifying the input array in place for marking.

def circularArrayLoop(nums):
    n = len(nums)
    
    def get_next_index(index):
        """Calculate the next index in the circular array"""
        return (index + nums[index]) % n
    
    def is_same_direction(index1, index2):
        """Check if two indices have the same direction (both positive or both negative)"""
        return (nums[index1] > 0) == (nums[index2] > 0)
    
    # Try starting from each index
    for i in range(n):
        # Skip if already marked as invalid (0)
        if nums[i] == 0:
            continue
        
        # Use slow and fast pointers
        slow = fast = i
        
        # Check if we can form a valid cycle starting from index i
        while True:
            # Move slow pointer one step
            slow = get_next_index(slow)
            
            # Check for single-element cycle or direction change
            if not is_same_direction(i, slow) or slow == get_next_index(slow):
                break
            
            # Move fast pointer two steps
            fast = get_next_index(fast)
            if not is_same_direction(i, fast) or fast == get_next_index(fast):
                break
            
            fast = get_next_index(fast)
            if not is_same_direction(i, fast) or fast == get_next_index(fast):
                break
            
            # If slow and fast meet, we found a cycle
            if slow == fast:
                return True
        
        # Mark all elements in this path as invalid by setting to 0
        # This optimizes future iterations
        slow = i
        direction = nums[i]
        while is_same_direction(slow, i) and nums[slow] != 0:
            next_index = get_next_index(slow)
            nums[slow] = 0
            slow = next_index
    
    return False