unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 457: Circular Array Loop

link

Since the array is circular, there is always a cycle. A loop is:

  1. A cycle with at least two indices.
  2. Within the cycle, the traversal direction does not change.

For example, below, if we start from index 0, the direction changes at the hop \textcircled{3} \rightarrow \textcircled{1}. But within the cycle: \textcircled{1} \rightarrow \textcircled{2} \rightarrow \textcircled{4} \rightarrow \textcircled{1}, the direction does not change. So, we declare it has a loop.

Starting from each index we can check the above two conditions using slow and fast pointers.

Time: \mathcal{O}(n^2), space: \mathcal{O}(1).

class Solution:
    def has_loop_from(self, begin, nums):
        def next(i):
            return (i+nums[i]) % len(nums)
        
        slow, fast = begin, next(begin)
        while slow != fast:
            slow = next(slow)
            fast = next(next(fast))
        
        head = slow
        dir = nums[head]
        while True:
            slow = next(slow)
            # Direction changed
            if nums[slow] * dir < 0:
                return False
            if slow == head:
                break
        
        # Cycle length > 1
        return slow != next(slow)

    def circularArrayLoop(self, nums: List[int]) -> bool:
        for i in range(len(nums)):
            if self.has_loop_from(i, nums):
                return True

        return False

If a cycle is not a loop, starting from different indices of that cycle is not going to find anything new. We can skip this wasted work by zeroing out (making self-loop) the indices of a not-loop cycle.

Time: \mathcal{O}(n), space: \mathcal{O}(1).

class Solution:
    def zero_out_cycle(self, begin, nums):
        def next(i):
            return (i+nums[i]) % len(nums)

        while nums[begin] != 0:
            begin_next = next(begin)
            nums[begin] = 0
            begin = begin_next

    def has_loop_from(self, begin, nums):
        def next(i):
            return (i+nums[i]) % len(nums)
        
        slow, fast = begin, next(begin)
        while slow != fast:
            slow = next(slow)
            fast = next(next(fast))
        
        head = slow
        dir = nums[head]
        while True:
            slow = next(slow)
            # Direction changed
            if nums[slow] * dir < 0:
                return False
            if slow == head:
                break
        
        # Cycle length > 1
        return slow != next(slow)

    def circularArrayLoop(self, nums: List[int]) -> bool:
        for i in range(len(nums)):
            if self.has_loop_from(i, nums):
                return True
            else:
                self.zero_out_cycle(i, nums)

        return False

tanvirdotzaman

,

Leave a comment