Array Nesting: Finding the Longest Cycle in a Permutation

Array Nesting is LeetCode problem #565. At first glance it looks like you might need to simulate a bunch of nested lookups for every starting index. But once you see the hidden structure, the problem collapses into something much simpler: finding the longest cycle in a permutation.

The problem

You are given an integer array nums of length n where nums is a permutation of the numbers in the range [0, n - 1]. For each index k, you build a set by following the chain:

s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ...}

You keep adding elements until you hit a duplicate. Return the size of the longest such set.

The approach

Here is the key insight that unlocks this problem: since nums is a permutation, every value from 0 to n - 1 appears exactly once. That means following the chain from any index will always lead back to where you started. You will never run off the end of the array or get stuck. Every chain forms a cycle.

Think of it this way. Each index i points to nums[i], which is another valid index. Since no two indices point to the same value (it is a permutation), this creates a set of disjoint cycles covering all n indices. Every index belongs to exactly one cycle.

So the problem reduces to: find the longest cycle.

The naive approach would be to start a chain from every index, but that would revisit elements you have already explored. Instead, you can mark indices as visited. Once you have traced a full cycle starting from some index, every index in that cycle is accounted for. When you encounter a visited index later, you skip it. This way, each index is visited at most once across all iterations, giving you O(n) total time.

The solution

def arrayNesting(nums):
    visited = [False] * len(nums)
    max_len = 0

    for i in range(len(nums)):
        if visited[i]:
            continue
        count = 0
        j = i
        while not visited[j]:
            visited[j] = True
            j = nums[j]
            count += 1
        max_len = max(max_len, count)

    return max_len

The outer loop tries every index as a potential cycle start. The inner while loop follows the chain, marking each index as visited and counting the length. Once it hits a visited index (which will be the starting index, since we are tracing a cycle), it stops. The maximum count across all cycles is your answer.

Step-by-step walkthrough

Let's trace through nums = [5, 4, 0, 3, 1, 6, 2]. Blue cells are the current chain being explored. Orange cells have already been visited in a previous step.

We explored three cycles of lengths 4, 2, and 1. The answer is 4.

Complexity analysis

Time: O(n). Each index is visited exactly once. The outer for loop runs n times, but the inner while loop only processes unvisited indices. Across all iterations of the outer loop, the while loop runs a total of n times.

Space: O(n) for the visited array. If you are allowed to modify the input, you can mark visited indices by setting nums[j] = n (or any out-of-range sentinel), which brings space down to O(1). But the O(n) version is cleaner and what interviewers typically expect.

The building blocks

This problem is built from one core pattern:

Permutation cycle detection. When an array is a permutation of [0, n - 1], treating each element as a pointer to another index creates a set of disjoint cycles. You can traverse all cycles in O(n) total time by marking visited indices and skipping anything you have already seen.

This pattern appears in several related problems:

• Find the Duplicate Number (LeetCode 287) uses array values as implicit pointers, forming cycles. The duplicate creates the cycle entry point. Floyd's algorithm detects it.
• Linked List Cycle (LeetCode 141) is the classic cycle detection problem. Same idea of following pointers until you revisit a node, but in a linked list instead of an array.
• Circular Array Loop (LeetCode 457) asks you to detect cycles in a circular array where values indicate jump distances. Similar traversal logic, but with more constraints on what counts as a valid cycle.
• First Missing Positive (LeetCode 41) uses the same "permutation placement" insight. Each value belongs at a specific index, and cycling values into place reveals the missing one.

Once you recognize that a permutation defines a function from indices to indices, and that every such function on a finite set decomposes into disjoint cycles, you can solve this entire family of problems with the same mental model.

Edge cases

• Single element. nums = [0]. The only cycle is 0 -> 0, length 1. The algorithm handles this correctly since the while loop runs once before revisiting index 0.
• Identity permutation. nums = [0, 1, 2, ..., n-1]. Every element is a self-loop. Every cycle has length 1. The answer is 1.
• One giant cycle. nums = [1, 2, 3, ..., n-1, 0]. All elements form a single cycle of length n. The algorithm traces the whole array in one pass of the while loop and returns n.
• Two equal-length cycles. nums = [1, 0, 3, 2]. Two cycles of length 2. The algorithm finds both and returns 2.

From understanding to recall

This problem has a satisfying "aha" moment once you see the permutation-to-cycles connection. But recognizing that structure under time pressure is the hard part. The solution code itself is short, and the visited marking pattern is reusable. The real skill is looking at an array of indices and thinking "this is a permutation, so it decomposes into cycles."

Practice writing the solution from memory. Focus on the two-loop structure: the outer loop that scans for unvisited starting points, and the inner loop that follows the chain. Once that pattern is locked in, you can adapt it to any permutation cycle problem.

Related posts

• Find the Duplicate Number - Uses array values as implicit pointers to detect cycles with Floyd's algorithm
• Linked List Cycle - The classic cycle detection problem using fast and slow pointers
• Circular Array Loop - Detecting valid cycles in a circular array with directional constraints