Array Nesting — Cycle Detection in Functional Graphs [LC 565]

Problem Statement#

Given an array nums of length n where nums[i] is in range [0, n-1] and all values are distinct, starting from index i, build a set S = {nums[i], nums[nums[i]], nums[nums[nums[i]]], ...} until revisiting an element. Return the maximum length of any such set S.

Constraints:

• 1 <= nums.length <= 2 * 10^4
• 0 &lt;= nums[i] < n
• All values in nums are distinct

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

Input:  nums = [0,1,2]
Output: 1

Why This Problem Matters#

LeetCode 565 is a functional graph cycle detection problem asked at Amazon and Google. The array defines a permutation where each index points to another index — the structure is a collection of disjoint cycles. Finding the longest cycle means finding the largest connected component.

The optimal insight is to mark visited nodes in-place (by setting them to n, which is an out-of-range sentinel value) so we never revisit them. This avoids a visited set and achieves O(1) extra space — a trick that appears in Find the Duplicate Number (LC 287) and First Missing Positive (LC 41).

The Core Insight#

Every element in a permutation belongs to exactly one cycle. Start from any unvisited index, follow the chain i → nums[i] → nums[nums[i]] → ... until you return to a visited node. Count the length of this cycle.

Visited marking: After processing a cycle, set each visited index to n (sentinel). Future starting points will immediately see a visited node and contribute length 0 — no need for a separate boolean array.

The total work across all cycles is O(n) — each index is visited exactly once.

Visual Dry Run#

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

Maximum cycle length = 4.

Trace from 0: nums[0]=5, nums[5]=6, nums[6]=2, nums[2]=0 — back to 0, length 4. After marking: indices 0,5,6,2 set to 7 (= n).

Solution (Optimal)#

class Solution:
    def arrayNesting(self, nums):
        n = len(nums)
        best = 0
        for i in range(n):
            if nums[i] == n:   # already visited
                continue
            length = 0
            j = i
            while nums[j] != n:  # follow chain until visited
                next_j = nums[j]
                nums[j] = n      # mark as visited (sentinel)
                j = next_j
                length += 1
            best = max(best, length)
        return best

var arrayNesting = function(nums) {
    const n = nums.length;
    let best = 0;
    for (let i = 0; i < n; i++) {
        if (nums[i] === n) continue;
        let length = 0;
        let j = i;
        while (nums[j] !== n) {
            const next = nums[j];
            nums[j] = n;       // mark visited
            j = next;
            length++;
        }
        best = Math.max(best, length);
    }
    return best;
};

Time: O(n) — each index visited at most once across all cycles Space: O(1) — in-place marking with sentinel, no extra visited array

Common Mistakes#

• Using a separate visited set — works but uses O(n) extra space unnecessarily
• Not handling the sentinel correctly — must check nums[j] == n (not nums[i]) in the while condition
• Modifying the array without restoring — if the problem guarantees no modification, use a separate visited set
• Counting incorrectly — the while loop increments length before marking, which is correct since we haven't counted the current node yet
• Assuming the cycle starts at i — the chain from i might lead to a cycle that was already partially counted (but the sentinel prevents this)

Interview Tips#

• Start by explaining the structure: "the array is a permutation — every node belongs to exactly one cycle"
• Explain the sentinel: "set visited nodes to n (out-of-range) so we skip them in the outer loop without extra memory"
• Prove O(n) time: "each index is visited at most once across all iterations of the outer loop — total work is O(n)"
• If the interviewer asks about modifying the input, offer the visited set alternative
• Connect to functional graph theory: this is exactly the problem of finding the longest cycle in a functional graph

Follow-up Questions#

• What if you cannot modify the input array? (Use a boolean visited array — O(n) space but O(n) time)
• How many distinct cycles are there? (Count the number of "chain starts" — each time you find an unvisited node and its chain forms a new cycle)
• What if values can repeat (not a permutation)? (The chain might not form clean cycles — need explicit cycle detection like Floyd's algorithm)
• How does this relate to Find the Duplicate Number (LC 287)? (Both use the index-as-pointer trick in permutation-like arrays)
• Can you find the actual nodes in the longest cycle, not just the length? (Record each visited node in the current chain before the sentinel)

Key Takeaways#

• LeetCode 565 is asked at Amazon and Google — functional graph where every node belongs to exactly one cycle
• The permutation structure guarantees clean cycles — no need for general cycle detection algorithms
• In-place sentinel marking (set visited to n) achieves O(1) extra space without a visited array
• Time O(n) — each index is visited exactly once across all starting points
• The outer loop skips sentinel-marked nodes immediately — amortized constant work per node
• This pattern — follow chain, mark visited in-place, track length — appears in Missing Number, Find Duplicate, and First Missing Positive
• If the input cannot be modified, substitute a boolean visited array for O(n) space but same O(n) time