Java solution using DP O(n) space O(m) m is max ring size


  • 0
    P
            int max = 0;
            int mem[] = new int[nums.length];
            Arrays.fill(mem,-1);
            for(int i=0;i<nums.length;i++){
                max = Math.max(helper(nums,i,mem),max);
            }
            return max;
        }
        
        public int helper(int[] nums, int k,int mem[]){
            if(mem[k] != -1){//get count if already computed
                return mem[k];
            }
            int[] arr = new int[nums.length];
            arr[nums[k]] = 1;
            int i = nums[k],count = 2;
            while(!map.containsKey(nums[i])){
                map.put(nums[i],count);
                i = nums[i];
                count++;
            }
            int n = map.size();
            for(Integer key:map.keySet()){ // store the ring for all in between index
                mem[key] = n - map.get(key);
            }
            mem[k] = n;
            return mem[k];
        }```

Log in to reply
 

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