DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

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:

class Solution:
    def DFS(self, nums, i, visited):
        visited.add(i)
        if nums[i] not in visited:
            return self.DFS(nums, nums[i], visited)
        else:
            return (i, visited)

    def arrayNesting(self, nums: List[int]) -> int:
        n = len(nums)
        mlen = 0
        visited = set()
        for i in range(n):
            if i not in visited:
                start, l = self.DFS(nums, i, set())
                end, l = self.DFS(nums, start, set())
                visited.update(l)
                mlen = max(mlen, len(l))
        return mlen
Enter fullscreen mode Exit fullscreen mode

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay