-1
$\begingroup$

Having a hard time understanding the runtime complexity of the following algorithm:

public class Solution {
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        if(n < 2){
            return false;
        }
        for(int i = 0; i < n; i++){
            if(nums[i] == 0){
                continue;
            }
            int slow = i, fast = advance(nums, i);
            while(nums[slow] * nums[fast] > 0 && nums[advance(nums, fast)] * nums[slow] > 0){
                if(slow == fast){
                    //one element loop does not count
                    if(slow == advance(nums, slow)){
                        break;
                    }
                    return true;
                 }
                 slow = advance(nums, slow);
                 fast = advance(nums, (advance(nums,fast)));
            }
            
            //loop not found, set all the elements along the way to 0
            slow = i;
            int val = nums[i];
            while(nums[slow] * val > 0){
                int next = advance(nums, slow);
                nums[slow] = 0;
                slow = next;
            }
            
        }
        return false;
            
    }
    public int advance(int[] nums, int i){
        int n = nums.length;
        return i + nums[i]  >= 0 ? (i+nums[i]) % n : n + ((i + nums[i]) %n);
    }
}

Been told that the complexity should be $O(n)$ because each node is visited at most four times by slow, by fast, be marking zero, be zero checking. Cannot quite agree, because even it is marked zero, the rest of the nodes still have to check whether it is zero or not. So you have to check it at least $n-1$ times.

$\endgroup$
  • 3
    $\begingroup$ This is not an algorithm, it is code. $\endgroup$ – gnasher729 Jul 2 at 16:36
  • $\begingroup$ Coding questions are off-topic here. Not all of us know any particular language. We ask people to replace code with concise pseudocode. Also, please show us your analysis. See cs.stackexchange.com/q/23593/755. $\endgroup$ – D.W. Jul 2 at 17:07
  • $\begingroup$ This looks like Floyd's Tortoise and Hare Algorithm. I suggest you to search it in Google to find out more about it and its complexity! $\endgroup$ – nir shahar Jul 2 at 17:16
  • $\begingroup$ Maybe you could add a counter variable and print statements and try it for smaller values of n to see if O(n) looks reasonable. $\endgroup$ – Bobby Durrett Jul 2 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.