Medium

Quiz

#565 Array Nesting

APPROACH

You are given an integer array nums of length n, which is a permutation of [0, n - 1]. Starting from any index k, follow the chain k -> nums[k] -> nums[nums[k]] -> ... until an index repeats to form a set. Return the size of the largest set producible by any starting index k.

Example 1:

Input: nums = [5,4,0,3,1,6,2]

Output: 4

Explanation:

nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.

One of the longest sets s[k]:

s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}

Example 2:

Input: nums = [0,1,2]

Output: 1

1 of 4

1:00

What is the optimal approach for this problem?