Problem Description

You have an integer array nums of length n that contains a permutation of all numbers from 0 to n-1 (each number appears exactly once).

For each starting index k, you need to build a set s[k] following these rules:

• Start with the element at index k: add nums[k] to the set
• Next, use the value you just added as the new index: add nums[nums[k]] to the set
• Continue this pattern: add nums[nums[nums[k]]], and so on
• Stop when you would add a duplicate element (an element already in the set)

Essentially, you're following a chain of indices where each element points to the next index to visit, creating a cycle since the array is a permutation.

For example, if nums = [5,4,0,3,1,6,2]:

• Starting at index 0: s[0] = {5, 6, 2, 0} (follow the chain: 0→5→6→2→0, stop before adding 0 again)
• Starting at index 1: s[1] = {4, 1} (follow the chain: 1→4→1, stop before adding 1 again)

Your task is to find the maximum length among all possible sets s[k] for k from 0 to n-1.

The solution uses a visited array to track which elements have already been part of a cycle. Since the array is a permutation, each element belongs to exactly one cycle. Once we've explored a cycle starting from any element in it, we don't need to explore it again from other starting points in the same cycle. The algorithm iterates through each unvisited index, follows its cycle while marking elements as visited, counts the cycle length, and keeps track of the maximum length found.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: Even though we have an array, we can model this as a graph problem. Each index i has a directed edge to index nums[i]. Since the array is a permutation, each node has exactly one outgoing edge and one incoming edge, forming one or more cycles.

Is it a tree?

• No: Trees don't have cycles, but our graph structure has cycles. When we follow the chain nums[k] → nums[nums[k]] → ..., we eventually return to a previously visited element, forming a cycle.

Is the problem related to directed acyclic graphs?

• No: Our graph has cycles (it's not acyclic). The permutation property guarantees that following the indices will create cycles.

Is the problem related to shortest paths?

• No: We're not looking for shortest paths between nodes. We want to find the longest cycle length.

Does the problem involve connectivity?

• Yes: We need to explore connected components (cycles) in the graph. Each cycle is a connected component where we follow edges until we return to the starting point.

Does the problem have small constraints?

• Yes: While the array can be up to length 10^5, each element is visited at most once when exploring cycles, making it tractable.

DFS/backtracking?

• Yes: We use DFS to traverse each cycle. Starting from an unvisited node, we follow the edges (using DFS) until we complete the cycle, tracking the length of each cycle.

Conclusion: The flowchart suggests using a DFS approach. We treat the array as a graph where each index points to another index, and use DFS to explore cycles, keeping track of visited nodes to avoid reprocessing the same cycle. The maximum cycle length found during this traversal is our answer.

Intuition

The key insight is recognizing that this array forms a special graph structure. Since nums is a permutation of [0, n-1], each index appears exactly once as a value. This means:

• Every index has exactly one outgoing edge (to nums[index])
• Every index has exactly one incoming edge (from some other index whose value is this index)

This creates a graph where every node has degree 2 (one in, one out), which means the graph must consist of one or more disjoint cycles. There are no dead ends or branching paths - just pure cycles.

When we start at any index k and follow the chain k → nums[k] → nums[nums[k]] → ..., we're essentially walking along one of these cycles. Since it's a cycle, we'll eventually return to where we started. The length of set s[k] is simply the length of the cycle that contains index k.

Here's the crucial realization: all indices in the same cycle will produce the same set length. If indices i and j are in the same cycle, then s[i] and s[j] will have the same length - they're just different starting points on the same circular path.

This means we don't need to check every possible starting index redundantly. Once we've explored a cycle from any starting point, we've found the length for all indices in that cycle. We can mark all nodes in that cycle as "visited" and skip them in future iterations.

The algorithm naturally follows:

1. For each unvisited index, perform a DFS to trace through its cycle
2. Mark all nodes in the cycle as visited while counting the cycle length
3. Keep track of the maximum cycle length encountered

The time complexity is O(n) because each element is visited exactly once across all DFS traversals, even though we might start multiple DFS calls. The space complexity is O(n) for the visited array.

Learn more about Depth-First Search patterns.

Solution Approach

The implementation uses a visited array to efficiently track which elements have already been processed as part of a cycle exploration.

Data Structures Used:

• vis: A boolean array of size n to mark visited indices
• res: Variable to track the maximum cycle length found

Algorithm Steps:

1. Initialize tracking structures:

   • Create a vis array of size n, initially all False
   • Set res = 0 to track the maximum cycle length

2. Iterate through each index:

   for i in range(n):
       if vis[i]:
           continue  # Skip if already part of a processed cycle

3. For each unvisited index, trace its cycle:

   • Start with cur = nums[i] (first element in the cycle)
   • Initialize cycle length m = 1
   • Mark vis[cur] = True

4. Follow the cycle until we return to the starting point:

   while nums[cur] != nums[i]:
       cur = nums[cur]      # Move to next element in cycle
       m += 1               # Increment cycle length
       vis[cur] = True      # Mark as visited

   The condition nums[cur] != nums[i] checks if we've completed the cycle. When nums[cur] == nums[i], it means the next element would be nums[i] again (back to where we started), so we stop.

5. Update the maximum cycle length:

   res = max(res, m)

Why this works:

• Each element belongs to exactly one cycle due to the permutation property
• Once we've measured a cycle from any starting point within it, all elements in that cycle are marked as visited
• We never process the same cycle twice, ensuring O(n) time complexity
• The visited array prevents redundant work while allowing us to find all distinct cycles

Example walkthrough with nums = [5,4,0,3,1,6,2]:

• Start at index 0: Follow 0→5→6→2→0, cycle length = 4
• Start at index 1: Follow 1→4→1, cycle length = 2
• Start at index 3: Follow 3→3, cycle length = 1
• Indices 2, 4, 5, 6 are already visited, so skip them
• Maximum cycle length = 4

Example Walkthrough

Let's trace through the algorithm with nums = [2,1,0,4,3]:

Initial State:

• vis = [False, False, False, False, False]
• res = 0

Iteration 1: i = 0

• vis[0] is False, so we explore this cycle
• Start with cur = nums[0] = 2, mark vis[2] = True, m = 1
• Follow the cycle:
  • nums[2] = 0 ≠ nums[0] = 2, so continue
  • cur = nums[2] = 0, mark vis[0] = True, m = 2
  • nums[0] = 2 = nums[0] = 2, so stop
• Cycle: 0→2→0, length = 2
• Update res = max(0, 2) = 2
• vis = [True, False, True, False, False]

Iteration 2: i = 1

• vis[1] is False, so we explore this cycle
• Start with cur = nums[1] = 1, mark vis[1] = True, m = 1
• Check: nums[1] = 1 = nums[1] = 1, so stop immediately
• Cycle: 1→1 (self-loop), length = 1
• res = max(2, 1) = 2
• vis = [True, True, True, False, False]

Iteration 3: i = 2

• vis[2] is True (already visited in iteration 1), skip

Iteration 4: i = 3

• vis[3] is False, so we explore this cycle
• Start with cur = nums[3] = 4, mark vis[4] = True, m = 1
• Follow the cycle:
  • nums[4] = 3 ≠ nums[3] = 4, so continue
  • cur = nums[4] = 3, mark vis[3] = True, m = 2
  • nums[3] = 4 = nums[3] = 4, so stop
• Cycle: 3→4→3, length = 2
• res = max(2, 2) = 2
• vis = [True, True, True, True, True]

Iteration 5: i = 4

• vis[4] is True (already visited in iteration 4), skip

Final Result: Maximum cycle length = 2

The algorithm efficiently found three cycles:

• Cycle 1: {0, 2} with length 2
• Cycle 2: {1} with length 1
• Cycle 3: {3, 4} with length 2

Each element was visited exactly once, and we correctly identified the maximum cycle length as 2.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input array nums.

The algorithm visits each element in the array exactly once. Although there's a nested while loop inside the for loop, each element is only processed once due to the vis array marking visited elements. Once an element is marked as visited (vis[i] = True), it will be skipped in future iterations of the outer loop. Therefore, the total number of operations across all iterations is bounded by n, resulting in linear time complexity.

Space Complexity: O(n) where n is the length of the input array nums.

The algorithm uses an additional boolean array vis of size n to track visited elements. This auxiliary array requires O(n) space. The remaining variables (cur, m, res, i) use constant space O(1). Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrectly marking the starting index as visited

The Problem: A common mistake is marking visited[i] = True (the starting index) instead of visited[nums[i]] = True (the first element in the cycle). This causes an off-by-one error where you miss counting one element in each cycle.

Incorrect Code:

for i in range(n):
    if visited[i]:
        continue
  
    visited[i] = True  # WRONG: marking the starting index
    current = nums[i]
    cycle_length = 1
  
    while nums[current] != nums[i]:
        current = nums[current]
        cycle_length += 1
        visited[current] = True

Why it's wrong:

• Index i might not be part of the cycle that starts from nums[i]
• For example, if nums = [1, 0] and we start at index 0:
  • The cycle from index 0 is: 0→1→0 (contains indices 0 and 1)
  • But if we mark visited[0] = True initially and then only mark indices during traversal, we'd mark 0 and 1
  • When we later try index 1, it's already marked visited, so we skip it
  • However, this creates inconsistency in what "visited" means

Correct Approach:

for i in range(n):
    if visited[i]:
        continue
  
    current = nums[i]
    cycle_length = 1
    visited[current] = True  # Mark the first element in the cycle
  
    while nums[current] != nums[i]:
        current = nums[current]
        cycle_length += 1
        visited[current] = True

Pitfall 2: Using the wrong termination condition

The Problem: Using while current != i instead of while nums[current] != nums[i] as the loop condition.

Incorrect Code:

while current != i:  # WRONG: comparing index with value
    current = nums[current]
    cycle_length += 1
    visited[current] = True

Why it's wrong:

• current holds a value from the array (which represents an index to jump to)
• i is the starting index position
• These two might never be equal if index i is not part of its own cycle
• For example, with nums = [1, 2, 0] starting at index 0:
  • current starts as nums[0] = 1
  • We'd be checking if 1 != 0, which is true
  • Next, current becomes nums[1] = 2
  • We'd check if 2 != 0, which is true
  • Next, current becomes nums[2] = 0
  • We'd check if 0 != 0, which is false, so we stop
  • This happens to work here, but it's conceptually wrong

Correct Approach: The condition should check if the next element in the sequence would be the same as the first element we added:

while nums[current] != nums[i]:  # Correct: checking if we'd revisit the first element
    current = nums[current]
    cycle_length += 1
    visited[current] = True

Pitfall 3: Not handling single-element cycles correctly

The Problem: Failing to account for self-loops where nums[i] == i.

Why it matters:

• If nums[3] = 3, this forms a cycle of length 1
• The standard traversal logic should handle this, but some implementations might accidentally skip or miscount these cases

Verification: The correct implementation naturally handles this case:

• Start at index 3 where nums[3] = 3
• Set current = nums[3] = 3, cycle_length = 1
• Check condition: nums[3] != nums[3] is False
• Loop doesn't execute, returns cycle_length = 1 ✓

Best Practice: Always test edge cases including:

• Single-element cycles (nums[i] = i)
• Two-element cycles (nums[i] = j and nums[j] = i)
• Full array as one cycle