LeetCode 565 - Array Nesting

LeetCode Problem 565

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search

Solution

Problem Understanding

The problem gives us an array nums that is guaranteed to be a permutation of the integers from 0 to n - 1. A permutation means every value appears exactly once, and every value is within the valid index range of the array.

For every starting index k, we repeatedly follow the chain:

• Start with nums[k]
• Move to nums[nums[k]]
• Then nums[nums[nums[k]]]
• Continue until we encounter a value that has already appeared in the current sequence

The resulting sequence forms a set s[k], and we want to compute the maximum possible size among all such sets.

Another way to think about the problem is that the array defines a directed graph where each index points to exactly one next index. Since the array is a permutation, every node has exactly one incoming and one outgoing edge. This structure naturally forms one or more cycles.

The task is therefore equivalent to finding the length of the largest cycle in the permutation graph.

Consider the first example:

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

Starting from index 0:

0 -> 5 -> 6 -> 2 -> 0

The values collected are:

{5, 6, 2, 0}

The cycle length is 4, which is the largest possible answer.

The constraints are important:

• nums.length can be as large as 10^5
• Every value is unique
• Every value is in the valid index range

These guarantees tell us several things:

• We must avoid quadratic solutions
• The traversal will never go out of bounds
• Since values are unique, the structure is entirely composed of disjoint cycles
• Each index belongs to exactly one cycle

A naive implementation could repeatedly revisit the same cycle many times, which would become too slow for large inputs. The key optimization is recognizing that once a node has been processed, we never need to process it again.

Important edge cases include:

• Arrays with a single element
• Arrays where every element points to itself
• Arrays containing one very large cycle
• Arrays containing multiple disjoint cycles of different lengths

Because the input is guaranteed to be a permutation, we never need to handle invalid indices or duplicate values.

Approaches

Brute Force Approach

The brute-force solution starts a traversal from every index independently.

For each starting position:

1. Create a temporary set to track visited elements in the current traversal
2. Repeatedly follow the next index
3. Stop when a duplicate is encountered
4. Record the size of the set

This approach is correct because it explicitly simulates the process described in the problem statement for every possible starting index.

However, it is inefficient because many traversals repeat the same work. If several starting points belong to the same cycle, the cycle gets traversed again and again.

For example:

0 -> 1 -> 2 -> 0

Starting from 0, 1, or 2 all traverse the exact same cycle.

In the worst case, a cycle of size n gets traversed n times, leading to O(n^2) time complexity.

Optimal Approach

The key insight is that each index belongs to exactly one cycle, and once we have visited a cycle, we never need to traverse it again.

We maintain a global visited array:

• If an index has already been processed, skip it
• Otherwise, traverse the cycle starting from that index
• Mark every encountered node as visited

Because each node is visited only once across the entire algorithm, the total work becomes linear.

This works particularly well because the permutation property guarantees:

• No branching paths
• No dead ends
• Every traversal eventually enters a cycle

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly traverses the same cycles
Optimal	O(n)	O(n)	Visits each index exactly once

Algorithm Walkthrough

1. Create a boolean visited array of length n.

This array tracks whether an index has already been processed in a previous traversal. Since each node belongs to exactly one cycle, revisiting processed nodes would only duplicate work. 2. Initialize a variable max_length to 0.

This variable stores the length of the largest cycle discovered so far. 3. Iterate through every index i in the array.

Each index is a potential starting point for a cycle traversal. 4. If visited[i] is already True, skip this index.

This means the current node already belongs to