{x}
blog image

Array Nesting

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.

Solution Explanation for Array Nesting

The problem asks to find the longest chain of nested elements in an array nums where each element represents the index of the next element in the chain. The chain stops when a duplicate element is encountered.

Two approaches are presented below:

Approach 1: Depth-First Search (DFS) with Visited Array

This approach uses depth-first search to traverse each chain and marks visited elements to avoid cycles.

Algorithm:

  1. Initialization: Create a visited array to track visited elements and initialize the maximum length (res) to 0.

  2. Iteration: Iterate through the input array nums. For each index i:

    • If visited[i] is false (element not visited yet):
      • Initialize cur to nums[i] and m (chain length) to 1.
      • Mark visited[cur] as true.
      • DFS: While nums[cur] is not equal to nums[i] (avoiding cycles):
        • Update cur to nums[cur].
        • Increment m.
        • Mark visited[cur] as true.
      • Update res to the maximum of res and m.

  3. Return: Return res which holds the maximum length of a chain.

Time Complexity: O(N), where N is the length of the input array. Each element is visited at most once. Space Complexity: O(N) to store the visited array.

Approach 2: In-place Modification

This approach cleverly modifies the input array itself to track visited elements, avoiding the need for a separate visited array.

Algorithm:

  1. Initialization: Initialize ans (maximum length) to 0.

  2. Iteration: Iterate through the input array nums. For each index i:

    • If nums[i] is less than the length of nums (meaning it hasn't been marked as visited yet):
      • Initialize cnt (current chain length) to 0.
      • Initialize j to i.
      • Chain traversal: While nums[j] is less than the length of nums:
        • Store the next element in k.
        • Mark the current element as visited by setting nums[j] to the length of nums.
        • Update j to k.
        • Increment cnt.
      • Update ans to the maximum of ans and cnt.

  3. Return: Return ans.

Time Complexity: O(N). Each element is visited or modified at most once. Space Complexity: O(1). No extra space is used besides a few variables.

The second approach is generally preferred due to its slightly better space complexity. Both achieve the same time complexity. The choice depends on whether you prefer the readability of the first approach versus the slight space optimization of the second. The provided code examples demonstrate both approaches in multiple programming languages.