Solution by lzyerste

  • 0

    Approach: Cycle Detection

    The key point in this problem is to transform to a cycle detection problem. We can adopt topological sort to detect a cycle in a directed graph.

    We take array indices as vertices in a graph and the corresponding value in the array is used to find its neighbor (of course, there's only one neighbor).

    In addition, pay attention to the problem description that there should be more than 1 element along the loop and the loop direction should be either "forward" or "backward". We treat positive values in the array as "forward" and negative values as "backward".

    So, when a cycle is detected in the depth-first-search, we need to check if it's a self-loop and keep going back to its parent to ensure they have same direction (forward or backward).

    Same direction means both positive or negative. => same sign

    class Solution(object):
        def circularArrayLoop(self, nums):
            :type nums: List[int]
            :rtype: bool
            n = len(nums)
            def dfs(nums, s, P, vis):
                # P is used to keep parent link
                # vis: visited nodes
                v = (s + nums[s]) % n  # the neighbor
                if v in P:  # a cycle is detected
                    if v == s: return False  # more than 1 ele along the loop
                    # the while is to check forward or backword
                    while s != v and nums[s] * nums[v] > 0:
                        s = P[s]  # its parent
                    return s == v
                if v in vis: return False
                P[v] = s
                return dfs(nums, v, P, vis)
            vis = set()
            for i in range(n):
                if i in vis: continue
                if dfs(nums, i, {i: None}, vis):
                    return True
            return False

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.