Array Nesting

Problem Id: 565 Difficulty: Medium


Intuition

Solution


class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        n = len(nums)
        length = [-1] * n
        for i in range(len(nums)):
            if length[i] == -1:
                self.update(nums, length, i)
        return max(length)

    def update(self, nums, length, i):
        visited = set()
        road = []
        while True:
            if length[i] != -1:
                base = length[i] + 1
                for j in range(len(road) - 1, -1, -1):
                    length[i] = base
                    base += 1
                return
            elif i in visited:
                cycle_length = 1
                j = nums[i]
                while j != i:
                    cycle_length += 1
                    j = nums[j]
                base = cycle_length
                j = len(road) - 1
                while cycle_length > 0:
                    length[road[j]] = base
                    j -= 1
                    cycle_length -= 1
                while j >= 0:
                    length[road[j]] = base
                    base -= 1
                return
            road.append(i)
            visited.add(i)
            i = nums[i]