leetcode/problems/src/array/ArrayNesting.java at master · KindleBooks66/leetcode · GitHub

History

56 lines (51 loc) · 1.53 KB

Raw

package array;

import java.util.*;

/**

* Created by gouthamvidyapradhan on 09/10/2019 A zero-indexed array A of length N contains all

* integers from 0 to N-1. Find and return the longest length of set S, where S[i] = {A[i], A[A[i]],

* A[A[A[i]]], ... } subjected to the rule below.

* Suppose the first element in S starts with the selection of element A[i] of index = i, the

* next element in S should be A[A[i]], and then A[A[A[i]]]… By that analogy, we stop adding right

* before a duplicate element occurs in S.

* 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 A is an integer within the range [0, N-1].

public class ArrayNesting {

public static void main(String[] args) {

int[] A = {5, 4, 0, 3, 1, 6, 2};

System.out.println(new ArrayNesting().arrayNesting(A));

}

Set<Integer> done;

int count;

public int arrayNesting(int[] nums) {

done = new HashSet<>();

int max = 0;

for (int i = 0; i < nums.length; i++) {

if (!done.contains(i)) {

count = 0;

dfs(i, nums);

max = Math.max(max, count);

}

return max;

}

private void dfs(int i, int[] nums) {

done.add(i);

count++;

int n = nums[i];

if (!done.contains(n)) {

dfs(n, nums);

}

leetcode/problems/src/array/ArrayNesting.java at master · KindleBooks66/leetcode · GitHub

Uh oh!

Expand file tree

Breadcrumbs

ArrayNesting.java

Latest commit

History

Breadcrumbs

ArrayNesting.java

File metadata and controls