Java One pass solution - O(n) time, O(1) space


  • 0
    J
    public class Solution {
        public boolean circularArrayLoop(int[] nums) {
        
            int count = 0;
            
            for(int i = 0; i < nums.length; i++) {
                int nextIndex = nextIndex(i, nums[i], nums);
                
                //Check current and next and make sure they aren't equal to the length of the array
                if(Math.abs(nums[i]) == nums.length) nums[i] = 0;
                if(Math.abs(nums[nextIndex]) == nums.length) nums[i] = 0;
                
                //Check current index and next index and varify they have the same sign, and not equal to zero
                if(nums[i] > 0 && nums[nextIndex] <= 0) nums[i] = 0;
                if(nums[i] < 0 && nums[nextIndex] >= 0) nums[i] = 0;
                
                //if either of the two conditions above are true, increase the count of zeros in the list
                if(nums[i] == 0) count++;
            }
            
            //if the array isn't all filled with zeros, there is a loop
            return (count < nums.length-1) ? true : false;
        }
        
        //calculates the next index
        public int nextIndex(int currentIndex, int currentValue, int[] array) {
            int combined = currentIndex + currentValue;
            int length = array.length-1;
            
            if(combined < 0) return length - Math.abs(length % combined);
            if(combined > length) return length % combined;
            return combined;
        }
    }
    

Log in to reply
 

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