Array Nesting - Leetcode Solution

Array Nesting is a problem on LeetCode that requires you to find the length of the longest set of consecutive integers that are contained within an array. The solution involves using a set to keep track of visited indices and iterating through the array to find all possible sets.

Here is the step-by-step solution for Array Nesting problem on LeetCode:

Step 1: Initialize a set to keep track of visited indices.

visited = set()

Step 2: Iterate through the array and initialize a variable to keep track of the maximum set size.

max_len = 0
for i in range(len(nums)):

Step 3: If the current index has not been visited, start a new set.

    if i not in visited:
        current_len = 0
        current_index = i
        current_set = set()

Step 4: While the current index has not been visited, add it to the set and increment the set size.

        while current_index not in visited:
            visited.add(current_index)
            current_set.add(current_index)
            current_len += 1

Step 5: If the current set size is greater than the maximum set size, update the maximum set size.

            if current_len > max_len:
                max_len = current_len

Step 6: Return the maximum set size.

return max_len

The full solution looks like this:

def arrayNesting(nums: List[int]) -> int:
    visited = set()
    max_len = 0
    for i in range(len(nums)):
        if i not in visited:
            current_len = 0
            current_index = i
            current_set = set()
            while current_index not in visited:
                visited.add(current_index)
                current_set.add(current_index)
                current_len += 1
                current_index = nums[current_index]
            if current_len > max_len:
                max_len = current_len
    return max_len

This solution has a time complexity of O(n) and a space complexity of O(n), where n is the length of the array.

1