Problem statement
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 element nums[k].
The next element in s[k] should be nums[nums[k]], and then nums[nums[nums[k]]], and so on.
We stop adding elements before a duplicate element occurs in s[k].
Return the length of the longest 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^5.
0 <= nums[i] < nums.length.
All the values of nums are unique.
Solution: Understanding the math behind
A permutation is a one-to-one mapping from a set of integers to itself.
The permutation on the set nums in this problem is defined by the mapping i -> nums[i]. For instance in Example 1, the permutation is defined as following:
0 -> 5,
1 -> 4,
2 -> 0,
3 -> 3,
4 -> 1,
5 -> 6,
6 -> 2.
You can always rearrange the definition of a permutation into groups of cyclic chains (factors).
0 -> 5, 5 -> 6, 6 -> 2, 2 -> 0,
1 -> 4, 4 -> 1,
3 -> 3
The set s[k] in this problem is such a chain. In mathematics, it is called a cycle; because the chain (0, 5, 6, 2) is considered the same as (5, 6, 2, 0), (6, 2, 0, 5) or (2, 0, 5, 6) in Example 1.
Assume you have used some elements of the array nums to construct some cycles. To construct another one, you should start with the unused elements.
The problem leads to finding the longest cycle of a given permutation.
Code
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int arrayNesting(vector<int>& nums) {
int maxLen(0);
vector<bool> visited(nums.size());
for (auto i : nums) {
if (visited[i]) {
continue;
}
int len(0);
while (!visited[i]) {
visited[i] = true;
i = nums[i];
len++;
}
maxLen = max(len, maxLen);
}
return maxLen;
}
int main() {
vector<int> nums = {5,4,0,3,1,6,2};
cout << arrayNesting(nums) << endl;
nums = {0,1,2};
cout << arrayNesting(nums) << endl;
nums = {0,2,1};
cout << arrayNesting(nums) << endl;
nums = {2,0,1};
cout << arrayNesting(nums) << endl;
}
Output:
4
1
2
3
Complexity
Runtime: O(N), where N = nums.length.
Extra space: much less than O(N) since vector<bool> is optimized for space efficiency.
Thanks for reading. Feel free to share your thought about my content and check out my FREE book 10 Classic Coding Challenges.
What is your approach? The problem was picked from leetcode.com. You can submit your solution in any programming language and check the performance.
