Array Nesting
MedPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through every possible starting index from 0 to n-1. For each starting index k, it simulates the process of building the set s[k] by following the chain of indices: k -> nums[k] -> nums[nums[k]] -> .... To detect when a duplicate element occurs, a temporary data structure (like a HashSet or a boolean array) is used for each starting index k. The length of the current sequence is tracked, and the maximum length found across all starting indices is returned.
Algorithm
- Initialize
maxLengthto 0. - Iterate through each index
ifrom0ton-1as a potential starting point. - For each
i, create a newHashSetto keep track of the numbers encountered in the current sequence to detect duplicates. - Start a traversal from
j = i. - In a loop, as long as the value
nums[j]has not been seen before in the current sequence:- Add
nums[j]to theHashSet. - Increment a local
count. - Move to the next element by updating
j = nums[j].
- Add
- Once a duplicate is found, the loop for the current sequence terminates.
- Update
maxLength = max(maxLength, count). - After checking all starting indices, return
maxLength.
Walkthrough
The most straightforward way to solve the problem is to follow the problem description directly. We can iterate through each element of the array and treat it as a starting point of a sequence. For each starting point i, we follow the chain nums[i], nums[nums[i]], and so on, keeping track of the elements we've seen in this specific sequence using a HashSet. We continue until we encounter an element that's already in our set. The size of the set at that point gives us the length of the sequence starting at i. We do this for all possible starting points and keep track of the maximum length found.
import java.util.HashSet;import java.util.Set; class Solution { public int arrayNesting(int[] nums) { int maxLength = 0; for (int i = 0; i < nums.length; i++) { Set<Integer> visitedInSequence = new HashSet<>(); int count = 0; int j = i; // The sequence stops right before a duplicate element occurs. // The value nums[j] is the element to be added to the set. while (!visitedInSequence.contains(nums[j])) { visitedInSequence.add(nums[j]); count++; j = nums[j]; } maxLength = Math.max(maxLength, count); } return maxLength; }}Complexity
Time
O(n^2). The outer loop runs `n` times. In the worst-case scenario (a single cycle of length `n`), the inner `while` loop also runs up to `n` times for each starting index `i`.
Space
O(n). For each iteration of the outer loop, a `HashSet` is created. In the worst-case scenario of a single large cycle, this set can store up to `n` elements.
Trade-offs
Pros
Simple to understand and implement as it directly follows the problem statement.
Cons
Highly inefficient due to redundant computations. The same cycle is traversed and its length is calculated for every element within that cycle.
High space complexity in the worst case.
This approach improves upon the brute-force method by recognizing that all elements in a single cycle will produce the same length. Therefore, once we calculate the length of a cycle starting from one of its elements, we don't need to recalculate it for any other element in that same cycle. We use a global boolean visited array to keep track of all indices that have already been visited as part of any cycle.
Algorithm
- Initialize
maxLengthto 0. - Create a boolean array
visitedof sizenand initialize all its elements tofalse. - Loop for
ifrom0ton-1:- If
visited[i]isfalse:- This means we've found a new, unvisited cycle.
- Initialize
count = 0andstart = i. - Start an inner loop that continues as long as
visited[start]isfalse.- Mark the current element as visited:
visited[start] = true. - Move to the next element in the cycle:
start = nums[start]. - Increment
count.
- Mark the current element as visited:
- After the cycle is fully traversed, update
maxLength = max(maxLength, count).
- If
- Return
maxLength.
Walkthrough
The key observation is that the input array represents a permutation, which can be decomposed into disjoint cycles. Any element within a cycle will traverse the entire cycle and yield the same length. The brute-force approach is inefficient because it recalculates this length for every element in the cycle. To optimize, we can use a visited array. When we start a traversal from an index i, we traverse its entire cycle, counting the elements. Crucially, we mark every index we visit in the visited array. In subsequent iterations of our main loop, if we encounter an index that is already marked as visited, we know its cycle length has already been accounted for, and we can skip it. This ensures each element in the nums array is visited exactly once.
class Solution { public int arrayNesting(int[] nums) { int n = nums.length; boolean[] visited = new boolean[n]; int maxLength = 0; for (int i = 0; i < n; i++) { if (!visited[i]) { int start = i; int count = 0; while (!visited[start]) { visited[start] = true; start = nums[start]; count++; } maxLength = Math.max(maxLength, count); } } return maxLength; }}Complexity
Time
O(n). Each element of the `nums` array is visited exactly once. The outer loop iterates `n` times, but the inner `while` loop's total executions across all outer loop iterations is `n`, because each element `i` is processed only when `visited[i]` is `false`.
Space
O(n). We use an additional boolean array `visited` of size `n` to store the visited status of each index.
Trade-offs
Pros
Efficient time complexity as it avoids redundant calculations.
Each element is processed only once.
Cons
Requires extra space proportional to the input size.
This is the most space-efficient approach. Instead of using an auxiliary visited array, it modifies the input array nums itself to mark visited elements. Since all original values in nums are within the range [0, n-1], we can use a special value that falls outside this range (e.g., n or -1) to signify that an element at a particular index has been visited. This eliminates the need for extra space.
Algorithm
- Initialize
maxLengthto 0. - Let
n = nums.length. - Loop for
ifrom0ton-1:- Choose a special marker value that is outside the valid range of indices, for example,
n. - If the value at
nums[i]has not been marked as visited (i.e.,nums[i] != n):- Start traversing a new cycle from
start = i. - Initialize
count = 0. - Start an inner loop that continues as long as
nums[start]is not the visited marker.- Store the next index:
nextIndex = nums[start]. - Mark the current index as visited by setting
nums[start] = n. - Move to the next index:
start = nextIndex. - Increment
count.
- Store the next index:
- Update
maxLength = max(maxLength, count).
- Start traversing a new cycle from
- Choose a special marker value that is outside the valid range of indices, for example,
- Return
maxLength.
Walkthrough
To achieve O(1) space complexity, we can avoid the extra visited array by using the input array nums itself for marking. The problem guarantees that 0 <= nums[i] < n. This means we can use a value outside this range, like n or Integer.MAX_VALUE, as a sentinel to mark an index as visited. The logic remains similar to the previous approach: we iterate through each index, and if it hasn't been visited, we start a traversal. During the traversal of a cycle, we overwrite the value at each visited index with our sentinel value. This way, we mark the node as visited and also retrieve the next node in the chain before the value is destroyed.
class Solution { public int arrayNesting(int[] nums) { int maxLength = 0; int n = nums.length; for (int i = 0; i < n; i++) { // Use 'n' as a visited marker since all original values are < n if (nums[i] != n) { int start = i; int count = 0; while (nums[start] != n) { int temp = start; start = nums[start]; nums[temp] = n; // Mark the element at index 'temp' as visited count++; } maxLength = Math.max(maxLength, count); } } return maxLength; }}Complexity
Time
O(n). Similar to the previous approach, each element is visited and processed exactly once.
Space
O(1). No extra space proportional to the input size is used. We only use a few variables for iteration and counting.
Trade-offs
Pros
Optimal time and space complexity.
No extra space is required, making it very memory-efficient.
Cons
Modifies the input array. If the caller requires the original array to be preserved, a copy must be made first, which would negate the space savings.
Solutions
Solution
class Solution { public int arrayNesting ( int [] nums ) { int ans = 0 , n = nums . length ; for ( int i = 0 ; i < n ; ++ i ) { int cnt = 0 ; int j = i ; while ( nums [ j ] < n ) { int k = nums [ j ]; nums [ j ] = n ; j = k ; ++ cnt ; } ans = Math . max ( ans , cnt ); } return ans ; } }class Solution { public: int arrayNesting ( vector < int >& nums ) { int ans = 0 , n = nums . size (); for ( int i = 0 ; i < n ; ++ i ) { int cnt = 0 ; int j = i ; while ( nums [ j ] < n ) { int k = nums [ j ]; nums [ j ] = n ; j = k ; ++ cnt ; } ans = max ( ans , cnt ); } return ans ; } };class Solution : def arrayNesting ( self , nums : List [ int ]) -> int : ans , n = 0 , len ( nums ) for i in range ( n ): cnt = 0 while nums [ i ] != n : j = nums [ i ] nums [ i ] = n i = j cnt += 1 ans = max ( ans , cnt ) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.