[LeetCode] Array Nesting

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]]], ... } 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:

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}

Input: nums = [0,1,2]
Output: 1

Approach: This is very much a straight forward problem. Basically we will start with first element (index 0) of the array and we keep going till we get the duplicate element. That means we need to maintain a hash set to have a record of all the visited elements. We will calculate the length of every cycle and return the maximum of those lengths. That's all!

 

Implementation in C#:

    public int ArrayNesting(int[] nums) 

    {

        int length = nums?.Length ?? 0;       

        if (length == 0)

        {

            return 0;

        }

        int maxLength = 0;

        HashSet<int> visited = new HashSet<int>();

        for (int i = 0; i < length; ++i)

        {

            int count = 0;

            int j = i;

            while (visited.Add(j))

            {

                j = nums[j];

                ++count;

            }

            maxLength = Math.Max(count, maxLength);

        }

        return maxLength;

    }

Complexity: O(n)