Concise C++ code, 0ms O(n) time, O(1) space, 15 lines with comments


  • 1
    J

    For each position i that has non-zero value:

    1. Determine the direction
    2. Check for loop (see if there is a valid path with length more than array size)
    3. If no loop, start from i again and change value along path to 0.
        bool circularArrayLoop(vector<int>& nums) {
            //next index
            #define n(i) ((nums[i]+i)%nums.size())
            int count, check, mark, mode;
            for( int i = 0; i < nums.size(); i ++ ){
                if( nums[i] != 0 ){
                    //check the direction
                    mode = nums[i] > 0? 1:-1;
                    count = 0; check = i; mark = i;
                    //check for loow
                    while( count++ <= nums.size() + 1&& mode*nums[n(check)] > 0 && n(check) != check ) 
                        check = n(check);
                    //a path longer than array size means there is a loop
                    if( count > nums.size() + 1 ) return true;
                    //mark all nodes in path as 0
                    while( nums[mark] > 0 ){ mark = n(mark); nums[mark] = 0; }
                }
            }
            return false;
        }
    

  • 0
    Z
    This post is deleted!

  • 0
    J

    @zhangyiwei I think each of the n/2 pairs doesn't take O(n) to check since the while loop also check for the direction.


  • 0
    Z
    This post is deleted!

  • 0
    J

    @zhangyiwei I think in this case, the function would have returned after the first valid loop is detected.


  • 0
    Z

    @jade86 yes, you are so right...Just forget my post...sorry to disturb >_<


  • 0
    J

    @zhangyiwei No problem, I stumbled on these questions all the time ^^


Log in to reply
 

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