MediumNo. 0565
Array Nesting — LeetCode 565 Python Solution
- Pattern
- Depth-First Search
- Topics
- Depth-First Search, Array
- Reading time
- 3 min
- Source
- leetcode.com
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
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 resComplexity
- 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
| No. | Problem | Difficulty |
|---|---|---|
| 0130 | Surrounded Regions | Medium |
| 0200 | Number of Islands | Medium |
| 0417 | Pacific Atlantic Water Flow | Medium |
| 0419 | Battleships in a Board | Medium |
| 0463 | Island Perimeter | Easy |
| 0529 | Minesweeper | Medium |
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.