What is the core pattern in Array Nesting?

The pattern involves traversing a permutation array using depth-first search to form sets until cycles are detected, maximizing set length.

Can I modify the input array in Array Nesting?

Yes, in-place marking like setting visited elements to -1 is allowed to reduce extra space usage.

Why do we need to track visited indices?

Tracking prevents revisiting elements, avoids infinite loops, and ensures correct counting of set lengths.

Is recursion necessary for this problem?

No, iterative DFS using a while loop can also efficiently handle nested traversal and cycle detection.

What is the maximum complexity for Array Nesting?

Using proper DFS with visited marking, time complexity is O(n) and space is O(n) if using a separate visited array, or O(1) with in-place marking.

#565

Medium

auto_awesome图·搜索

LeetCode 题解工作台

数组嵌套

索引从 0 开始长度为 N 的数组 A ，包含 0 到 N - 1 的所有整数。找到最大的集合 S 并返回其大小，其中 S[i] = {A[i], A[A[i]], A[A[A[i]]], ... } 且遵守以下的规则。假设选择索引为 i 的元素 A[i] 为 S 的第一个元素， S 的下一个元素…

数组深度优先搜索

题目描述

索引从0开始长度为N的数组A，包含0到N - 1的所有整数。找到最大的集合S并返回其大小，其中 S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }且遵守以下的规则。

假设选择索引为i的元素A[i]为S的第一个元素，S的下一个元素应该是A[A[i]]，之后是A[A[A[i]]]... 以此类推，不断添加直到S出现重复的元素。

示例 1:

输入: A = [5,4,0,3,1,6,2]
输出: 4
解释: 
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.

其中一种最长的 S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

提示：

1 <= nums.length <= 10⁵
0 <= nums[i] < nums.length
A中不含有重复的元素。

lightbulb

解题思路

方法一：图

嵌套数组最终一定会形成一个环，在枚举 $nums[i]$ 的过程中，可以用 $vis$ 数组剪枝，避免重复枚举同一个环。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        n = len(nums)
        vis = [False] * n
        res = 0
        for i in range(n):
            if vis[i]:
                continue
            cur, m = nums[i], 1
            vis[cur] = True
            while nums[cur] != nums[i]:
                cur = nums[cur]
                m += 1
                vis[cur] = True
            res = max(res, m)
        return res

speed

复杂度分析

指标	值
时间	complexity is O(n) because each index is visited at most once in the DFS traversal. Space complexity is O(1) with in-place marking or O(n) if using a separate visited array to track already traversed indices.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Watch if the candidate identifies the cycle-based nature of traversal early.
question_mark
Check if the candidate correctly marks visited indices to avoid double counting.
question_mark
See if the candidate optimizes space using in-place modifications rather than extra arrays.

warning

常见陷阱

外企场景

error
Failing to detect cycles can cause infinite loops in the traversal.
error
Revisiting already counted indices inflates set sizes and wastes time.
error
Using nested loops instead of linear DFS leads to unnecessary O(n^2) complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow arrays with duplicate values, requiring counting unique elements per set.
arrow_right_alt
Compute the number of sets that reach the maximum length instead of just the length.
arrow_right_alt
Return all indices forming the longest nested set instead of just its size.

help

常见问题

外企场景

继续练习

#529 扫雷游戏 #472 连接词 #463 岛屿的周长