Array Nesting
01 · Problem
You are given an array nums of length n that is a permutation of the integers 0 to n - 1 (every value appears exactly once).
For a starting index k, build the set s[k] by repeatedly following values as indices: start with nums[k], then add nums[nums[k]], then nums[nums[nums[k]]], and so on, stopping just before an element would be added a second time.
Return the size of the largest set s[k] over all k.
02 · Examples
nums = [5,4,0,3,1,6,2]
4
Starting at k = 0: nums[0] = 5, nums[5] = 6, nums[6] = 2, nums[2] = 0, which is already in the set, so s[0] = {5, 6, 2, 0} has size 4.
nums = [0,1,2]
1
Every element points to itself, so each set has exactly one element.
nums = [1,2,0]
3
0 -> 1 -> 2 -> 0 forms a single loop through every element, so every set has size 3.
03 · Constraints
- 011 <= nums.length <= 105
- 020 <= nums[i] < nums.length
- 03All values of nums are distinct
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.