concise java o(n) time o(1) space, kind of dfs.


  • 0
    Z

    try each i as start point to find a loop with the same direction , set visited to 0.

    public class Solution {
        public boolean circularArrayLoop(int[] nums) {
            if(nums == null || nums.length == 0) return false;
            int pre = 0, cur = 0, n = nums.length;
            for(int i=0 ; i<n ; i++){
                if(nums[i] == 0) continue;
                pre = cur = i;
                int sign = nums[cur] > 0 ? 1 : -1;
                boolean isReversed  = false;
                while(nums[cur] != 0){
                    pre = cur; 
                    cur += nums[cur];
                    if(nums[pre] * sign < 0) {
                        isReversed = true;
                        break;
                    }
                    nums[pre] = 0;
                    if(cur >= n) cur -= n;
                    if(cur < 0) cur += n;
                }
                if(pre != cur && !isReversed && i == cur) return true;
            }
            return false;
        }
    }
    
    

Log in to reply
 

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