Java solution by marking paths


  • 0
    W
    public class Solution {
        public boolean circularArrayLoop(int[] nums) {
            if(nums.length < 2) return false;
            //set all values in the range (-nums.length, nums.length), and this doesn't change sign
            for(int i = 0; i < nums.length; i++) nums[i] %= nums.length;
            for(int i = 0; i < nums.length; i++){
                if(nums[i] == 0 || nums[i] >= nums.length) continue; //if already visited continue
                int temp = i, sign = (int)Math.signum(nums[i]);
                while(true){
                    if(nums[temp] >= nums.length) { //if it is visited, check if it is visited by previous paths or current path
                        if(nums[temp] == i + nums.length) return true;
                        else break;
                    }
                    if((int)Math.signum(nums[temp]) != sign) break; //encount a different direction
                    int next = (nums[temp] + nums.length + temp) % nums.length; //next position
                    nums[temp] = i + nums.length; //mark this path by a number unique to this path
                    temp = next;
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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