565. Array Nesting LeetCode Solution

In this guide, you will get 565. Array Nesting LeetCode Solution with the best time and space complexity. The solution to Array Nesting problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Array Nesting solution in C++
Array Nesting solution in Java
Array Nesting solution in Python
Additional Resources

565. Array Nesting LeetCode Solution image

Problem Statement of 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.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

565. Array Nesting LeetCode Solution in C++

class Solution {
 public:
  int arrayNesting(vector<int>& nums) {
    int ans = 0;

    for (const int num : nums) {
      if (num == -1)
        continue;
      int index = num;
      int count = 0;
      while (nums[index] != -1) {
        const int cache = index;
        index = nums[index];
        nums[cache] = -1;
        ++count;
      }
      ans = max(ans, count);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

565. Array Nesting LeetCode Solution in Java

class Solution {
  public int arrayNesting(int[] nums) {
    int ans = 0;

    for (final int num : nums) {
      if (num == -1)
        continue;
      int index = num;
      int count = 0;
      while (nums[index] != -1) {
        final int cache = index;
        index = nums[index];
        nums[cache] = -1;
        ++count;
      }
      ans = Math.max(ans, count);
    }

    return ans;
  }
}
// code provided by PROGIEZ

565. Array Nesting LeetCode Solution in Python

class Solution:
  def arrayNesting(self, nums: list[int]) -> int:
    ans = 0

    for num in nums:
      if num == -1:
        continue
      index = num
      count = 0
      while nums[index] != -1:
        cache = index
        index = nums[index]
        nums[cache] = -1
        count += 1
      ans = max(ans, count)

    return ans
 # code by PROGIEZ