#565

Medium

auto_awesomeArray plus Depth-First Search

LeetCode Problem Workspace

Array Nesting

Find the longest nested set in a permutation array using a depth-first traversal, handling cycles efficiently for medium-level complexity.

array depth first search

Problem Statement

You are given a permutation array nums of length n containing integers from 0 to n-1 without duplicates. For each index k, define a set s[k] starting from nums[k] and repeatedly following nums until a cycle occurs: s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ...}.

Return the length of the longest set s[k] that can be formed in this manner. You must efficiently handle cycles and ensure that each element is only counted once per set traversal.

Examples

Example 1

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

Output: 4

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

Example details omitted.

Constraints

1 <= nums.length <= 105
0 <= nums[i] < nums.length
All the values of nums are unique.

Solution Approach

DFS Traversal with Visited Tracking

Iterate through each index, and for unvisited elements, follow the nums chain recursively or iteratively. Mark each visited element to prevent revisiting and count the size of each set. Track the maximum size encountered to find the answer.

Cycle Detection Optimization

Since nums is a permutation, all chains eventually form cycles. Once a cycle is detected, terminate traversal and update the maximum set length. This avoids redundant work and leverages the problem's inherent cycle structure.

In-place Marking for Space Efficiency

Optionally, mark visited indices by modifying nums directly (e.g., setting to -1) to reduce extra space usage. This maintains linear time complexity while avoiding additional visited arrays.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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

Continue Practicing

#529 minesweeper #472 concatenated words #463 island perimeter