Watch 10 video solutions for Array Nesting, a medium level problem involving Array, Depth-First Search. This walkthrough by Coding Decoded has 3,264 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.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 | 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 |