Concise C++ solution with explanation


  • 0
    H

    This problem is similar to check if a linked list has circle or not. Similarly, we can use i, k to simulate the fast and slow pointers respectively. Because each element in the array could be the 'head' of a 'linked list', we need to do the check to every elements, then the time complexity will be O(n). Actually it is not necessary to do the check for every element because if an element is traversed in previous check and proved no loop, we can just skip it. According to the description "The given array is guaranteed to contain no element "0".", we can set all traversed elements to 0 as marker.

    To make the code more concise, it will return -1 if for self-loop or reverse-direction.

    class Solution {
    public:
        bool circularArrayLoop(vector<int>& nums) {
            for (int i = 0; i < nums.size(); i++) {
                if (nums[i] == 0) continue; // Already checked, skip
                int j = i;  // slow pointer
                int k = next(nums, j); // fast pointer
                while (k >= 0) {
                    j = next(nums, j);
                    k = next(nums, k);
                    if (k >= 0) k = next(nums, k);
                    if (k == j) return true; // fast meet slow, there is a loop
                }
                j = i;
                while (j >= 0) {
                    nums[j] = 0; // set all traversed elements to 0
                    j = next(nums, j);
                }
            }
            return false;
        }
        
        int next(vector<int>& nums, int i) {
            int n = nums.size();
            int step = abs(nums[i]) % n;
            if (nums[i] < 0) step = n - step;
            int j = (i + step) % n;
            return (j != i && nums[i] * nums[j] > 0) ? j : -1;
        }
    };
    

Log in to reply
 

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