Array Nesting Leetcode Solution

Problem Statement

Array Nesting Leetcode Solution – 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}

Approach

The given condition that the index domain is the same as the value domain is frequently encountered in Leetcode problems. When we have this condition, I tend to think of using a technique I call in place flag. Instead of using an extra visited array, we can just mutate the input array to reflect the flag information we want.

Brute Force Approach

Here, the brute force way to do this problem is to run a while loop and increment the count until we found an element that is previously seen, for each index in the array, so the run time complexity for this approach is O(n^2). This will not pass the cases, we need to think of a more optimal solution.

Optimal Approach

When we write the brute force solution we notice that many elements are visited many times, so the idea is to keep a visited array, and run a while loop, in which we increment the count and mark that element visited until we get an element which is already visited. This while loop is run for only those elements which are unvisited.

This little change makes the time complexity O(n).

Code

C++ Code For Array Nesting

class Solution {
public:
    int arrayNesting(vector<int>& nums) {
        int n = nums.size();
        
        vector<int> vis(n,0);
        //visited array
        
        int mx = 0;
        //variable to store maximum size of set.
        
        for(int i=0;i<n;i++)
        {
            if(vis[nums[i]]==0)
            {
                // if element is not visited before.
                int str = nums[i];
                int cnt = 0;
                do{
                    cnt++;
                    vis[str] = 1;
                    str = nums[str];
                    //all the nodes in the cycle becomes visited
                }
                while(vis[str]!=1);
                
                mx = max(mx,cnt);
            }
        }
        
        return mx;
    }
};

Java Code For Array Nesting

class Solution {
    public int arrayNesting(int[] nums) {
        int n = nums.length;
        
        int[] vis = new int[n];
        //visited array
        
        int mx = 0;
        //variable to store maximum size of set.
        
        for(int i=0;i<n;i++)
        {
            if(vis[nums[i]]==0)
            {
                // if element is not visited before.
                int str = nums[i];
                int cnt = 0;
                do{
                    cnt++;
                    vis[str] = 1;
                    str = nums[str];
                    //all the nodes in the cycle becomes visited
                }
                while(vis[str]!=1);
                
                mx = Math.max(mx,cnt);
            }
        }
        
        return mx;
    }
}

Complexity Analysis For Array Nesting Leetcode Solution

Time complexity

The time complexity for this approach is O(n), as we are only running simulations on those elements which are not visited since there are n elements so the time complexity is O(n).

Space Complexity

The space complexity for this approach is O(n), used by the visited array of size n.