We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Array Nesting

Number: 565

Difficulty: Medium

Paid? No

Companies: Apple

Problem Description

Given an array of unique integers where each element is in the range [0, n-1] (i.e., a permutation), we need to form sets s[k] starting at index k such that s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ...} until a duplicate appears. The task is to determine the maximum size among all such sets.

Key Insights

  • The array represents a permutation, which means every element is unique and the chains formed will eventually loop.
  • Once an element is visited in any chain, it does not need to be processed again, which helps avoid redundant work.
  • The problem can be solved using a simple traversal (or DFS-like approach) by following the chain from each index until a previously seen index is encountered.
  • An auxiliary data structure (e.g., a boolean array) is useful to mark numbers as visited.

Space and Time Complexity

Time Complexity: O(n) - Each element is visited exactly once. Space Complexity: O(n) - For the visited tracking array.

Solution

We iterate over each index in the array. For each index that has not been visited, follow the chain defined by the array until a cycle is detected. Mark each element of the chain as visited during the traversal. This ensures that each element is processed only once, providing an efficient solution. The maximum length encountered during these traversals is the result. The approach uses a while-loop for the chain traversal, with an auxiliary boolean array to record visited elements and avoid duplicate work.

Code Solutions

# Python solution with line-by-line comments
def arrayNesting(nums):
    # n represents the length of the permutation array
    n = len(nums)
    # visited array to track elements that have been already processed
    visited = [False] * n
    # variable to store the maximum set size encountered
    max_size = 0

    # iterate through each index in nums
    for i in range(n):
        # if this index has not been visited, process its chain
        if not visited[i]:
            current = i
            count = 0
            # traverse the chain until an element is revisited
            while not visited[current]:
                visited[current] = True  # mark the element as visited
                current = nums[current]  # move to the next index in chain
                count += 1
            # update max_size if we found a larger chain
            max_size = max(max_size, count)
    return max_size

# Example usage:
nums = [5,4,0,3,1,6,2]
print(arrayNesting(nums))  # Output: 4
← Back to All Questions