457 Circular Array Loop

457. Circular Array Loop

1. Question

You are given an array of positive and negative integers. If a number n at an index is positive, then move forward n steps. Conversely, if it's negative (-n), move backward n steps. Assume the first element of the array is forward next to the last element, and the last element is backward next to the first element. Determine if there is a loop in this array. A loop starts and ends at a particular index with more than 1 element along the loop. The loop must be "forward" or "backward'.

Example 1:Given the array [2, -1, 1, 2, 2], there is a loop, from index 0 -> 2 -> 3 -> 0.

Example 2:Given the array [-1, 2], there is no loop.

Note:The given array is guaranteed to contain no element "0".

Can you do it inO(n)time complexity andO(1)space complexity?

2. Implementation

(1) Two Pointers

思路: 题意是是说在数组中找到一个loop，这个loop里的数要么全是正数(forward), 要么全是负数(backward), 同时loop的size必须大于1。对于找loop的题目，我们很容易想到用快慢指针，由于数组可以当做是circular的，所以如果我们从数组index i走下一步 (i + nums[i])，我们要判断(i + nums[i])的正负，如果是正数则要mod n ((即 (i + nums[i]) % n），如果是负数，说明我们是往后走，则要加上n, 即 ((i + nums[i] + n) % n)

class Solution {
    public boolean circularArrayLoop(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                continue;
            }

            int slow = i;
            int fast = getNext(i, nums);

            while (nums[fast] * nums[i] > 0 && nums[getNext(fast, nums)] * nums[i] > 0) {
                if (slow == fast) {
                    if (slow == getNext(slow, nums)) {
                        break;
                    }
                    return true;
                }
                slow = getNext(slow, nums);
                fast = getNext(getNext(fast, nums), nums);
            }

            slow = i;

            while (nums[slow] * nums[i] > 0) {
                int next = getNext(slow, nums);
                nums[slow] = 0;
                slow = next;
            }
        }
        return false;
    }

    public int getNext(int i, int[] nums) {
        int n = nums.length;
        return (i + nums[i]) >= 0 ? (i + nums[i]) % n : (i + nums[i] + n) % n; 
    }
}

3. Time & Space Complexity

Two Pointers: 时间复杂度O(n), 空间复杂度O(1)