Optimization insights to avoid TLE

This is my 923rd problem solved on LC: Array Nesting. Problem is down below. Basically the author is looking for the longest sequence a[index], a[a[index]], a[a[a[index]]], and so on, without dupes. I tried an N^2, hitting TLE. The insight that did the trick was that once we have tried a sequence, for example, {a,b,c,d,e}, it is pointless to try a sequence starting with b, c, d or e since the length will be shorter than that tried for a. Barely made the pass after that. Code is down below, cheers, ACC.

Array Nesting - LeetCode

565. Array Nesting

Medium

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.

public int ArrayNesting(int[] nums)
{
    int retVal = 0;
    Hashtable indexAlreadyTried = new Hashtable();

    for (int i = 0; i < nums.Length; i++)
    {
        Hashtable seen = new Hashtable();
        int last = nums[i];
        if (!indexAlreadyTried.ContainsKey(last))
        {
            seen.Add(last, true);
            indexAlreadyTried.Add(last, true);
            for (; ; )
            {
                last = nums[last];
                if (!indexAlreadyTried.ContainsKey(last)) indexAlreadyTried.Add(last, true);
                if (seen.ContainsKey(last)) break;
                seen.Add(last, true);
            }

            retVal = Math.Max(retVal, seen.Count);
            if (retVal == nums.Length) break;
        }
    }

    return retVal;
}