457. Circular Array Loop

Tag: Fast-Slow pointers, No AC first time

Description

457-1

457-2

Solution

To determine a cycle, Fast-Slow pointers is a good way for solving it in linear time and constant space.

Some tricky points

  • Determine all positive or all negative
  • Determine length k>1

We can do a product of two nums to judge whether they are same positive or not, and do slow == Next(slow) to judge loop’s length == 1

Code

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
class Solution {
public:
    bool circularArrayLoop(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] == 0)
                continue;
            int fast = getNext(n, i, nums[i]), slow = i;
            bool pos = nums[i] > 0, res = true;
            while(nums[slow] * nums[fast] > 0 && nums[slow] * nums[getNext(n, fast, nums[fast])] > 0){
                if(slow == fast){
                    if(slow != getNext(n, slow, nums[slow]))
                        return true;
                    break;
                }
                slow = getNext(n,slow, nums[slow]);
                fast = getNext(n, fast, nums[fast]);
                fast = getNext(n, fast, nums[fast]);
            }
            int tmp = i;
            while(nums[tmp] * nums[getNext(n, tmp, nums[tmp])] > 0){
                int step = nums[tmp];
                nums[tmp] = 0;
                tmp = getNext(n, tmp, step);
            }
        }
        return false;
    }

    int getNext(int size, int i, int move){
        while(i + move < 0)
            i += size;
        while(i + move >= size)
            i -= size;
        return i + move;
    }
};

457-3