565. Array Nesting

MediumDepth-First SearchArray
Leetcode Link

Problem Description

In this problem, you are given an integer array nums with a length of n, where nums is a permutation of the numbers in the range [0, n - 1]. The goal is to create a unique set s[k] for each index k in the array. The set s[k] is formed by repeatedly applying the transformation nums[i] -> nums[nums[i]] starting with nums[k]. The transformation stops when it would add a duplicate element to s[k].

In other words:

  1. Begin with an index k and the corresponding element nums[k], and add it to the set s[k].
  2. Find the next element by using the current element as the index to look up the next value in the array (nums[nums[k]]), and add that to the set.
  3. Continue the process, each time using the latest element added to the set as the new index to look up.
  4. Stop when you are about to add an element that is already in the set, because that would create a duplicate.

The task is to determine the size of the largest set s[k] that can be created by following the above rules.

Intuition

To tackle the problem, note that since nums is a permutation of the numbers in [0, n - 1], every element in nums is part of exactly one cycle. Once you visit an element in nums, all subsequent elements that would be visited by following the transformation rule are part of the same cycle, and re-visiting them would just repeat the cycle without increasing the size of any set s[k].

The strategy, therefore, is to iterate through each element of nums and trace out the cycle, marking elements as visited by setting them to a value outside the range [0, n - 1] (for instance, n). Count the number of steps it takes to complete the cycle. This count represents the size of the set s[k] formed by starting at the index k.

By doing this for each index k and keeping track of the maximum count found, we can identify the longest length of a set s[k]. The elements are marked as visited to avoid redundant computations and to ensure that once an element is a part of a set, it is not counted again for subsequent indices.

Learn more about Depth-First Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of these properties could exist for a graph but not a tree?

Solution Approach

The implemented solution follows a simple yet effective approach. It traverses through each element of the array nums, and for each element, it tracks the formation of the set s[k] by following the chain of indices as described by the transformation rule nums[i] -> nums[nums[i]].

Here is the step-by-step explanation of the process using the given code:

  1. Initialize a variable ans to store the length of the largest set s[k] and set its initial value to zero (0). Initialize n to the length of nums.
  2. Loop through each index i from 0 to n-1. The variable cnt is used to keep track of the length of the set s[k] starting at index i.
  3. Inside the loop, follow the cycle that starts at nums[i]. The while loop continues as long as the current element nums[i] has not been visited (a visited element is marked by setting it to n).
  4. Retrieve the number at the current index i (stored in j), then mark the element at i as visited by setting nums[i] to n.
  5. Set the current index i to j to move to the next number in the set.
  6. Increment the counter cnt which reflects the size of the current set s[k].
  7. Once a cycle is traced (and the while loop exits), compare the size of this set (cnt) with the previous maximum (ans) and update ans if cnt is larger.
  8. Continue with the next index, marking elements and counting the size of each set until all indices are processed.
  9. Return ans, which is the length of the longest set s[k].

Through this algorithm, all sets are explored only once, since any index that has been visited and marked will not be considered again. The code effectively avoids duplicating work by marking the visited elements. This mechanism is key to ensuring the algorithm runs efficiently and the solution's time complexity is kept at O(n), where n is the size of the input array nums.

Mathematically, you could view this as tracing cycles in a graph where nodes represent elements in the array and directed edges connect node i to node nums[i]. The objective is to find the length of the longest cycle in this graph without visiting any node more than once.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Example Walkthrough

Let's take an example array nums with the permutation of numbers [1, 2, 0, 4, 5, 3]. Here's the step-by-step walkthrough to find the size of the largest set s[k].

  1. Initialize the answer ans to 0. Since the length of nums is 6, initialize n to 6.

  2. Start the loop with index i = 0. Here, nums[0] = 1. Initialize cnt = 0 which will count the size of set s[0].

  3. Begin the transformation for set s[0]:

    • nums[0] = 1, so the next index to visit is 1 and cnt becomes 1. We mark nums[0] as visited by setting it to n.
    • Now, i = 1 and nums[1] = 2, so the next index to visit is 2 and cnt becomes 2. We mark nums[1] as visited.
    • Next, i = 2 and nums[2] = 0, but nums[0] has already been visited, so the cycle is complete, and we stop here.

  4. The size of set s[0] is 2. We compare it with ans and since 2 > 0, we update ans to 2.

  5. Move to the next index i = 1, but we have already visited nums[1], so we skip to the next one, i = 2. This index is also visited, so we move on to i = 3.

  6. For i = 3, the process is:

    • nums[3] = 4 and cnt is reset to 1. We mark nums[3] as visited.
    • Next, i = 4 and nums[4] = 5. Increment cnt to 2 and mark nums[4] as visited.
    • Then, i = 5 and nums[5] = 3. cnt is incremented to 3 and mark nums[5] as visited.
    • Finally, nums[3] is already marked as visited, so we end the cycle.

  7. The size of the set formed starting at index 3 is 3. We compare it with ans, and since 3 > 2, we update ans to 3.

  8. Continuing this process for the remaining unvisited indices (which are none in this case), we find that no other set has a size larger than 3.

  9. Having completed the cycle for each index, the largest set s[k] has size 3, so we return ans = 3.

Through the above example, we were able to find the longest cycle in the permutation graph, which represents the size of the largest set s[k]. The algorithm efficiently marks visited nodes to avoid redundant calculations, leading to an optimized solution with a linear time complexity relative to the size of the array nums.

Solution Implementation

1from typing import List  # We need to import List from typing to use it as a type hint.
2
3class Solution:
4    def arrayNesting(self, nums: List[int]) -> int:
5        # Initialize the max size of the nesting to 0.
6        max_nesting_size = 0  
7        # Get the length of the input list.
8        num_elements = len(nums)
9      
10        # Iterate through each element in the list.
11        for i in range(num_elements):
12            # Initialize count for the current set.
13            current_set_size = 0  
14            # Continue traversing the set until we find an element that is marked as visited.
15            while nums[i] != num_elements:
16                # Fetch the next index from the current element.
17                next_index = nums[i]
18                # Mark the current element as visited by setting it to num_elements.
19                nums[i] = num_elements  
20                # Move to the next index.
21                i = next_index
22                # Increment the size count for the current set.
23                current_set_size += 1
24            # Update the maximum nesting size if the current set size is larger.
25            max_nesting_size = max(max_nesting_size, current_set_size)
26       
27        # Return the maximum size of nesting found.
28        return max_nesting_size
29
1class Solution {
2    public int arrayNesting(int[] nums) {
3        int maxNestSize = 0; // Variable to keep the size of the largest nest
4        int arrayLength = nums.length; // Get the length of the array
5
6        for (int start = 0; start < arrayLength; ++start) { // Loop through each element in the array
7            int size = 0; // Initialize size for the current nest
8            int currentIndex = start; // Starting index for the current nest
9
10            // Iterate through the nest starting at currentIndex until a visited element is found
11            while (nums[currentIndex] < arrayLength) { // Visited elements are marked with value equal or greater than arrayLength
12                int nextIndex = nums[currentIndex]; // Get the next index in the nest
13                nums[currentIndex] = arrayLength; // Mark the current index as visited
14                currentIndex = nextIndex; // Move to the next index
15                ++size; // Increase the size of the current nest
16            }
17
18            maxNestSize = Math.max(maxNestSize, size); // Update the size of the largest nest found so far
19        }
20
21        return maxNestSize; // Return the size of the largest nest
22    }
23}
24
1class Solution {
2public:
3    int arrayNesting(vector<int>& nums) {
4        int maxNestSize = 0;                   // This will hold the maximum size of the nest
5        int numElements = nums.size();         // Get the number of elements in the array
6
7        // Iterate through each element in the array
8        for (int i = 0; i < numElements; ++i) {
9            int nestSize = 0;                  // Initialize the size for the current nest
10            int currentIndex = i;              // Start nesting from the current index
11
12            // Loop to find the nest size starting from the current index
13            while (nums[currentIndex] < numElements) {
14                int tempIndex = nums[currentIndex]; // Store next index from the current element's value
15                nums[currentIndex] = numElements;   // Mark the current element as visited
16                currentIndex = tempIndex;           // Move to the next index in the nest
17                ++nestSize;                         // Increment the nest size
18            }
19
20            // Update maxNestSize if the current nest is bigger
21            maxNestSize = max(maxNestSize, nestSize);
22        }
23
24        return maxNestSize;                  // Return the largest nest size found
25    }
26};
27
1function arrayNesting(nums: number[]): number {
2    let maxNestSize: number = 0;  // This will hold the maximum size of the nest
3    let numElements: number = nums.length;  // Get the number of elements in the array
4
5    // Iterate through each element in the array
6    for (let i = 0; i < numElements; ++i) {
7        let nestSize: number = 0;  // Initialize the size for the current nest
8        let currentIndex: number = i;  // Start nesting from the current index
9
10        // Loop to find the nest size starting from the current index
11        while (nums[currentIndex] < numElements) {
12            let tempIndex: number = nums[currentIndex]; // Store the next index from the current element's value
13            nums[currentIndex] = numElements;  // Mark the current element as visited
14            currentIndex = tempIndex;  // Move to the next index in the nest
15            nestSize++;  // Increment the nest size
16        }
17
18        // Update maxNestSize if the current nest is larger
19        maxNestSize = Math.max(maxNestSize, nestSize);
20    }
21
22    return maxNestSize;  // Return the largest nest size found
23}
24
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a min heap?

Time and Space Complexity

Time Complexity

The time complexity of the code is O(n). This is because each element is visited only once. The while loop marks visited elements by setting their value to n, ensuring that each element can become the start of a set at most once. Since the input array has n elements, and we are doing constant time operations per element, traversing and marking all elements results in a linear time complexity relative to the size of the input array.

Space Complexity

The space complexity of the code is O(1) (ignoring the input size). This is due to the fact that no additional space proportional to the input size is used. The variables ans, n, cnt, i, and j only use a constant amount of extra space.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Recommended Readings

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫