Problem statement

https://leetcode.com/problems/circular-array-loop/

Solution

First of all, if we have numbers >= n, make them in range (-n+1, n-1). Now, let us iterate over list and start to build loop, and save direction of movement. I denote visited elements by n + i. So, if we find new element with this value, we return True. If we found 0 or number in range (n, n + i), we break our loop: it means we found already visited elements. If direction is wrong, we also break.

Complexity

Time complexity is O(n), additional space is O(1), because we directly change our nums.

Code

class Solution:
    def circularArrayLoop(self, nums):
        def sign(q): return q/abs(q)
        
        n = len(nums)
        for i in range(n):
            nums[i] = int(sign(nums[i]) * (abs(nums[i]) % n))

        for i in range(n):
            if nums[i] == 0 or nums[i] >= n: continue
            dr, start = sign(nums[i]), i
            while True:
                tmp = nums[start]
                nums[start] = n + i
                start = (start + tmp) % n
                if nums[start] == n + i: return True
                if nums[start] == 0 or nums[start] in range(n, n + i): break
                if sign(nums[start]) != dr: break

There is similar solution, using the idea of Problem 0141 Linked List Cycle: we use two iterators: fast and slow. If there is a loop (fast == slow), we return true, else if we meet element with different directions, then the search fail, we set all elements along the way to 0. Because 0 is fail for sure so when later search meet 0 we know the search will fail.