Java Slow/Fast Pointer Solution


  • 20
    J

    Just think it as finding a loop in Linkedlist, except that loops with only 1 element do not count. Use a slow and fast pointer, slow pointer moves 1 step a time while fast pointer moves 2 steps a time. If there is a loop (fast == slow), we return true, else if we meet element with different directions, then the search fail, we set all elements along the way to 0. Because 0 is fail for sure so when later search meet 0 we know the search will fail.

    public class Solution {
        public boolean circularArrayLoop(int[] nums) {
            int n = nums.length;
            for (int i = 0; i < n; i++) {
                if (nums[i] == 0) {
                    continue;
                }
                // slow/fast pointer
                int j = i, k = getIndex(i, nums);
                while (nums[k] * nums[i] > 0 && nums[getIndex(k, nums)] * nums[i] > 0) {
                    if (j == k) {
                        // check for loop with only one element
                        if (j == getIndex(j, nums)) {
                            break;
                        }
                        return true;
                    }
                    j = getIndex(j, nums);
                    k = getIndex(getIndex(k, nums), nums);
                }
                // loop not found, set all element along the way to 0
                j = i;
                int val = nums[i];
                while (nums[j] * val > 0) {
                    int next = getIndex(j, nums);
                    nums[j] = 0;
                    j = next;
                }
            }
            return false;
        }
        
        public int getIndex(int i, int[] nums) {
            int n = nums.length;
            return i + nums[i] >= 0? (i + nums[i]) % n: n + ((i + nums[i]) % n);
        }
    }
    

  • 0
    R

    Nice solution!

    getIndex() could also be:

    public int getIndex(int i, int[] nums) {
            int n = nums.length;
            return (i + nums[i]) % n + (i + nums[i] < 0)*n;
        }
    

  • 10
    G

    I found this solution to be the most cogent, and it's darned fast too.

    In my attempts to understand its implementation, I refactored and added comments:

    public class Solution {
        int len;
        /**
         * Moves the pointer 'i' ahead one iteration.
         */
        private int advance(int[] nums, int i) {
            i += nums[i];
            if (i < 0) i += len;
            else if (i > len - 1) i %= len;
            return i;
        }
        
        public boolean circularArrayLoop(int[] nums) {
            // Handle bad input
            if (nums == null || nums.length < 2) return false;
            
            len = nums.length;
            
            /**
             * Check every possible start location.
             * We may start at a short-loop, for instance, but the Array
             * may still contain a valid loop.
             */
            for (int i = 0; i < len; i++) {
                /**
                 * We set elements to 0 which are on known non-loop paths.
                 * So, if we encounter a 0, we know we're not on a loop path.
                 * So, move to the next start location in the list.
                 */
                if (nums[i] == 0) continue;
                
                // Stagger our starts, so we don't conclude we've found a loop,
                // as we might otherwise when slow == fast.
                int slow = i, fast = advance(nums, slow);
                
                /** 
                 * Whether i is positive or negative defines our direction, so if
                 * the directions differ, so too will the signs.
                 * If the signs differ, we can't be in a 'forward' or a 'backward'
                 * loop, so we exit the traverse.
                 */
                while (nums[i] * nums[fast] > 0 &&
                        nums[i] * nums[advance(nums, fast)] > 0) {
                    if (slow == fast) {
                        if (slow == advance(nums, slow)) break; // 1-element loop
                        return true;
                    }
                    slow = advance(nums, slow);
                    fast = advance(nums, advance(nums, fast));
                }
                
                /**
                 * If we're here, we didn't find a loop, so we know this path
                 * doesn't have a loop, so we re-traverse it until we reverse
                 * direction or encounter a '0' element.
                 * During the re-traverse, we set each element we see to 0.
                 */
                slow = i;
                int sgn = nums[i];
                while (sgn * nums[slow] > 0) {
                    int tmp = advance(nums, slow);
                    nums[slow] = 0;
                    slow = tmp;
                }
            }
            
            // We've tested the whole array and have not found a loop,
            // therefore there isn't one, so return false.
            return false;
        }
    }
    

  • 0
    L
    This post is deleted!

  • 0
    W

    @GrubenM

    There is a risk of using * operation to judge wether two steps are in same direction cause there may be overflow cases.

    private int next(int now, int[] A) {
        return ((now + A[now]) % A.length + A.length) % A.length;
    }
    
    private boolean same(int flag, int b) {
        return b == 0 ? false : (flag ^ (b >>> 31)) == 0;
    }
    
    public boolean circularArrayLoop(int[] nums) {
        if (nums == null || nums.length < 2) return false;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) continue;
            for (int flag = nums[i] >>> 31, slow = i, fast = next(slow, nums); same(flag, nums[slow]) && same(flag, nums[fast]); slow = next(slow, nums), fast = next(next(fast, nums), nums))
                if (slow == fast) 
                    if (slow == next(slow, nums)) break;
                    else return true;
            for (int flag = nums[i] >>> 31, j = i, next; same(flag, nums[j]); next = next(j, nums), nums[j] = 0, j = next);
        }
        return false;
    }

  • 0
    This post is deleted!

  • 0
    J
    This post is deleted!

  • 0
    T

    Nice solution. But seems the time complexity did not meet the requirement
    Seems the time complexity is not o(n), but the square level.


  • 2
    T

    @JeremyLi28
    Nice solution. But seems the time complexity did not meet the requirement
    Seems the time complexity is not o(n), but the square level.


  • 0
    W
    This post is deleted!

  • 0
    T

    Thanks to @JeremyLi28 and @GrubenM Very nice solution and explanation!
    Here is my java solution based on this idea.
    The only difference is that my slow and fast pointers start at the same position together. I think this would be easier to understand.
    Please let me know if there is any problem. Thanks.

    public boolean circularArrayLoop(int[] nums) {
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == 0)   continue;
                int slow = i, fast = i; // slow & fast starts together
                while (nums[i] * nums[slow] > 0 && nums[i] * nums[fast] > 0 && nums[i] * nums[move(nums, fast)] > 0) {
                    slow = move(nums, slow);
                    fast = move(nums, move(nums, fast));
                    if (slow == fast) {
                        if (slow == move(nums, slow))   break; // 1 element loop
                        return true;
                    }
                }
                // mark elements along failed path as 0
                slow = i;
                int sign = nums[i]; // important, since nums[i] will be set to 0 inside the loop
                while (sign * nums[slow] > 0) {
                    int tmp = move(nums, slow);
                    nums[slow] = 0;
                    slow = tmp;
                }
            }
            return false;
        }
        private int move(int[] nums, int i) {
            i += nums[i];
            return i >= nums.length ? i % nums.length : i < 0 ? i + nums.length : i;
        }
    

  • 0
    M
    This post is deleted!

  • 0
    H

    @mmangelmm I dont think putting + n inside is correct. If (i + nums[i]) % n gives you negative integer, then do n + (i + nums[i]) % n. In this case, (i + nums[i] + n) % n == (i + nums[i]) % n. Correct me if I am wrong, I feel that the operator % may be implemented differently in different language.


  • 0
    M

    @hellotest said in Java Slow/Fast Pointer Solution:

    (i + nums[i]) % n

    (i + nums[i]) % n = (i + nums[i]) % n + 0 = (i + nums[i]) % n + n % n = (i + nums[i] + n) % n
    You can replace function getIndex in a AC answer to see if it's correct.
    At least, I use it and get AC.


  • 0
    H

    @mmangelmm Are you using c++, I dont know about java. As for the AC code, well this problem only had 10 test cases and I had already know two tests that did not covered there so some code will be accepted incorrectly.


  • 0
    M

    @hellotest

    Yes. I use c++


  • 0
    H

    @mmangelmm What I mean is that we should get positive index not negative, consider [-2, -3, -9] or [-5, -3, -9], what will you get?


  • 0
    M

    @hellotest

    I think
    (i + nums[i]) % n = (i + nums[i]) % n + 0 = (i + nums[i]) % n + n % n = (i + nums[i] + n) % n
    can prove it's correct.
    I also tried your test cases with both c++ and java. both AC


  • 0
    H

    @mmangelmm said in Java Slow/Fast Pointer Solution:

    @hellotest

    I think
    (i + nums[i]) % n = (i + nums[i]) % n + 0 = (i + nums[i]) % n + n % n = (i + nums[i] + n) % n
    can prove it's correct.
    I also tried your test cases with both c++ and java. both AC

    They are the same. Why you want to add n there? For example, [-2, -3, -9], n = 3, take i = 0, then (0 + nums[0]) % 3 = (-2) % 3 = -2 (at least in c++). Of course, if we add n inside, it will become (0 + nums[0] + 3) % 3 = 1, which is the correct index.

    But what if [-5, -3, -9]? You still get the negative index because adding one n inside is not enough.


  • 0
    M

    @hellotest

    here is my c++ code.
    at least AC by now.

    int getIndex(vector<int>& nums, int i) {
      int n = nums.size();
      return (nums[i] + i + n) % n;
    }
    
    bool circularArrayLoop(vector<int>& nums) {
      int n = nums.size();
      if (n < 2) {
        return false;
      }
      
      for (int i = 0; i < n; i++) {
        if (nums[i] == 0) {
          continue;
        }
        int slow = i;
        int fast = getIndex(nums, i);
        
        while (nums[slow] * nums[fast] > 0 &&
               nums[slow] * nums[getIndex(nums, fast) > 0]) {
          if (fast == slow) {
            if (slow == getIndex(nums, slow)) {
              break;
            }
            return true;
          }
          slow = getIndex(nums, slow);
          fast = getIndex(nums, getIndex(nums, fast));
        }
        
        slow = i;
        int val = nums[slow];
        while(nums[slow] * val > 0) {
          auto next = getIndex(nums, slow);
          nums[slow] = 0;
          slow = next;
        }
      }
      
      return false;
    }
    

Log in to reply
 

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