Java

  • /**
    
     A zero-indexed array A consisting of N different integers is given. The array contains all integers in the range [0, N - 1].
    
     Sets S[K] for 0 <= K < N are defined as follows:
    
     S[K] = { A[K], A[A[K]], A[A[A[K]]], ... }.
    
     Sets S[K] are finite for each K and should NOT contain duplicates.
    
     Write a function that given an array A consisting of N integers, return the size of the largest set S[K] for this array.
    
     Example 1:
     Input: A = [5,4,0,3,1,6,2]
     Output: 4
     Explanation:
     A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
    
     One of the longest S[K]:
     S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}
     Note:
     N is an integer within the range [1, 20,000].
     The elements of A are all distinct.
     Each element of array A is an integer within the range [0, N-1].
    
     reference: https://leetcode.com/articles/array-nesting/
     */
    public class Array_Nesting {
    
    
        public class Solution_skip_visited {
            public int arrayNesting(int[] nums) {
                boolean[] visited = new boolean[nums.length];
                int res = 0;
                for (int i = 0; i < nums.length; i++) {
    
                    // @note: if visited, then the count here must be less than previous visit
                    if (!visited[i]) {
                        int start = nums[i], count = 0;
                        do {
                            start = nums[start];
                            count++;
                            visited[start] = true;
                        }
                        while (start != nums[i]);
                        res = Math.max(res, count);
                    }
                }
                return res;
            }
        }
    
    
        public class Solution_brute_force {
            public int arrayNesting(int[] nums) {
                int res = 0;
                for (int i = 0; i < nums.length; i++) {
                    int start = nums[i], count = 0;
                    do {
                        start = nums[start];
                        count++;
                    }
                    while (start != nums[i]); // if not the initial start number, then continue
                    res = Math.max(res, count);
    
                }
                return res;
            }
        }
    
    }
    
  • // OJ: https://leetcode.com/problems/array-nesting/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        int arrayNesting(vector<int>& A) {
            int ans = 0;
            for (int i = 0; i < A.size(); ++i) {
                if (A[i] == -1) continue;
                int cnt = 0, j = i;
                while (A[j] != -1) {
                    int k = j;
                    j = A[j];
                    A[k] = -1;
                    ++cnt;
                }
                ans = max(ans, cnt);
            }
            return ans;
        }
    };
    
  • class Solution(object):
      def arrayNesting(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        cache = [0] * len(nums)
        ans = 0
        for i, start in enumerate(nums):
          if cache[i]:
            continue
          p = start
          length = 1
          while nums[p] != start:
            cache[nums[p]] = 1
            p = nums[p]
            length += 1
          ans = max(ans, length)
        return ans
    
    

Java

  • class Solution {
        public int arrayNesting(int[] nums) {
            int length = nums.length;
            boolean[] visited = new boolean[length];
            int maxLength = 0;
            for (int i = 0; i < length; i++) {
                if (visited[i])
                    continue;
                int curLength = 0;
                int index = i;
                while (!visited[index]) {
                    int num = nums[index];
                    visited[index] = true;
                    index = num;
                    curLength++;
                }
                maxLength = Math.max(maxLength, curLength);
            }
            return maxLength;
        }
    }
    
  • // OJ: https://leetcode.com/problems/array-nesting/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        int arrayNesting(vector<int>& A) {
            int ans = 0;
            for (int i = 0; i < A.size(); ++i) {
                if (A[i] == -1) continue;
                int cnt = 0, j = i;
                while (A[j] != -1) {
                    int k = j;
                    j = A[j];
                    A[k] = -1;
                    ++cnt;
                }
                ans = max(ans, cnt);
            }
            return ans;
        }
    };
    
  • class Solution(object):
      def arrayNesting(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        cache = [0] * len(nums)
        ans = 0
        for i, start in enumerate(nums):
          if cache[i]:
            continue
          p = start
          length = 1
          while nums[p] != start:
            cache[nums[p]] = 1
            p = nums[p]
            length += 1
          ans = max(ans, length)
        return ans
    
    

All Problems

All Solutions