Java solution with memoization


  • 0
    M

    Start with an element and jump to the next and mark all the elements on the way as visited. Since there are two directions each element should have different flags for every direction. Once all elements are visited in that direction exit the loop and compare the last index with the starting index. In subsequent passes visited elements won't be visited again, therefore worst case complexity is O(n).

        public boolean circularArrayLoop(int[] nums) {
            boolean [] forwardVisited = new boolean[nums.length];
            boolean [] backwardsVisited = new boolean[nums.length];
            
            for (int j = 0; j < nums.length; j++) {
                int elementCount = 0;
                int i = j;
                boolean forward = (nums[i] > 0);
                
                if (forward) {
                    while(!forwardVisited[i]) {
                       elementCount++;
                       forwardVisited[i] = true;
                       if (nums[i] < 0) {
                          break;
                       }
                       i += nums[i];
                       if (i >= nums.length) {
                           i -= nums.length;
                       }
                    }
                } else {
                    while(!backwardsVisited[i]) {
                       elementCount++;
                       backwardsVisited[i] = true;
                       if (nums[i] > 0) {
                          break;
                       }
                       i += nums[i];
                       if (i < 0) {
                           i += nums.length;
                       }
                    }
                }
                if (j == i && elementCount > 1) {
                    return true;
                }
            }
            return false;
        }
    

Log in to reply
 

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