A real O(N) time/ O(1) space solution using Count instead of the two pointers method


  • 0
    B

    The code counts how many elements in any given path/loop. if it exceeds the count of the array itself then there must be a loop.

    If not, we set the elements in the path to zeros not to process them again.

    Each element is generally visited max 3 times (when there are no loops). If there is a loop, an extra N elements are visited before the code exits. So in total the code is O(N)

    class Solution {
    public:
        bool circularArrayLoop(vector<int>& nums) {
            int N=nums.size();
            for(int i=0;i<N;i++)
            {
                if((i+nums[i])%N != i)
                {
                    bool direction =(nums[i]>0);
                    int j=i, count= 0;
                    while(direction == (nums[j]>0))
                    {
                        int tmp=(j+nums[j]+N)%N;
                        if(count>=N)
                            return true;
                        if(tmp == j )
                            break;
                        j=tmp;
                        count++;
                    }
                    j=i;
                    while(true)
                    {
                        int tmp=(j+nums[j]+N)%N;
                        if(tmp == j )
                            break;
                        nums[j]=0;
                        j=tmp;
                    }
                }
            }
            
            return false;
        }
    };
    

Log in to reply
 

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