Possible O(n) time, and O(1) space solution using DFS.


  • 0
    D

    I feel that this can be solved by handling the forward and backward cycles separately. i.e. first process all positive numbers, and then process all negative numbers.

    The first step is to reduce each number such that abs(number) < nums.size() since if it's greater, we can always reduce it to be < nums.size().

    When processing a forward cycle, we maintain a generation number for each cycle. When we start along a cycle, we set the generation number of the cycle. If we hit a number which is from the same generation, we declare a cycle. If we hit a negative number or a cycle with a smaller generation number, we move ahead (since we've hit a dead end or we've hit a previous cycle). It's clear that hitting a negative number won't get us anywhere (because of a change in direction). When we hit a previous generation cycle, that too won't get us anywhere since if we were to get somewhere, we would have found the cycle when we started that previous cycle.

    The same logic applies for a backward cycle.

    class Solution {
    public:
        bool circularArrayLoop(vector<int>& nums) {
            const int isz = nums.size();
            for (int i = 0; i < nums.size(); ++i) {
                if (nums[i] >= isz) {
                    nums[i] %= nums.size();
                } else if (abs(nums[i]) >= isz) {
                    nums[i] = -((-nums[i]) % isz);
                }
            }
            int gen = nums.size() + 1; // generation number of the cycle.
            for (int i = 0; i < nums.size(); ++i) {
                if (nums[i] <= 0) continue;
                int j = i;
                while (nums[j] > 0 && nums[j] < nums.size()) {
                    const int k = j;
                    j += nums[j];
                    j %= nums.size();
                    nums[k] = gen;
                }
                if (nums[j] == gen) {
                    return true;
                }
                ++gen;
            }
            gen = -(isz + 1);
            for (int i = 0; i < nums.size(); ++i) {
                if (nums[i] >= 0) continue;
                int j = i;
                while (nums[j] < 0 && nums[j] > -isz) {
                    const int k = j;
                    j += nums[j];
                    // j %= isz; (but it doesn't work the way I expected)
                    if (j < 0) { j = isz + j; }
                    nums[k] = gen;
                }
                if (nums[j] == gen) {
                    return true;
                }
                --gen;
            }
            return false;
        }
    };
    

    This solution fails for the test case [2,-2,2,-2,-1] and returns true instead of the expected false, but I feel that the example solution may be incorrect.


Log in to reply
 

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