[Leetcode] 565. Array Nesting array nesting

tags: LeetCode  Algorithm  Python 

A zero-indexed array A of length N contains all integers from 0 to N-1. Find and return the longest length of set S, where S[i] = {A[i], A[A[i]], A[A[A[i]]], ... } subjected to the rule below.

Suppose the first element in S starts with the selection of element A[i] of index = i, the next element in S should be A[A[i]], and then A[A[A[i]]]… By that analogy, we stop adding right before a duplicate element occurs in S.

Example 1:

Input: A = [5,4,0,3,1,6,2] Output: 4 Explanation: A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2. One of the longest S[K]: S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

Solution:

This question is actually the largest ring. It should be noted that once it is accessed in the previous different rings, it will not appear in the current ring, which can be ignored.

The idea is to, start from every number, find circles in those index-pointer-chains, every time you find a set (a circle) mark every number as visited (-1) so that next time you won't step on it again.

 

 

 

Python:

class Solution(object):
    def arrayNesting(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans, step, n = 0, 0, len(nums)
        
        seen = [False] * n # 두 개의 리스트 활용 
        for i in range(n): # 탐색의 시작포인트를 brute force 로 탐색 시작
            while not seen[i]: # seen[i] 가 False 이면 True 로 바꾸고 계속 진행, True 이면 Stop 
                seen[i] = True # True 로 변경 
                i, step = nums[i], step + 1 # i = nums[i] index를 value 로 찾고, 다시 value 가 index
            ans = max(ans, step)
            step = 0
        return ans

#Ref: https://www.programmerall.com/article/80591154229/