aboutsummaryrefslogtreecommitdiff
path: root/array_nesting.py
blob: 3cec7f55a02461e0bb57b6da5f2e6bc1e971b329 (plain)
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
# 565. Array Nesting

"""
you are given an integer array 'nums' of length 'n' where 'nums' is a
permutation of the numbers in the range '[0, n - 1]'. you should bild a set
's[k] = {nums[k], nums[nums[k]], ... }' subjected to the following rules: the
first element in 's[k]' starts with the selection of the element 'nums[k]' of
'index = k'. the next element in 's[k]' should be 'nums[nums[k]]', and so on.
we stop adding right before a duplication element occurs in 's[k]'. return
the longest set of 's[k]'
"""


class Solution(object):
    def arrayNesting(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        seen, ans = [0] * len(nums), 0
        for i in nums:
            cnt = 0
            while not seen[i]:
                seen[i], cnt, i = 1, cnt + 1, nums[i]
            ans = max(ans, cnt)
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.arrayNesting(nums=[5, 4, 0, 3, 1, 6, 2]))
    print(obj.arrayNesting(nums=[0, 1, 2]))