Array Nesting - Solution & Explanation
Problem Statement
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:
- The first element in
s[k]starts with the selection of the elementnums[k]ofindex = k. - The next element in
s[k]should benums[nums[k]], and thennums[nums[nums[k]]], and so on. - We stop adding right before a duplicate element occurs in
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.length- All the values of
numsare unique.
Approach Overview
Problem Overview: You receive an integer array nums containing a permutation of values 0..n-1. Starting from index k, repeatedly jump to nums[k], then nums[nums[k]], forming a sequence until a value repeats. The task is to compute the maximum size of such a set.
The key observation: because the array is a permutation, following indices forms disjoint cycles. The size of the largest cycle equals the answer. The task becomes detecting cycle lengths efficiently without reprocessing elements.
Approach 1: Iterative Using Visited Array (O(n) time, O(n) space)
Treat the array as a directed graph where each index points to nums[i]. Each component forms a cycle. Maintain a boolean visited array so every element is processed only once. For each index i, if it hasn't been visited, repeatedly follow the chain i → nums[i] → nums[nums[i]] while marking nodes visited and counting the cycle length. Track the maximum length across all cycles.
This approach is straightforward and easy to reason about. Each index is visited at most once, giving O(n) total traversal time and O(n) auxiliary memory. It's ideal when clarity matters or when modifying the input array is not allowed. The traversal pattern resembles cycle exploration in Depth-First Search, although implemented iteratively on an array.
Approach 2: In-Place Modification without Extra Space (O(n) time, O(1) space)
The permutation constraint allows marking visited elements directly inside the array. When traversing a chain, replace visited values with a sentinel such as -1. Start from index i, repeatedly move to next = nums[i], count the length, and mark nums[i] = -1 to indicate it has been processed. Stop when the traversal reaches a marked element.
This eliminates the separate visited array and keeps memory usage constant. Each index is still processed exactly once, so runtime remains O(n). The tradeoff is mutating the input array, which may not be allowed in some environments but is perfectly acceptable in most coding interviews.
Recommended for interviews: Both approaches achieve optimal O(n) time by recognizing the permutation cycles. Start with the visited-array method because it clearly demonstrates cycle detection and safe traversal. If the interviewer asks about space optimization, transition to the in-place marking approach to reduce memory to O(1). Showing both demonstrates strong understanding of cycle traversal patterns in arrays.
Approach 1: Approach 1: Iterative Using Visited Array
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.
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.
Complexity
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.
Approach 2: Approach 2: In-Place Modification without Extra Space
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.
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.
Complexity
Time Complexity: O(N), executing a linear pass through the nodes.
Space Complexity: O(1), modifying input without auxiliary space.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Iterative Using Visited Array | Time Complexity: O(N), where N is the number of elements in the array, as each element is visited at most once. |
| Approach 2: In-Place Modification without Extra Space | Time Complexity: O(N), executing a linear pass through the nodes. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Cycle Traversal with Visited Array | O(n) | O(n) | Best for clarity and when modifying the input array is not allowed |
| In-Place Modification (Mark Visited) | O(n) | O(1) | Memory-constrained scenarios or when the array can be safely modified |
Video Solution
Array Nesting | Leetcode 565 | Live coding session 🔥🔥🔥🔥 • Coding Decoded • 3,324 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Array Nesting easy or hard?
Array Nesting Python/Java solution
How to solve Array Nesting in O(n)?
What is the best approach for Array Nesting?
Is Array Nesting asked at Google/Amazon/Meta?
What data structure is used in Array Nesting?
What is the time complexity of Array Nesting?
Ready to solve this problem?
Practice Array Nesting with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor