Circular Array Loop Solution in Python

Explore More Solutions

Problem Description

Welcome to the world of circular arrays, where every element is a potential pit stop on your journey to nowhere! Imagine you’re on a merry-go-round, and each seat tells you how many steps to take next. If you’re lucky, you might just find yourself back where you started. If not, well, you might just end up in a never-ending loop of confusion.

In this problem, you are given an array of integers, where each integer represents the number of steps to move forward (if positive) or backward (if negative). Your task is to determine if there exists a loop in the array that allows you to keep moving in the same direction without hitting a zero (which is like hitting a brick wall).

Code Solution


class Solution:
    def circularArrayLoop(self, nums: list[int]) -> bool:
        def advance(i: int) -> int:
            return (i + nums[i]) % len(nums)

        if len(nums) < 2:
            return False

        for i, num in enumerate(nums):
            if num == 0:
                continue

            slow = i
            fast = advance(slow)
            while num * nums[fast] > 0 and num * nums[advance(fast)] > 0:
                if slow == fast:
                    if slow == advance(slow):
                        break
                    return True
                slow = advance(slow)
                fast = advance(advance(fast))

            slow = i
            sign = num
            while sign * nums[slow] > 0:
                next = advance(slow)
                nums[slow] = 0
                slow = next

        return False

Approach Explanation

The solution employs a two-pointer technique, often referred to as the “tortoise and hare” approach. Here’s how it works:

Advance Function: This function calculates the next index based on the current index and the value at that index, wrapping around using modulo.
Loop Detection: For each index, we check if we can form a loop by moving both a slow pointer (one step at a time) and a fast pointer (two steps at a time). If they meet, we have a loop.
Marking Visited: If we determine that a loop exists, we mark the visited indices as zero to avoid re-evaluating them.

Time and Space Complexity

Time Complexity: O(n), where n is the number of elements in the array. Each element is processed at most twice.

Space Complexity: O(1), as we are using a constant amount of space for pointers and do not use any additional data structures.

Real-World Example

Imagine you’re at a party, and there’s a game where you have to follow a set of instructions to find the next drink. Each instruction tells you how many steps to take to the left or right. If you keep following the instructions and end up back at the same drink without hitting a wall (or a sober friend), congratulations! You’ve found a circular array loop!