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^50 <= nums[i] < nums.lengthAll the values ofnumsare distinct.
Hints for Array Nesting
Hint 1
Draw an arrow from each index
itonums[i]. Becausenumsis a permutation, what shape do the arrows form?Hint 2
Every index lies on exactly one cycle, and
s[k]is precisely the cycle that containsk.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
- Keep a visited flag per index.
- For each unvisited index, follow
j = nums[j]until you reach a visited index, marking and counting as you go. - 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 bestJava
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)