Question
Given a permutation which contains numbers in the range [1, N], return the length of the largest cycle in the permutation.
A permutation cycle is a subset of a permutation whose elements trade places with one another.
Sample Testcases:
a) longestCycle([2 3 1]) returns 3, since only cycle is (1 2 3) whose length is 3
b) longestCycle([5 4 3 2 1]) returns 2, since the permutation can be decomposed into (1 5), (2 4), (3)
Solution
This is just an idea.
Now first of all, its important to understand what is a cycle in permutation.
Keeping that in mind, I take (5,4,3,2,1) as an example. First, we fetch 5, and we swap number 5 with the 5th element of the array (which is 1). After this swap, value 1 is in the 1st position, so this cycle is done, the length is 2.
We continue doing this until all numbers of value v is in the (v)th position, we should know the largest length of cycle during this process.
I did not write code, and I found very little relevant resources. If you did, please leave a comment below.