LeetCode 565: Array Nesting

Problem Restatement

We are given an integer array nums of length n.

The array is a permutation of the numbers from 0 to n - 1. That means every value appears exactly once.

For each starting index k, we build a set:

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

We stop right before a duplicate value would be added.

Return the largest possible size of s[k].

The constraints are 1 <= nums.length <= 10^5, 0 <= nums[i] < nums.length, and all values in nums are unique. The examples include nums = [5,4,0,3,1,6,2], output 4, and nums = [0,1,2], output 1.

Input and Output

Example function shape:

def arrayNesting(nums: list[int]) -> int:
    ...

Examples

Example 1:

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

Start at index 0.

The sequence is:

nums[0] = 5
nums[5] = 6
nums[6] = 2
nums[2] = 0
nums[0] = 5

Before adding duplicate 5, the set is:

{5, 6, 2, 0}

Its length is:

4

So the answer is:

4

Example 2:

nums = [0, 1, 2]

Each index points to itself:

nums[0] = 0
nums[1] = 1
nums[2] = 2

Every nesting set has length 1.

So the answer is:

1

First Thought: Simulate From Every Index

A direct solution is to start from every index and follow the chain until a duplicate appears.

For each start, we can use a set to remember values already seen in that chain.

This works, but it repeats work.

If one starting index enters a cycle, every other index in the same cycle will produce the same cycle length. We should not traverse that cycle again.

Key Insight

Because nums is a permutation, every index has exactly one outgoing edge:

i -> nums[i]

Every value is also unique, so every index has exactly one incoming edge.

This means the array forms disjoint cycles.

The problem asks for the length of the largest cycle.

Once we traverse a cycle, every index in that cycle is fully processed. Starting from any of them again cannot give a new answer.

So we keep a global visited array.

Algorithm

1. Create a boolean array visited of length n.
2. Initialize ans = 0.
3. For each index i:
   1. If i is already visited, skip it.
   2. Otherwise, follow the chain:

      i -> nums[i] -> nums[nums[i]] -> ...
   3. Count how many unvisited indices are reached.
   4. Mark each reached index as visited.
   5. Update ans.

Correctness

Since nums is a permutation of 0 through n - 1, following the rule i = nums[i] can never leave the valid index range.

Because there are only finitely many indices, the sequence must eventually repeat. Since every value is unique, the repeated structure is a cycle.

For any starting index inside a cycle, following nums visits exactly the indices in that cycle before returning to the start. Therefore, the length of the nesting set is exactly the cycle length.

The algorithm traverses each unvisited cycle once, counts its length, and marks all indices in it as visited. Later starts inside the same cycle are skipped, which does not lose any larger answer because they have the same cycle length.

Since every index belongs to exactly one cycle, the algorithm considers every cycle exactly once and returns the largest cycle length.

Complexity

Let n = len(nums).

Implementation

class Solution:
    def arrayNesting(self, nums: list[int]) -> int:
        n = len(nums)
        visited = [False] * n
        ans = 0

        for i in range(n):
            if visited[i]:
                continue

            length = 0
            current = i

            while not visited[current]:
                visited[current] = True
                current = nums[current]
                length += 1

            ans = max(ans, length)

        return ans

Code Explanation

We keep track of processed indices:

visited = [False] * n

For every possible starting index:

for i in range(n):

we skip it if it already belongs to a cycle we processed:

if visited[i]:
    continue

Otherwise, we follow the chain:

current = i

while not visited[current]:

Inside the loop, we mark the current index and move to the next index:

visited[current] = True
current = nums[current]
length += 1

When we reach an already visited index, the current cycle has ended.

Then we update the best answer:

ans = max(ans, length)

In-Place Version

We can also mark visited indices directly inside nums.

Since every value is originally in the range 0 to n - 1, we can use n as a sentinel value.

This changes the input array.

class Solution:
    def arrayNesting(self, nums: list[int]) -> int:
        n = len(nums)
        ans = 0

        for i in range(n):
            length = 0

            while nums[i] != n:
                next_i = nums[i]
                nums[i] = n
                i = next_i
                length += 1

            ans = max(ans, length)

        return ans

This version uses O(1) extra space, but it mutates nums.

Testing

def run_tests():
    s = Solution()

    assert s.arrayNesting([5, 4, 0, 3, 1, 6, 2]) == 4
    assert s.arrayNesting([0, 1, 2]) == 1
    assert s.arrayNesting([1, 2, 0]) == 3
    assert s.arrayNesting([1, 0, 3, 2]) == 2
    assert s.arrayNesting([2, 0, 1, 4, 3]) == 3

    print("all tests passed")

run_tests()