Lintcode 1229. Circular Array Loop (Medium) (Python)_code1229

1229. Circular Array Loop

Description:

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
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.

Challenge
Can you do it in O(n) time complexity and O(1) space complexity?

Notice
The given array is guaranteed to contain no element “0”.

Code:

class Solution:
    """
    @param nums: an array of positive and negative integers
    @return: if there is a loop in this array
    """
    def circularArrayLoop(self, nums):
        n = len(nums)
        remain = n
        for i in range(n):
            if nums[i] != None:

                j = i
                count = 1
                while True:
                    jj = j
                    j = (j + nums[j] + n) % n
                    if jj == j:
                        break
                    count += 1
                    if nums[j] == None or nums[j] * nums[i] < 0:
                        break

                    if count > remain:
                        return True

                j = i
                numsi = nums[i]
                while nums[j] != None:
                    jj = j
                    remain -= 1
                    j = (j + nums[j] + n) % n
                    nums[jj] = None
                    if nums[j] == None or nums[j] * numsi < 0:
                        break

        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36