C++ one pass clean logic solution O(n) time O(1) space


  • 0
    Z
    class Solution {
    public:
        bool circularArrayLoop(vector<int>& nums) {
            if (nums.size() < 2) return false;
            int len = nums.size();
            // One pass loop
            for (int i = 0; i < len; ++i) {
                // skip the '0's. visited path will be zeroed out 
                if (!nums[i]) continue; 
                // slow-fast pointer to get inside the loop
                int p = i, q = next(nums, len, i);
                while (p != q) {
                    p = next(nums, len, p);
                    q = next(nums, len, next(nums, len, q));
                }
                // If the loop has more than one element
                if (p != next(nums, len, p)) {
                    int dir = nums[p] > 0 ? 1 : -1;
                    do {
                        p = next(nums, len, p);
                        // check the direction
                        if ((dir^nums[p]) < 0) {
                            dir = 0;
                            break;
                        }
                    } while (p != q);
                    if (dir) return true;
                }
                // Requested loop not found, zeroed out path from 'i'
                p = i;
                while (nums[p]) {
                    int tmp = p;
                    p = next(nums, len, p);
                    nums[tmp] = 0;
                }
            }
            return false;
        }
    private:
        // helper function to get the next index
        int next(vector<int> &nums, int len, int cur) {
            int k = (nums[cur] + cur) % len;
            return k < 0 ? k + len : k;
        }
    };
    

Log in to reply
 

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