medium

Array Nesting

Find the longest cycle formed by repeatedly indexing into a permutation.

1. Define the problem

Array Nesting

You are given an integer array nums of length n, where nums is a permutation of the numbers 0 to n - 1. Following the sequence i, numsi, nums[numsi], … eventually returns to i, forming a cycle . Return the length of the longest such cycle across all starting points. Since a permutation splits cleanly into disjoint cycles, walk each unvisited starting index once, following the chain until it loops back, and remember the longest chain found.

Constraints

  • 1 ≤ nums.length ≤ 105
  • 0 ≤ numsi < nums.length
  • All the values of nums are unique.

Example

Inputnums = [5, 4, 0, 3, 1, 6, 2]
Output4

Explanation Starting at index 0: 0 → 5 → 6 → 2 → back to 0, a cycle of length 4 — the longest one in this array.

2. Know the words first

In plain terms

Permutation
An array containing each number from 0 to n - 1 exactly once, in some order.
Cycle
A loop formed by repeatedly jumping from index i to index numsi until you land back where you started.
3. Visualize the solution

Walk each unvisited index, following its cycle

Walk each unvisited index, following its cycle
Statusvisit

Start at index 0. Mark it visited, length becomes 1, jump to nums[0]=5.

What happens in this step

current = 0, length = 1
nums[0] = 5 → current becomes 5
Step 1 of 6

Steps to visualize

  1. Pick the first index that has not been visited yet and start walking its chain: current, then numscurrent, and so on.
  2. Mark each index visited as you land on it, counting the length as you go.
  3. Stop when the chain lands on an already-visited index — that closes the cycle.
  4. Keep the largest cycle length seen across every starting index, skipping any index already absorbed into an earlier cycle.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Walk each unvisited index, following its cycle
Statusvisit

Start at index 0. Mark it visited, length becomes 1, jump to nums[0]=5.

What happens in this step

current = 0, length = 1
nums[0] = 5 → current becomes 5
Step 1 of 6
5. Solution

Solution

solution.tsTypeScript
function arrayNesting(nums) {
  const visited = new Array(nums.length).fill(false);
  let longest = 0;

  for (let i = 0; i < nums.length; i++) {
    if (visited[i]) {
      continue;
    }

    let length = 0;
    let current = i;

    while (!visited[current]) {
      visited[current] = true;
      current = nums[current];
      length++;
    }

    longest = Math.max(longest, length);
  }

  return longest;
}
Time
O(n)
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
nums = [5, 4, 0, 3, 1, 6, 2]4example from the docstring
nums = [0]1smallest valid input: a single self-loop
nums = [0, 1, 2, 3]1every index is its own cycle of length 1
nums = [3, 2, 1, 0]2two disjoint cycles of equal length
nums = [1, 2, 3, 4, 0]5the entire array forms a single cycle
nums = [1, 0]2the smallest non-trivial two-element cycle

Keep reading