Circular Array Loop - Leetcode Solution

Circular Array Loop is a problem in LeetCode where we are given an array of integers that represent a circular loop. We have to detect if the circular loop contains a loop of positive or negative integers. A loop is considered positive if it covers all the indices in a forward or clockwise direction and negative if it covers all the indices in a backward or counterclockwise direction. The details of the problem along with its solution are given below.

Problem Statement

We are given an array of integers, nums. We start from any index in the array and follow the loop. The loop can be either forward or backward. We declare that a loop exists if we follow the loop and visit at least one index more than once.

A loop is positive if it follows the array in a forward or clockwise direction and negative if it follows the array in a backward or counterclockwise direction. We can assume that there are no "holes" (i.e., other unvisited indices) in the array and that the loop is always non-empty.

We have to determine if there is a loop in nums and whether the loop is positive or negative.

Example

Input: nums=[2, -1, 1, 2, 2] Output: True

Input: nums=[-1, 2] Output: False

Solution

We can solve this problem by using the concept of two pointers. The idea is to maintain two pointers i and j, where i will be the slow pointer, and j will be the fast pointer. Initially, both pointers will point to the first index of the array.

We will move the slow pointer i one step at a time, and the fast pointer j two steps at a time. Using this approach, we will either find a loop or will reach the end of the array.

While iterating, we will keep track of the directions of the pointers. If the direction of the slow pointer is different from the direction of the fast pointer, there is no loop in the array.

If both pointers are pointing in the same direction, we will check if they ever meet (i.e., they point to the same index of the array). If they do, that indicates the presence of a loop. To determine the direction of the loop, we can check the signs of the integers in the loop.

If the sum of the integers in the loop is positive, the loop is positive. If it is negative, the loop is negative.

Here is the complete solution in Python:

def circularArrayLoop(nums): n = len(nums) for i in range(n): # Slow and fast pointer slow, fast = i, next_index(i, nums)

    # Same direction pointers
    while nums[slow] * nums[fast] > 0 and nums[slow] * nums[next_index(fast, nums)] > 0:
        if slow == fast:
            if slow == next_index(slow, nums):
                break  # Single element loop
            return True  # Loop found
        
        slow = next_index(slow, nums)
        fast = next_index(next_index(fast, nums), nums)
    
    # Mark elements in current cycle as 0 to flag as visited
    j = i
    while nums[j] * nums[next_index(j, nums)] > 0:
        nums[j], j = 0, next_index(j, nums)

return False

def next_index(i, nums): return (i + nums[i]) % len(nums)

The time complexity of this solution is O(N^2), where N is the length of the array. However, the actual time complexity is much less than that as most of the elements will be flagged as visited after the first iteration. The space complexity of the solution is O(1) as we are not using any additional space.

Conclusion

In the Circular Array Loop problem, we have to find a loop in a circular array of integers and determine its positivity or negativity. We can solve this problem by using two pointers and checking if they point to the same index after moving them one at a time or two at a time. We can also determine the direction of the loop by checking the signs of the integers in the loop.

1