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 element nums[k] of index = k.
  • The next element in s[k] should be nums[nums[k]], and then nums[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 <= 105
  • 0 <= nums[i] < nums.length
  • All the values of nums are 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);
    }
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [5,4,0,3,1,6,2]

Output

x
+
cmd
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;
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [5,4,0,3,1,6,2]

Output

x
+
cmd
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;
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [0,1,2]

Output

x
+
cmd
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())
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [0,1,2]

Output

x
+
cmd
1
Advertisements

Demonstration


Previous
#564 Leetcode Find the Closest Palindrome Tilt Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#566 Leetcode Reshape the Matrix Solution in C, C++, Java, JavaScript, Python, C# Leetcode