Tortoise and Hare Solution Accounting for f(i) == f(f(i))


  • 0
    W

    The tortoise and hare solution doesn't account for when the path has a dead end (aka there's a node that has a self-cycle).

    For example, the array [0, 1, 2, 3, 4, 4] should return 4, but instead returns 0 because the slow and fast pointers will get stuck at the first index.

    From a graph perspective, the issue is that despite being unique integers, the list of numbers is not necessarily a single linked list, but instead multiple linked lists with many that are self-cycles. How do we detect the existence of a cycle when it could be in any of these sub lists?

    Well, first note that each of these linked lists is either a part of the main linked list or a single node self-cycle. Why? Because each integer should only appear once. If there is only one integer that has duplicates, then that integer is the only one with an in-degree of more than one, which implies that all other nodes have at most one incoming edge. This implies that we will only get stuck if we start on a node that points to itself. Now, having duplicate integers also implies that at least one of these duplicates will be at an index that is not equal to the integer. Therefore, we simply iterate through each starting position until we find a cycle that is not a self-cycle.

    class Solution(object):
    def detect_cycle(self, nums, i):
        slow = i
        fast = i
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        return slow
    
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(len(nums)):
            x = self.detect_cycle(nums, i)
            if i == x:
                continue
            y = i
            while True:
                x, y = nums[x], nums[y]
                if x == y:
                    return x
        return False        
    

Log in to reply
 

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