My simple solution - 0(n) DFS with and without 0(n) extra space


  • 0
    M

    With extra space without changing the original array

        public int arrayNesting(int[] nums) {
            if(nums.length==0)
                return 0;
            if(nums.length==1)
                return 1;     
            
            boolean[] visited = new boolean[nums.length];
            
            int curr=0,max=0;        
            
            for(int i=0;i<nums.length;i++)
            {        
                if(visited[i]) continue;
                while(!visited[i])
                {
                    visited[i]=true;
                    curr++;
                    i=nums[i];
                }
                max=Math.max(max,curr);
                curr=0;
            }
            return max;
    
        }
    

    Without extra space,but changing the original array

        public int arrayNesting(int[] nums) {
            if(nums.length==0)
                return 0;
            if(nums.length==1)
                return 1;     
            int curr=0,max=0;        
            
            for(int i=0;i<nums.length;i++)
            {    
                if(nums[i]<0) continue;
                int start = i;
                while(curr==0 || start!=i)
                {                
                    curr++;
                    int val=i;
                    i=nums[i];
                    nums[val]=-1;
                }
                max=Math.max(max,curr);
                curr=0;
            }
            return max;
    
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.