Java solution, easy to follow


  • 0
    J

    This algo divides responsibilities in a way that I believe makes it easier to follow. It is also non-destructive to the input data. The "next" function detects cases that we can abandon, while the main code focuses on finding a loop.

    The main loop is a simple slow/fast pointer search to find loops. The next function uses Integer object, so that it can pass or return null as an end case. And null returns end the search.

    Null can be returned from next in the following cases:

    1. When input pos value is null (fast pointer that double-calls would cause this)
    2. When direction changes. Direction is captured on the first step in the "dir" value, and then passed to all follow-on calls to next. So the first time the product of dir and num[pos] is less than zero, we know we've changed direction, so return null.
    3. When a "self pointer" is found, meaning the next value from pos is the same index as pos.
    public class Solution {
        public boolean circularArrayLoop(int[] nums) {
            boolean found = false;
    
            for ( int n=0; n<nums.length; n++ ) {
                Integer ps = n;
                Integer pf = next(nums, 0, n);
                int dir = nums[n];
    
                while ( ps != null && pf != null && ps != pf ) {
                    ps = next(nums, dir, ps);
                    pf = next(nums, dir, next(nums, dir, pf));
                }
    
                if ( ps != null && ps == pf ) {
                    found = true;
                    break;
                }
            }
    
            return found;
        }
    
        Integer next(int[] nums, int dir, Integer pos) {
            if ( pos == null ) return null; // null, return null
            if ( dir * nums[pos] < 0 ) return null; // change in direction, return null
    
            Integer next = (pos + nums[pos]) % nums.length;
            if ( next < 0 ) next += nums.length; // wrap negative
    
            if ( next == pos ) next = null; // self-pointer, return null
            return next;
        }
    }
    

Log in to reply
 

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