Skip to content

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<int>& 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