O(n) solution not using slow/fast pointer


  • 0
    N

    The observation I have is that loops have sums of jump that are multiples of array length. So, keep jumping until either of:

    • Hit something going the other direction
    • Hit something I've seen before in a previous iteration
    • Sum modulo length is zero, in which case return true.

    Use zeros to mark each item that we have seen.

    Here is my accepted code:

    public class CircularArrayLoop {
        public boolean circularArrayLoop(int[] nums) {
            int length = nums.length;
    
            for (int i = 0; i < length; i++) {
                if (nums[i] == 0) {
                    continue;
                } else {
                    long sum = nums[i];
                    int jump = nums[i];
                    boolean isForward = nums[i] > 0;
                    nums[i] = 0;
                    int cur = i;
                    while (true) {
                        int next = Math.floorMod(cur + jump, length);
                        int nextValue = nums[next];
                        if (nextValue == 0 || ((nextValue > 0) ^ isForward)) {
                            break;
                        }
                        sum += nextValue;
                        if (sum % length == 0) {
                            return true;
                        }
                        nums[cur] = 0;
                        jump = nextValue;
                        cur = next;
                    }
                }
            }
            return false;
        }
    }
    

  • 0
    L

    I don't think it works for [1,1,2]. There is a loop 1->2->1 while your code returns false. That's because by checking sum % length == 0 you are assuming the loop starts at index i.


Log in to reply
 

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