MediumNo. 0565

Array Nesting — LeetCode 565 Python Solution

Topics
Depth-First Search, Array
Reading time
3 min

The problem

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]]], ...

Example

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.

Python solution

PythonSolution
class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        n = len(nums)
        vis = [False] * n
        res = 0
        for i in range(n):
            if vis[i]:
                continue
            cur, m = nums[i], 1
            vis[cur] = True
            while nums[cur] != nums[i]:
                cur = nums[cur]
                m += 1
                vis[cur] = True
            res = max(res, m)
        return res

Complexity

Time
O(V+E)
Space · auxiliary
O(V)

Pattern: Depth-First Search

Follow one path to its end before trying the next — the default way to explore a graph. LeetCode 565. Array Nesting is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Depth-First Search.

The depth-first search guide has the Python template for the pattern and the 366 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0130Surrounded RegionsMedium
0200Number of IslandsMedium
0417Pacific Atlantic Water FlowMedium
0419Battleships in a BoardMedium
0463Island PerimeterEasy
0529MinesweeperMedium

Frequently asked questions

How hard is LeetCode 565. Array Nesting?

LeetCode 565. Array Nesting is rated Medium on LeetCode.

What is the time complexity of LeetCode 565. Array Nesting?

The Python solution on this page runs in O(V+E).

What is the space complexity of LeetCode 565. Array Nesting?

The Python solution on this page uses O(V) auxiliary space.

What topics does LeetCode 565. Array Nesting cover?

LeetCode 565. Array Nesting is tagged Depth-First Search and Array on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.