_565. Array Nesting.md

565. Array Nesting

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 02, 2024

Last updated : July 02, 2024

---

Related Topics : Array, Depth-First Search

Acceptance Rate : 56.38 %

---

Version 1

Runtime: $O(2n)\rightarrow O(n)$

Space: $O(n)$

This is due to the initial hashmap conversion. Honestly isn't that efficient but still passes and is $O(n)$

Version 2

Runtime: $O(n)$

Space: $O(n)$

Also is $O(n)$ but doesn't have an initial pass to form a HashMap. Note that it's not necessary to add the original value (or any value of an index before the current for that matter) since they only appear once and only values to the right will be checked. Thus we won't encounter it again either way.

---

Solutions

• m565 v1 O(1) space.py
• m565 v1 O(n) space.py.py

Python

m565 v1 O(1) space.py

class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        visited = set()
        maxx = 0

        for i in range(len(nums)) :
            if i in visited :
                continue

            counter = 1
            curr = nums[i]
            while curr != i :
                counter += 1
                visited.add(curr)
                curr = nums[curr]
            maxx = max(maxx, counter)

        return maxx

m565 v1 O(n) space.py.py

class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        hs = {i: nums[i] for i in range(len(nums))}

        maxx = 0
        while hs :
            curr = random.choice(list(hs.keys()))
            lenth = 0

            while curr in hs :
                lenth += 1
                temp = hs.get(curr)
                hs.pop(curr)
                curr = temp
            maxx = max(maxx, lenth)
            
        return maxx