Array Nesting
Medium · Graphs · Explanation and code example
Walk and Mark Permutation Cycles
How it works
The array is a permutation, so repeatedly using a value as the next index walks a cycle. Once a cycle is visited, it cannot give a new answer from another starting index. Mark consumed entries as -1, saving each next index before overwriting it.
Steps
- Skip already marked entries.
- Walk the cycle, storing the next index before marking the current entry.
- Track the largest number of visited entries in one walk.
Complexity
- Time: O(n).
- Space: O(1).
Things to watch for
- This mutates the input array.
- Save the next index before writing -1.
- The permutation guarantee makes visited components cycles.
Python code example
from functools import cache
class Solution:
def arrayNesting(self, nums: list[int]) -> int:
ans = 0
for num in nums:
if num == -1:
continue
index = num
count = 0
while nums[index] != -1:
cache = index
index = nums[index]
nums[cache] = -1
count += 1
ans = max(ans, count)
return ans
C++ code example
class Solution {
public:
int arrayNesting(vector<int>& nums) {
int ans = 0;
for (const int num : nums) {
if (num == -1)
continue;
int index = num;
int count = 0;
while (nums[index] != -1) {
const int cache = index;
index = nums[index];
nums[cache] = -1;
++count;
}
ans = max(ans, count);
}
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.