Algorithm
Problem Name: 565. Array Nesting
Problem Link: https://leetcode.com/problems/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 elementnums[k]ofindex = k. - The next element in
s[k]should benums[nums[k]], and thennums[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 <= 1050 <= nums[i] < nums.length- All the values of
numsare unique.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int arrayNesting(vector<int>& nums) {
int maxDepth = 0;
for(int i = 0; i < nums.size(); i++){
if(nums[i] == -1) continue;
DFS(nums, i, 0, maxDepth);
}
return maxDepth;
}
void DFS(vector<int>& nums, int num, int depth, int& maxDepth){
if(nums[num] == -1){
maxDepth = max(maxDepth, depth);
return;
}
int next = nums[num];
nums[num] = -1;
DFS(nums, next, depth + 1, maxDepth);
}
};
Input
nums = [5,4,0,3,1,6,2]
Output
4
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int arrayNesting(int[] nums) {
int maxSize = 0;
for (int i = 0; i < nums.length; i++) {
int count = 0;
for (int k = i; nums[k] >= 0; count++) {
int numsK = nums[k];
nums[k] = -1;
k = numsK;
}
maxSize = Math.max(maxSize, count);
}
return maxSize;
}
}
Input
nums = [5,4,0,3,1,6,2]
Output
4
#3 Code Example with Javascript Programming
Code -
Javascript Programming
/**
* @param {number[]} nums
* @return {number}
*/
const arrayNesting = function(nums) {
let res = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] !== Number.MAX_SAFE_INTEGER) {
let start = nums[i],
count = 0;
while (nums[start] !== Number.MAX_SAFE_INTEGER) {
let temp = start;
start = nums[start];
count++;
nums[temp] = Number.MAX_SAFE_INTEGER;
}
res = Math.max(res, count);
}
}
return res;
};
Input
nums = [0,1,2]
Output
1
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def arrayNesting(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dic={}
for i in range(len(nums)):
if i in dic:
continue
j=i
dic[j]=1
while nums[i]!=j:
dic[j]+=1
i=nums[i]
dic[i]=1
return max(dic.values())
Input
nums = [0,1,2]
Output
1