You are given an integer array nums of length n where nums is a permutation of the numbers in the range [0, n - 1].
You should build a set s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ... } subjected to the following rule:
s[k] starts with the selection of the element nums[k] of index = k.s[k] should be nums[nums[k]], and then nums[nums[nums[k]]], and so on.s[k].Return the longest length of a set s[k].
Example 1:
Input: nums = [5,4,0,3,1,6,2]
Output: 4
Explanation:
nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.
One of the longest sets s[k]:
s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}
Example 2:
Input: nums = [0,1,2] Output: 1
Constraints:
1 <= nums.length <= 1050 <= nums[i] < nums.lengthnums are unique.In #565 Array Nesting, the array represents a set of index mappings where starting from an index i, you repeatedly move to nums[i]. This creates chains that eventually form cycles. The goal is to find the maximum size of such a chain.
A practical approach is to treat the array as a directed graph and explore each chain using Depth-First Search (DFS) or iterative traversal. Maintain a visited structure so each index is processed only once. For every unvisited index, follow the sequence i → nums[i] → nums[nums[i]] until a visited node appears, counting the length of that chain.
This works because each element belongs to exactly one cycle. By marking visited indices, we avoid recomputing the same chains and ensure linear processing. Some optimized solutions modify the array itself to mark visited nodes, reducing extra memory usage.
The resulting algorithm runs in O(n) time since each index is visited at most once, with O(n) or O(1) additional space depending on how visited nodes are tracked.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS / Iterative traversal with visited array | O(n) | O(n) |
| In-place traversal by marking visited elements | O(n) | O(1) |
NeetCodeIO
In this approach, we use an auxiliary 'visited' array to keep track of the elements that have already been included in any set s[k]. For each unvisited element at index i, we keep iterating through the sequence by accessing nums[nums[i]] until we encounter an element already visited. Each time we reach an unvisited element, we mark it as visited, and increment the length of the current sequence. We keep track of the longest length among all sequences generated from each starting index.
Time Complexity: O(N), where N is the number of elements in the array, as each element is visited at most once.
Space Complexity: O(N) due to the additional 'visited' array.
1#include <stdio.h>
2#include <stdbool.h>
3
4int arrayNesting(int* nums, int numsSize){
5 bool visited[numsSize]
This C program uses an iterative method with a boolean array to track visited elements. It loops through each element in the array and checks sequences starting from unvisited indices. The nested do-while loop continues until a visited element is encountered, at which point the sequence stops. The maximum length of the sequences encountered is stored and returned.
This approach minimizes space usage by modifying the input array itself as a marker of visited nodes. By setting each visited position to a sentinel value (e.g., -1 or a number outside the expected range), we can achieve the same iterative closure tracking. We simply iterate over each number and trace the sequence until we circle back to a marked node. This is an improvement on memory constraints when needing to handle particularly large datasets.
Time Complexity: O(N), executing a linear pass through the nodes.
Space Complexity: O(1), modifying input without auxiliary space.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, it can be viewed as a graph traversal problem where each index points to another index. This forms directed cycles, which can be explored using DFS or iterative traversal techniques.
Problems similar to Array Nesting appear in technical interviews because they test graph traversal, cycle detection, and efficient use of visited states. Understanding how to avoid redundant work is key to solving it optimally.
The optimal approach is to traverse the array chains while marking visited indices. Since each element belongs to exactly one cycle, visiting each index once ensures the longest chain can be found efficiently in linear time.
A simple visited array or set works well to track which indices have already been explored. In optimized solutions, the input array itself can be modified to mark visited nodes and avoid extra memory usage.
The C program adopts in-place marking to track progressing paths within nesting procedures. The primary loop controls the sequence length, adjusting and modifying indices by placing distinctions (as sentinel values) when indexes are processed. The solution ends by providing the largest found sequence, sidestepping additional space use for a tracker array.