Scale Engineer

Array Nesting

Med
#0548Time: 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.
Algorithms
Depth-First Search
Data structures
Array

Prompt

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 element nums[k] of index = k.
  • The next element in s[k] should be nums[nums[k]], and then nums[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 <= 105
  • 0 <= nums[i] < nums.length
  • All the values of nums are 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 maxLength to 0.
  • Iterate through each index i from 0 to n-1 as a potential starting point.
  • For each i, create a new HashSet to 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 the HashSet.
    • Increment a local count.
    • Move to the next element by updating j = nums[j].
  • 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.

Solutions

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 ; } }

Video 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.

← Previous

Previous problem

Next →

Next problem