Array Nesting

Medium
1124.

Array Nesting

Array Nesting is a medium coding problem on arrays and depth-first search, asked in Amazon and Apple interviews.

nums has length n and is a permutation of the integers 0 to n - 1, so every value is also a valid index.

For a starting index k, build the set s[k] by following the array as a chain of pointers: take nums[k], then nums[nums[k]], then nums[nums[nums[k]]], and so on. Stop just before you would add a value that is already in the set.

Return the size of the largest set s[k] over all starting indices k.

Example 1

Input
nums = [2,0,1,4,3]
Output
3
Explanation
From `k = 0`: `nums[0] = 2`, `nums[2] = 1`, `nums[1] = 0`, then `nums[0] = 2` again — the set is `{2, 1, 0}`. Indices 3 and 4 only reach each other.

Example 2

Input
nums = [0,1,2]
Output
1
Explanation
Every value points to itself.

Example 3

Input
nums = [1,2,3,4,0]
Output
5

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] < nums.length
  • All the values of nums are distinct.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var arrayNesting = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Array Nesting — Solution in Python, Java & C++

Array Nesting solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Apple.

Array Nesting is a medium coding problem on arrays and depth-first search, asked in Amazon and Apple interviews.

  • Difficulty: Medium
  • Topics: Arrays, Depth-First Search
  • Asked at: Amazon, Apple
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

nums has length n and is a permutation of the integers 0 to n - 1, so every value is also a valid index.

For a starting index k, build the set s[k] by following the array as a chain of pointers: take nums[k], then nums[nums[k]], then nums[nums[nums[k]]], and so on. Stop just before you would add a value that is already in the set.

Return the size of the largest set s[k] over all starting indices k.

Example 1

Input: nums = [2,0,1,4,3]
Output: 3
Explanation: From `k = 0`: `nums[0] = 2`, `nums[2] = 1`, `nums[1] = 0`, then `nums[0] = 2` again — the set is `{2, 1, 0}`. Indices 3 and 4 only reach each other.

Example 2

Input: nums = [0,1,2]
Output: 1
Explanation: Every value points to itself.

Example 3

Input: nums = [1,2,3,4,0]
Output: 5

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] < nums.length
  • All the values of nums are distinct.

Hints for Array Nesting

  1. Hint 1

    Draw an arrow from each index i to nums[i]. Because nums is a permutation, what shape do the arrows form?

  2. Hint 2

    Every index lies on exactly one cycle, and s[k] is precisely the cycle that contains k.

  3. Hint 3

    Walk each cycle once, marking indices as visited, and keep the longest cycle length.

How to solve Array Nesting

A permutation splits into disjoint cycles, and the set built from any index is exactly the cycle through that index — so the answer is the length of the longest cycle.

Approach

  1. Keep a visited flag per index.
  2. For each unvisited index, follow j = nums[j] until you reach a visited index, marking and counting as you go.
  3. The count is that cycle's length; keep the maximum.

Why it works

Every value has exactly one predecessor and one successor in a permutation, so following the pointers from k must return to k itself — never to some earlier element of a tail. All indices on that cycle produce the same set, so measuring each cycle once and never revisiting it is enough.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Restarting the walk from every index without the shared visited array is O(n^2).
  • The visited array is global across starts: an index on an already-measured cycle cannot belong to a longer one.
  • A fixed point (nums[i] = i) is a cycle of length 1, so the answer is at least 1.

Reference solution

Python

from typing import List

def arrayNesting(nums: List[int]) -> int:
    seen = [False] * len(nums)
    best = 0
    for i in range(len(nums)):
        length = 0
        j = i
        while not seen[j]:
            seen[j] = True
            j = nums[j]
            length += 1
        best = max(best, length)
    return best

Java

public static int arrayNesting(int[] nums) {
    int n = nums.length;
    boolean[] seen = new boolean[n];
    int best = 0;
    for (int i = 0; i < n; i++) {
        int len = 0, j = i;
        while (!seen[j]) {
            seen[j] = true;
            j = nums[j];
            len++;
        }
        best = Math.max(best, len);
    }
    return best;
}

C++

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

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Depth-First Search (DFS)