457. Circular Array Loop

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 class Solution { public: bool circularArrayLoop(vector& nums) { const int n = nums.size(); if (n < 2) return false; auto advance = [&](int i) { const int val = (i + nums[i]) % n; return i + nums[i] >= 0 ? val : n + val; }; for (int i = 0; i < n; ++i) { if (nums[i] == 0) continue; int slow = i; int fast = advance(slow); while (nums[i] * nums[fast] > 0 && nums[i] * nums[advance(fast)] > 0) { if (slow == fast) { if (slow == advance(slow)) break; return true; } slow = advance(slow); fast = advance(advance(fast)); } slow = i; const int sign = nums[i]; while (sign * nums[slow] > 0) { const int next = advance(slow); nums[slow] = 0; slow = next; } } return false; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 class Solution { public boolean circularArrayLoop(int[] nums) { if (nums.length < 2) return false; for (int i = 0; i < nums.length; ++i) { if (nums[i] == 0) continue; int slow = i; int fast = advance(nums, slow); while (nums[i] * nums[fast] > 0 && nums[i] * nums[advance(nums, fast)] > 0) { if (slow == fast) { if (slow == advance(nums, slow)) break; return true; } slow = advance(nums, slow); fast = advance(nums, advance(nums, fast)); } slow = i; final int sign = nums[i]; while (sign * nums[slow] > 0) { final int next = advance(nums, slow); nums[slow] = 0; slow = next; } } return false; } private int advance(int[] nums, int i) { final int n = nums.length; final int val = (i + nums[i]) % n; return i + nums[i] >= 0 ? val : n + val; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution: def circularArrayLoop(self, nums: List[int]) -> bool: def advance(i: int) -> int: return (i + nums[i]) % len(nums) if len(nums) < 2: return False for i, num in enumerate(nums): if num == 0: continue slow = i fast = advance(slow) while num * nums[fast] > 0 and num * nums[advance(fast)] > 0: if slow == fast: if slow == advance(slow): break return True slow = advance(slow) fast = advance(advance(fast)) slow = i sign = num while sign * nums[slow] > 0: next = advance(slow) nums[slow] = 0 slow = next return False