Array Nesting

medium array dfs

Problem

Given a permutation nums of 0..n-1, define S(i) = {nums[i], nums[nums[i]], …}. Return max |S(i)|.

Inputnums = [5,4,0,3,1,6,2]

Output4

Indices form disjoint cycles; the answer is the longest cycle.

nums (permutation of 0..n-1)

def array_nesting(nums):
    best = 0
    seen = [False] * len(nums)
    for i in range(len(nums)):
        if seen[i]: continue
        j = i; cnt = 0
        while not seen[j]:
            seen[j] = True
            j = nums[j]; cnt += 1
        best = max(best, cnt)
    return best

function arrayNesting(nums) {
  const seen = new Array(nums.length).fill(false);
  let best = 0;
  for (let i = 0; i < nums.length; i++) {
    if (seen[i]) continue;
    let j = i, cnt = 0;
    while (!seen[j]) { seen[j] = true; j = nums[j]; cnt++; }
    if (cnt > best) best = cnt;
  }
  return best;
}

class Solution {
    public int arrayNesting(int[] nums) {
        boolean[] seen = new boolean[nums.length];
        int best = 0;
        for (int i = 0; i < nums.length; i++) {
            if (seen[i]) continue;
            int j = i, cnt = 0;
            while (!seen[j]) { seen[j] = true; j = nums[j]; cnt++; }
            best = Math.max(best, cnt);
        }
        return best;
    }
}

int arrayNesting(vector& nums) {
    vector seen(nums.size(), false);
    int best = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        if (seen[i]) continue;
        int j = i, cnt = 0;
        while (!seen[j]) { seen[j] = true; j = nums[j]; cnt++; }
        best = max(best, cnt);
    }
    return best;
}

Explanation

Because nums is a permutation of 0..n-1, following i → nums[i] → nums[nums[i]] → ... always loops back to where you started. The whole array breaks neatly into separate cycles, and the answer is simply the length of the longest one.

The clever part is that we never need to re-explore. Once we walk a cycle and mark its indices as seen, any later index that is already seen belongs to a cycle we have measured, so we continue past it. This is why the whole thing runs in one linear pass.

For each fresh starting index, we follow the chain with a pointer j = nums[j], counting steps in cnt and marking each spot until we hit a node we have already visited. We then update best with the larger of itself and cnt.

Example: nums = [5, 4, 0, 3, 1, 6, 2]. Starting at index 0: 0 → 5 → 6 → 2 → 0, a cycle of length 4. The remaining indices form shorter cycles, so the answer is 4.

Time: O(n) Space: O(n)