[leetcode #565] Array Nesting

Problem

You are given an integer array nums of length n where nums is a permutation of the numbers in the range [0, n - 1].

You should build a set s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ... } subjected to the following rule:

・ The first element in s[k] starts with the selection of the element nums[k] of index = k.
・ The next element in s[k] should be nums[nums[k]], and then nums[nums[nums[k]]], and so on.
・ We stop adding right before a duplicate element occurs in s[k].

Return the longest length of a set s[k].

Example 1:

Input: nums = [5,4,0,3,1,6,2]
Output: 4
Explanation: 
nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.
One of the longest sets s[k]:
s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}

Example 2:

Input: nums = [0,1,2]
Output: 1

Constraints:

・ 1 <= nums.length <= 10⁵
・ 0 <= nums[i] < nums.length
・ All the values of nums are unique.

Idea

nums의 최대 길이가 10⁵나 되므로 brute force인 O(n²)으로 풀면 Time Limit Exceeded로 실패하게 된다. 이를 해결하기 위해 한 번 탐색한 index는 다시 탐색하지 않도록 visited라는 boolean array를 만들었다. set을 만들기 위해 nums[i] 값을 다음 루프를 돌 때 i로 활용했으며, 이미 한 번 방문했던 index면 루프를 빠져나오게 했다. 루프를 빠져나올 때 세었던 count 값를 리턴하여 현재 max값과 비교한뒤, max값보다 크면 max값을 바꿔준다. array의 모든 원소를 다 탐색한 뒤 max를 리턴하면 된다.

알고리즘은 다음과 같다.

1. index 방문 여부를 확인하는 array를 만든다.
2. 모든 index에 대해 set을 만드는 함수를 호출한다.
3. 함수 내에서는 루프를 돌며 count값을 센다.
   a. 이미 방문한 index면 루프를 빠져나온다.
   b. 방문하지 않은 index의 경우 count값을 늘리고 방문 여부를 true로 설정한다.
   c. 다음 index를 nums[i]로 정한다.
4. 함수가 리턴한 값과 최대값을 비교하여 최대값보다 크면 최대값으로 설정한다.
5. 모든 index에 대해 set을 만든 뒤 최대값을 리턴한다.

Solution

class Solution {
    public int arrayNesting(int[] nums) {
	int n = nums.length;
	boolean[] visited = new boolean[n];

    	int cnt = 0;
        int max = 0;
        for (int i=0; i < n; i++) {
            max = Math.max(max, makeSet(nums, visited, i));
        }

        return max;
    }

    private int makeSet(int[] nums, boolean[] visited, int i) {
        int cnt = 0;

        while (true) {
            if (visited[i])
                break;
            cnt++;
            visited[i] = true;
            i = nums[i];
        }

        return cnt;
    }
}

Reference

https://leetcode.com/problems/array-nesting/