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

565 - Array Nesting

All Problems

All Solutions