Array Nesting [Medium] — Cycle Length Tracking
Sanjeev SharmaAdvertisement
Problem Statement
nums is a permutation of [0..n-1]. Starting from index k, S(k) = {nums[k], nums[nums[k]], ...}. Find the maximum length of S(k).
Input: [5,4,0,3,1,6,2] → Output: 4 (S[0]={5,6,2,0})
Intuition
Each element belongs to exactly one cycle. DFS/follow-the-chain from each unvisited node, marking visited to avoid re-processing.
Solutions
C++
int arrayNesting(vector<int>& nums) {
int ans=0;
for(int i=0;i<nums.size();i++){
if(nums[i]==-1) continue;
int len=0,j=i;
while(nums[j]!=-1){int next=nums[j];nums[j]=-1;j=next;len++;}
ans=max(ans,len);
}
return ans;
}
Python
def arrayNesting(nums: list[int]) -> int:
ans = 0
for i in range(len(nums)):
if nums[i] == -1:
continue
length, j = 0, i
while nums[j] != -1:
nxt = nums[j]
nums[j] = -1
j = nxt
length += 1
ans = max(ans, length)
return ans
Complexity
- Time: O(n) — each element visited once
- Space: O(1)
Advertisement
