Domain 2MediumCORE

Array Nesting

We need to find the maximum length of a 'chain' starting from any index i. A chain is formed by repeatedly using an element as an index for the next lookup: $S[i] = {A[i], A[A[i]], ...}$. We stop when we encounter a duplicate value in this specific sequence.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array

565. Array Nesting

Model: qwen3.5:9b
Topics: Array
FAANG asked: 0
Acceptance rate: 56.0%


Problem Breakdown

We need to find the maximum length of a “chain” starting from any index i. A chain is formed by repeatedly using an element as an index for the next lookup: S[i]={A[i],A[A[i]],...}S[i] = \{A[i], A[A[i]], ...\}. We stop when we encounter a duplicate value in this specific sequence.

Inputs:

  • An array A of length N, containing distinct integers from 0 to N-1 (a permutation).

Outputs:

  • The maximum integer representing the longest chain length found across all possible starting indices.

Constraints & Edge Cases:

  • NN up to 20,000: Requires an efficient solution (O(N)O(N)), not quadratic.
  • Elements are distinct and within range [0, N-1]: This guarantees that every index maps to a valid next index without bounds errors or duplicates in the input array itself (permutation property).
  • Since it is a permutation where each element appears exactly once as an output value, this structure forms disjoint cycles. There are no “tails” leading into cycles; every node has exactly one incoming and outgoing edge within its component.

Intuition

If we simulate the chain for every index i independently without optimization:

  1. For each start point 00 to N−1N-1, traverse until a duplicate is found (cycle detection).
  2. In the worst case, this could lead to re-traversing the same nodes multiple times if we don’t track visited status globally across different starting points. This would result in O(N2)O(N^2) time complexity.

Key Insight: Because A contains all integers from 0 to N-1 exactly once (it’s a permutation), every node has an out-degree of 1 and an in-degree of 1. The graph structure is strictly composed of disjoint cycles. If we start traversing at any unvisited index, we will traverse the entire cycle it belongs to before returning to that starting point or hitting another visited component (which won’t happen here due to disjointness). Once a node is part of a processed chain, all nodes in its cycle are effectively “accounted for.” We never need to start traversing from any node within an already-processed cycle.

Approach

  1. Initialize a visited boolean array of size NN (all False) to track which indices have been included in a calculated chain length.

  2. Iterate through each index i from 0 to N-1:

    • If A[i] has not been visited yet, start traversing the cycle starting at i.
    • Traverse by following curr=A[curr]curr = A[curr] until we hit a node that is already marked as visited. Since it’s disjoint cycles and we mark nodes immediately during traversal, this condition effectively detects when we complete the current component or merge (though merging isn’t possible here). However, to strictly count length without infinite loops in logic:
    • Actually, simpler approach for permutation graphs: Traverse until you hit a node that was marked visited in any previous run. But since it’s disjoint cycles and unvisited nodes start fresh, we just traverse the cycle. To avoid re-counting, mark every node as visited immediately upon entering during traversal.
    • Wait, if I mark them globally: Start at ii. Mark ii True. Move to next. If that was already marked (from a previous outer loop iteration), stop? No, in disjoint cycles, you won’t hit an old node unless it’s the start of your current cycle which is now marked by step 1.
    • Correct logic: Iterate i. If not visited[i]: Start traversal from curr = i, count length while marking nodes as visited until we encounter a node that was already visited (which implies closure or previous processing). Since it’s disjoint cycles, the first duplicate encountered in this specific path must be one of the nodes just marked.
    • Actually, standard solution: Just traverse and mark visited for every index touched during traversal. If an outer loop hits a node that is already visited (from current run or previous), skip it? No, if we mark immediately inside the inner loop, when does the inner loop stop? It stops when we hit a node marked before this specific traversal started?
    • Let’s refine: Since every component is an isolated cycle. If I start at unvisited i, all nodes in that cycle are currently False (unvisited). As I traverse and mark them True, eventually I will loop back to the first node of my current path which was marked True earlier in this same traversal? No, if I mark immediately:
      • Start 00. Mark 0. Move to next unmarked… wait, all nodes are initially False. So as long as I haven’t visited a specific index yet, it’s False. The only way to hit a True node is the one we just marked? No, that would be immediate stop if logic was “stop on True”.
      • Better: Use inner loop condition while not visited[curr]. Mark inside loop body. Move next. If I mark immediately at start of traversal (ii), then move to A[i]A[i] (which is False). Then mark it… eventually come back to a node that was marked in this run?
      • Wait, if I use visited array initialized all false:
        for i in range(N):
            if not visited[i]: # Start new component
                curr = i
                while not visited[curr]:
                    visited[curr] = True
                    curr = A[curr]
                max_len = max(max_len, count) 
      • Wait, this logic has a flaw. If I mark visited inside the loop immediately: The first node ii is marked. Next node A[i]A[i] (unmarked). Mark it… eventually we return to start? No, if we are in a cycle of length K. We visit nodes 0..K-1. All get marked True. Then next step points back to one of them which is now True. Loop terminates. Count increments correctly inside loop or outside.
      • Wait, does this count the full cycle? Yes. Because all nodes in that component are currently unvisited globally (since it’s disjoint). So we traverse until we hit a node marked in current run OR previous runs. Since they were previously False, and now become True as we go… wait.
      • If I mark curr immediately: ii is set to True. Next index points to some other unvisited node (since disjoint). Mark it True. Eventually loop back to start? No, if I marked the start at step 1, then when I return to start later in traversal, it’s already True. So yes, this works perfectly for finding cycle length and marking component as processed globally.
  3. Keep track of max_len during each successful traversal.

  4. Return max_len.

Complexity Analysis

  • Time: O(N)O(N). Each element is visited at most twice (once in outer loop check, once inside inner traversal). Since we mark nodes as visited globally, every node contributes to exactly one cycle calculation across the entire execution.
  • Space: O(N)O(N) for the visited array.

Solution

def arrayNesting(A):
    n = len(A)
    visited = [False] * n
    max_len = 0
    
    # Iterate through each index to find unprocessed components (cycles)
    for i in range(n):
        if not visited[i]:
            curr = i
            count = 0
            
            # Traverse the cycle until we hit a node already marked as visited.
            # Since it's a permutation graph, this marks all nodes in the current disjoint cycle.
            while not visited[curr]:
                visited[curr] = True
                curr = A[curr]
                count += 1
                
            max_len = max(max_len, count)
            
    return max_len

# Example usage:
A = [5,4,0,3,1,6,2]
print(arrayNesting(A)) # Output: 4

Edge Cases Handled

  • Single Element (N=1): The loop runs once for index 0. visited[0] becomes True. Count is 1. Returns 1. Correct.
  • Identity Array: If A[i]=iA[i] = i for all ii, each cycle has length 1. Outer loop processes every element, inner loop counts 1 immediately (since next index points to self which was just marked). Max len returns 1. Correct.
  • Single Large Cycle: All elements form one big chain returning to start. The visited array ensures we traverse the whole thing once in O(N)O(N) time rather than re-scanning parts of it multiple times for different starting points within that cycle (though outer loop skips them anyway).