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: . We stop when we encounter a duplicate value in this specific sequence.
Inputs:
- An array
Aof lengthN, 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:
- up to 20,000: Requires an efficient solution (), 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:
- For each start point to , traverse until a duplicate is found (cycle detection).
- 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 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
-
Initialize a
visitedboolean array of size (all False) to track which indices have been included in a calculated chain length. -
Iterate through each index
ifrom 0 to N-1:- If
A[i]has not been visited yet, start traversing the cycle starting ati. - Traverse by following 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
visitedin 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 . Mark 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 fromcurr = 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
visitedfor 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 . 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
Truenode 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 (), then move to (which is False). Then mark it… eventually come back to a node that was marked in this run? - Wait, if I use
visitedarray 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
visitedinside the loop immediately: The first node is marked. Next node (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
currimmediately: 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.
- Start . 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
- If
-
Keep track of
max_lenduring each successful traversal. -
Return
max_len.
Complexity Analysis
- Time: . 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: for the
visitedarray.
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 for all , 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
visitedarray ensures we traverse the whole thing once in time rather than re-scanning parts of it multiple times for different starting points within that cycle (though outer loop skips them anyway).