FilesExpand file tree

 master

/

array-nesting.py

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

46 lines (43 loc) · 1.3 KB

 master

/

array-nesting.py

Top

File metadata and controls

• Code
• Blame

46 lines (43 loc) · 1.3 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

# Time: O(n)

# Space: O(1)

# A zero-indexed array A consisting of N different integers is given.

# The array contains all integers in the range [0, N - 1].

#

# Sets S[K] for 0 <= K < N are defined as follows:

#

# S[K] = { A[K], A[A[K]], A[A[A[K]]], ... }.

#

# Sets S[K] are finite for each K and should NOT contain duplicates.

#

# Write a function that given an array A consisting of N integers,

# return the size of the largest set S[K] for this array.

#

# Example 1:

# Input: A = [5,4,0,3,1,6,2]

# Output: 4

# Explanation:

# A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.

#

# One of the longest S[K]:

# S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

# Note:

# N is an integer within the range [1, 20,000].

# The elements of A are all distinct.

# Each element of array A is an integer within the range [0, N-1].

class Solution(object):

def arrayNesting(self, nums):

"""

:type nums: List[int]

:rtype: int

"""

result = 0

for num in nums:

if num != None:

start, count = num, 0

while nums[start] != None:

temp = start

start = nums[start]

nums[temp] = None

count += 1

result = max(result, count)

return result