Jobs

Interviews

Discussions

Array Nesting

Medium

Asked by:

59 views

Topics:

Arrays

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 <= 10⁵
0 <= nums[i] < nums.length
All the values of nums are unique.

Try coding it in LeetCode

Array Nesting

Medium

Asked by:

59 views

Topics:

Arrays

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 <= 10⁵
0 <= nums[i] < nums.length
All the values of nums are unique.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the input array nums? Can I assume they are non-negative?
Is the input array guaranteed to contain only integers, or could there be other data types?
Could the input array be empty or null? If so, what should I return?
Are all numbers within the array guaranteed to be within the bounds of the array's indices (i.e., between 0 and nums.length - 1)?
If there are multiple nesting cycles of different lengths, should I return the length of the longest one?

Brute Force Solution

Approach

The brute force strategy for this problem involves exploring every possible 'cycle' within the given set of numbers. We start at a number, follow its indicated link to another number, and continue until we loop back to where we started. We repeat this process for every possible starting number.

Here's how the algorithm would work step-by-step:

Pick a number from the set.
Follow the number's 'link' to another number in the set.
Continue following links until you arrive back at the original number you started with.
Count how many numbers you visited in that 'cycle'.
Record the size of that cycle.
Repeat the whole process, starting with a different number that hasn't been visited yet.
Keep doing this until you've started from every single number in the set.
Finally, find the biggest cycle size that you recorded. That's your answer.

Code Implementation

def array_nesting_brute_force(numbers):
    maximum_cycle_size = 0

    for start_index in range(len(numbers)):
        current_index = start_index
        current_cycle_size = 0
        visited_indices = set()

        # Iterate through the array following the links.

        while current_index not in visited_indices:
            visited_indices.add(current_index)
            current_index = numbers[current_index]
            current_cycle_size += 1

        # Track the largest cycle

        maximum_cycle_size = max(maximum_cycle_size, current_cycle_size)

    return maximum_cycle_size

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each of the n elements of the input array nums. For each element, it follows the chain of indices until it returns to the starting element, effectively identifying a cycle. Crucially, once an element is visited within a cycle, it's marked as visited, ensuring that the same cycle is never traversed again from a different starting point. This guarantees that each element is visited at most once, leading to a total of O(n) operations.

Space Complexity

O(1) – The brute force approach iterates through the array and calculates the cycle length for each starting index. The only extra memory used is for a few integer variables to keep track of the current position in the cycle and the maximum cycle length seen so far. No auxiliary data structures that scale with the input size N (the length of the array) are used. Therefore, the space complexity is constant, O(1).

Optimal Solution

Approach

Imagine each number as a pointer to another number. The goal is to find the longest chain you can make by following these pointers. The clever part is that once you've traced a chain, you don't need to trace it again.

Here's how the algorithm would work step-by-step:

Start at a number.
Follow the pointer to the next number in the chain.
Keep following the pointers, counting how many numbers are in the chain until you reach a number you've already seen.
Remember the length of this chain.
When you are following the pointers, if you land on a number you have already visited from some prior chain, you can skip this number and move on to the next number, because the size of that chain has already been calculated.
Move to the next number that you haven't started a chain with yet, and repeat the process.
Keep track of the longest chain you find.
The length of the longest chain is your answer.

Code Implementation

def array_nesting(nums):
    array_length = len(nums)
    longest_nesting_length = 0
    visited = [False] * array_length

    for i in range(array_length):
        if not visited[i]:
            # Start a new chain if not visited yet.
            nesting_length = 0
            current_index = i

            while not visited[current_index]:
                visited[current_index] = True
                current_index = nums[current_index]
                nesting_length += 1

            # Update the longest chain if the current one is bigger.
            longest_nesting_length = max(longest_nesting_length, nesting_length)

    return longest_nesting_length

Big(O) Analysis

Time Complexity

O(n) – The outer loop iterates through each of the n elements in the input array nums. Inside the loop, there's a while loop that follows the chain of pointers. Crucially, once a number has been visited (as part of a cycle), it's marked as visited by setting nums[current] to -1. Because of this marking, each element in nums is visited at most once across all cycles. Therefore, the total number of steps taken across all calls to the inner while loop is also bounded by n. Consequently, the overall time complexity is O(n).

Space Complexity

O(1) – The provided explanation implicitly suggests modifying the input array `nums` in-place to mark visited elements. While not explicitly stated whether this is allowed or not, the plain english explanation doesn't mention creating any auxiliary data structures like a boolean array or a hash set to keep track of visited indices. Therefore, assuming in-place modification is acceptable (or a constant amount of extra variables are used to track the longest chain), the algorithm uses a constant amount of extra space, independent of the input size N. The space used does not scale with the input array's size.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately, as no nesting is possible.
Array with one element	Return 1, as the single element forms a trivial cycle with itself.
Array where nums[i] == i for all i	Each element forms a cycle of length 1; the maximum cycle length will be 1.
Array with all elements pointing to each other (e.g., nums[0] = 1, nums[1] = 0)	Each pair of elements forms a cycle of length 2; the algorithm will find these and return 2 if the array has only these two.
Array with maximum size (n = 10^5)	Ensure the solution has O(n) time complexity and doesn't exceed memory limits, typically by using in-place modification or a visited array of size n.
Array contains a long cycle that includes almost all elements	The algorithm should efficiently traverse the long cycle without exceeding time limits.
Array contains multiple disjoint cycles of varying lengths	The algorithm must correctly identify the longest cycle amongst all disjoint cycles.
Cycles overlap, potentially leading to incorrect length calculations	Use a 'visited' array or in-place modification (e.g., marking visited elements with -1) to prevent revisiting elements within the same traversal to handle overlapping cycles correctly.

Null or empty input array

How to Handle:

Return 0 immediately, as no nesting is possible.

Array with one element

How to Handle:

Return 1, as the single element forms a trivial cycle with itself.

Array where nums[i] == i for all i

How to Handle:

Each element forms a cycle of length 1; the maximum cycle length will be 1.

Array with all elements pointing to each other (e.g., nums[0] = 1, nums[1] = 0)

How to Handle:

Each pair of elements forms a cycle of length 2; the algorithm will find these and return 2 if the array has only these two.

Array with maximum size (n = 10^5)

How to Handle:

Ensure the solution has O(n) time complexity and doesn't exceed memory limits, typically by using in-place modification or a visited array of size n.

Array contains a long cycle that includes almost all elements

How to Handle:

The algorithm should efficiently traverse the long cycle without exceeding time limits.

Array contains multiple disjoint cycles of varying lengths

How to Handle:

The algorithm must correctly identify the longest cycle amongst all disjoint cycles.

Cycles overlap, potentially leading to incorrect length calculations

How to Handle:

Use a 'visited' array or in-place modification (e.g., marking visited elements with -1) to prevent revisiting elements within the same traversal to handle overlapping cycles correctly.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the input array nums? Can I assume they are non-negative?
Is the input array guaranteed to contain only integers, or could there be other data types?
Could the input array be empty or null? If so, what should I return?
Are all numbers within the array guaranteed to be within the bounds of the array's indices (i.e., between 0 and nums.length - 1)?
If there are multiple nesting cycles of different lengths, should I return the length of the longest one?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Pick a number from the set.
Follow the number's 'link' to another number in the set.
Continue following links until you arrive back at the original number you started with.
Count how many numbers you visited in that 'cycle'.
Record the size of that cycle.
Repeat the whole process, starting with a different number that hasn't been visited yet.
Keep doing this until you've started from every single number in the set.
Finally, find the biggest cycle size that you recorded. That's your answer.

Code Implementation

def array_nesting_brute_force(numbers):
    maximum_cycle_size = 0

    for start_index in range(len(numbers)):
        current_index = start_index
        current_cycle_size = 0
        visited_indices = set()

        # Iterate through the array following the links.

        while current_index not in visited_indices:
            visited_indices.add(current_index)
            current_index = numbers[current_index]
            current_cycle_size += 1

        # Track the largest cycle

        maximum_cycle_size = max(maximum_cycle_size, current_cycle_size)

    return maximum_cycle_size

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at a number.
Follow the pointer to the next number in the chain.
Keep following the pointers, counting how many numbers are in the chain until you reach a number you've already seen.
Remember the length of this chain.
When you are following the pointers, if you land on a number you have already visited from some prior chain, you can skip this number and move on to the next number, because the size of that chain has already been calculated.
Move to the next number that you haven't started a chain with yet, and repeat the process.
Keep track of the longest chain you find.
The length of the longest chain is your answer.

Code Implementation

def array_nesting(nums):
    array_length = len(nums)
    longest_nesting_length = 0
    visited = [False] * array_length

    for i in range(array_length):
        if not visited[i]:
            # Start a new chain if not visited yet.
            nesting_length = 0
            current_index = i

            while not visited[current_index]:
                visited[current_index] = True
                current_index = nums[current_index]
                nesting_length += 1

            # Update the longest chain if the current one is bigger.
            longest_nesting_length = max(longest_nesting_length, nesting_length)

    return longest_nesting_length

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately, as no nesting is possible.
Array with one element	Return 1, as the single element forms a trivial cycle with itself.
Array where nums[i] == i for all i	Each element forms a cycle of length 1; the maximum cycle length will be 1.
Array with all elements pointing to each other (e.g., nums[0] = 1, nums[1] = 0)	Each pair of elements forms a cycle of length 2; the algorithm will find these and return 2 if the array has only these two.
Array with maximum size (n = 10^5)	Ensure the solution has O(n) time complexity and doesn't exceed memory limits, typically by using in-place modification or a visited array of size n.
Array contains a long cycle that includes almost all elements	The algorithm should efficiently traverse the long cycle without exceeding time limits.
Array contains multiple disjoint cycles of varying lengths	The algorithm must correctly identify the longest cycle amongst all disjoint cycles.
Cycles overlap, potentially leading to incorrect length calculations	Use a 'visited' array or in-place modification (e.g., marking visited elements with -1) to prevent revisiting elements within the same traversal to handle overlapping cycles correctly.

Null or empty input array

How to Handle:

Return 0 immediately, as no nesting is possible.

Array with one element

How to Handle:

Return 1, as the single element forms a trivial cycle with itself.

Array where nums[i] == i for all i

How to Handle:

Each element forms a cycle of length 1; the maximum cycle length will be 1.

Array with all elements pointing to each other (e.g., nums[0] = 1, nums[1] = 0)

How to Handle:

Each pair of elements forms a cycle of length 2; the algorithm will find these and return 2 if the array has only these two.

Array with maximum size (n = 10^5)

How to Handle:

Ensure the solution has O(n) time complexity and doesn't exceed memory limits, typically by using in-place modification or a visited array of size n.

Array contains a long cycle that includes almost all elements

How to Handle:

The algorithm should efficiently traverse the long cycle without exceeding time limits.

Array contains multiple disjoint cycles of varying lengths

How to Handle:

The algorithm must correctly identify the longest cycle amongst all disjoint cycles.

Cycles overlap, potentially leading to incorrect length calculations

How to Handle:

Use a 'visited' array or in-place modification (e.g., marking visited elements with -1) to prevent revisiting elements within the same traversal to handle overlapping cycles correctly.