LeetCode 457: Circular Array Loop Solution in Python – A Step-by-Step Guide

What Is LeetCode 457: Circular Array Loop?

In LeetCode 457: Circular Array Loop, you’re given an integer array nums representing a circular array, where each element indicates the number of steps to move forward (positive) or backward (negative), wrapping around modulo n (array length). Your task is to determine if there’s a loop—a sequence of indices that cycles back to a starting point—where all moves are in the same direction (all positive or all negative) and the loop length is greater than 1. For example, in [2, -1, 1, 2, 2], a loop exists: 0 → 2 → 3 → 0 (all positive). It’s like finding a consistent trail that loops around the circle.

Problem Statement

• Input: nums (List[int])—circular array of integers.
• Output: bool—True if a valid loop exists, False otherwise.
• Rules:
• Move i to (i + nums[i]) % n.
• Loop must have all positive or all negative moves.
• Loop length > 1 (no self-loops).

Constraints

• 1 <= nums.length <= 5000.
• -10^5 <= nums[i] <= 10^5.
• nums[i] != 0 (no zero steps).

Examples to Get Us Started

• Input: nums = [2,-1,1,2,2]
• Output: True (Loop: 0 → 2 → 3 → 0, all positive).
• Input: nums = [3,1,2]
• Output: True (Loop: 0 → 3 → 0, all positive, adjusted modulo).
• Input: nums = [1,-1,5,1,4]
• Output: False (Mixed directions or no loop).

Understanding the Problem: Finding the Loop

To solve LeetCode 457: Circular Array Loop in Python, we need to detect a cycle in a circular array where all steps are unidirectional (all positive or all negative) and the cycle length exceeds 1. A naive approach—checking every possible path—could be O(n²) or worse. Instead, we can use cycle detection techniques optimized for direction consistency. We’ll explore:

• Best Solution (Cycle Detection with Visited Tracking): O(n) time, O(n) space—fast and efficient.
• Alternative Solution (Brute Force with Path Tracking): O(n²) time, O(n) space—simple but slow.

Let’s dive into the cycle detection solution—it’s the explorer’s compass we need.

Best Solution: Cycle Detection with Visited Tracking

Why This Is the Best Solution

The cycle detection with visited tracking is the top pick because it’s O(n) time and O(n) space, efficiently finding a valid loop in one pass per starting point using a visited set and direction checks. It mimics Floyd’s cycle-finding algorithm but adapts for circular arrays and direction consistency, marking visited indices to avoid redundant paths. It’s like following a trail with a map, marking your steps, and spotting when you loop back—smart and precise!

How It Works

Here’s the strategy:

• Step 1: For each unvisited index i as a start:
• Use a visited set to track seen indices globally.
• Use a path set to track the current traversal.
• Step 2: Follow steps:
• Compute next index: (i + nums[i]) % n.
• Check direction consistency with nums[i].
• If next index in path set, check loop length and direction.
• Step 3: Return True if valid loop found, False otherwise.
• Why It Works:
• Visited set prevents revisiting dead ends.
• Path set detects cycles, direction check ensures validity.

Step-by-Step Example

Example: nums = [2,-1,1,2,2]

• n = 5:
• Start i=0:
• visited = {}, path = {}.
• i=0: nums[0]=2 > 0, next = (0+2)%5 = 2, path = {0}.
• i=2: nums[2]=1 > 0, next = (2+1)%5 = 3, path = {0,2}.
• i=3: nums[3]=2 > 0, next = (3+2)%5 = 0, path = {0,2,3}.
• i=0: in path, loop = [0,2,3,0], length = 3 > 1, all positive, True.
• Result: True.

Example: nums = [1,-1,5,1,4]

• Start i=0:
• i=0: 1 > 0, next = 1, path = {0}.
• i=1: -1 < 0, mixed direction, reset.
• No valid loop: False.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def circularArrayLoop(self, nums: List[int]) -> bool:
        n = len(nums)

        def get_next(i):
            # Compute next index with modulo
            return (i + nums[i]) % n if (i + nums[i]) >= 0 else ((i + nums[i]) % n + n) % n

        # Step 1: Try each starting point
        visited = set()
        for i in range(n):
            if i in visited:
                continue

            # Step 2: Track current path
            path = set()
            curr = i
            direction = nums[i] > 0  # True for forward, False for backward

            while curr not in path:
                path.add(curr)
                visited.add(curr)
                next_idx = get_next(curr)

                # Check direction consistency
                if (nums[next_idx] > 0) != direction:
                    break

                # Check if next is visited but not in current path
                if next_idx in visited and next_idx not in path:
                    break

                # If loop detected
                if next_idx in path:
                    if len(path) > 1 or (next_idx != curr):  # Ensure length > 1
                        return True
                    break

                curr = next_idx

        return False

• Line 5-7: Helper to compute next index with proper modulo.
• Line 10-11: Visited set, loop over starts.
• Line 14-34: For each start:
• Path tracks current cycle, direction set by first move.
• Compute next_idx, check direction, detect cycle.
• If cycle found, verify length > 1.
• Line 36: Return False if no valid loop.
• Time Complexity: O(n)—each index visited once.
• Space Complexity: O(n)—visited and path sets.

It’s like a loop-finding compass!

Alternative Solution: Brute Force with Path Tracking

Why an Alternative Approach?

The brute force method tracks paths from each start—O(n²) time, O(n) space—checking for cycles explicitly. It’s slower but intuitive, like walking every trail until you loop back, noting each step. Good for small n or clarity!

How It Works

• Step 1: For each start i, follow steps, track path.
• Step 2: Check direction and cycle, verify length > 1.
• Step 3: Return True if valid, False otherwise.

Step-by-Step Example

Example: nums = [2,-1,1,2,2]

• Start i=0:
• Path: 0 → 2 → 3 → 0, all positive, length = 3, True.
• Result: True.

Code for Brute Force

Copy codeclass Solution:
    def circularArrayLoop(self, nums: List[int]) -> bool:
        n = len(nums)

        def get_next(i):
            return (i + nums[i]) % n if (i + nums[i]) >= 0 else ((i + nums[i]) % n + n) % n

        for i in range(n):
            path = []
            curr = i
            direction = nums[i] > 0

            while curr not in path:
                path.append(curr)
                next_idx = get_next(curr)
                if (nums[next_idx] > 0) != direction:
                    break
                if next_idx in path:
                    if len(path) - path.index(next_idx) > 1:
                        return True
                    break
                curr = next_idx

        return False

• Line 5-7: Next index helper.
• Line 10-20: For each start, track path, check direction and cycle length.
• Time Complexity: O(n²)—path length up to n per start.
• Space Complexity: O(n)—path list.

It’s a slow trail tracker!

Comparing the Two Solutions

• Cycle Detection (Best):
• Pros: O(n), fast, scalable.
• Cons: O(n) space.
• Brute Force (Alternative):
• Pros: O(n²), simple.
• Cons: Slower.

Cycle detection wins for speed.

Edge Cases and More Examples

• Input: [1] → False.
• Input: [2,2] → True.
• Input: [1,-1] → False.

Cycle detection handles all well.

Complexity Recap

• Cycle Detection: Time O(n), Space O(n).
• Brute Force: Time O(n²), Space O(n).

Cycle detection’s the champ.

Key Takeaways

• Cycle Detection: Track smartly.
• Brute Force: Walk every path.
• Python Tip: Sets find cycles—see [Python Basics](/python/basics).

Final Thoughts: Find That Loop

LeetCode 457: Circular Array Loop in Python is a cycle-chasing expedition. Cycle detection is your fast compass, while brute force is a steady hike. Want more cycle fun? Try LeetCode 141: Linked List Cycle or LeetCode 287: Find the Duplicate Number. Ready to hop some loops? Head to Solve LeetCode 457 on LeetCode and explore today—your coding skills are looping strong!