Array Nesting solution and explanation
Google
9 more videos on this problem
Array Nesting | Leetcode 565 | Live coding session 🔥🔥🔥🔥Coding Decoded · 10:37 · 3K views
Array nesting problem (LeetCode #565) - Inside codeInside code · 7:19 · 2K views
565. Array Nesting | LEETCODE MEDIUM | DFS | CODE EXPLAINERcode Explainer · 6:17 · 2K views
LeetCode 565 Array NestingDevendraSingh Rathore · 5:07 · 1K views
Leetcode - Array Nesting (Python)Timothy H Chang · 8:49 · 1K views
LeetCode 565. Array NestingHappy Coding · 8:58 · 1K views
Array Nesting | Maths | Depth First Search | 565 LeetCode | Day 01CodeWithSunny · 14:36 · 770 views
Array Nesting | LeetCode 565 | Theory + Python codeSai Anish Malla · 15:23 · 734 views
Array Nesting Leetcode 565 || Live Coding Sessions || Coding Culture5 Minutes Code · 8:51 · 529 views
Daily Leetcode #519: Sep 01, 2021 - 565. Array NestingProgramming Live with Larry · 19:25 · 470 views
The problem
You are given an integer array nums of length n where nums is a permutation of the numbers in the range [0, n - 1].
You should build a set s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ... } subjected to the following rule:
- The first element in
s[k]starts with the selection of the elementnums[k]ofindex = k. - The next element in
s[k]should benums[nums[k]], and thennums[nums[nums[k]]], and so on. - We stop adding right before a duplicate element occurs in
s[k].
Return the longest length of a set s[k].
Example 1:
Input: nums = [5,4,0,3,1,6,2]
Output: 4
Explanation:
nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.
One of the longest sets s[k]:
s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}
Example 2:
Input: nums = [0,1,2] Output: 1
Constraints:
1 <= nums.length <= 1050 <= nums[i] < nums.length- All the values of
numsare unique.
Approach overview
Problem Overview: You receive an integer array nums containing a permutation of values 0..n-1. Starting from index k, repeatedly jump to nums[k], then nums[nums[k]], forming a sequence until a value repeats. The task is to compute the maximum size of such a set.
The key observation: because the array is a permutation, following indices forms disjoint cycles. The size of the largest cycle equals the answer. The task becomes detecting cycle lengths efficiently without reprocessing elements.
Approach 1: Iterative Using Visited Array (O(n) time, O(n) space)
Treat the array as a directed graph where each index points to nums[i]. Each component forms a cycle. Maintain a boolean visited array so every element is processed only once. For each index i, if it hasn't been visited, repeatedly follow the chain i → nums[i] → nums[nums[i]] while marking nodes visited and counting the cycle length. Track the maximum length across all cycles.
This approach is straightforward and easy to reason about. Each index is visited at most once, giving O(n) total traversal time and O(n) auxiliary memory. It's ideal when clarity matters or when modifying the input array is not allowed. The traversal pattern resembles cycle exploration in Depth-First Search, although implemented iteratively on an array.
Approach 2: In-Place Modification without Extra Space (O(n) time, O(1) space)
The permutation constraint allows marking visited elements directly inside the array. When traversing a chain, replace visited values with a sentinel such as -1. Start from index i, repeatedly move to next = nums[i], count the length, and mark nums[i] = -1 to indicate it has been processed. Stop when the traversal reaches a marked element.
This eliminates the separate visited array and keeps memory usage constant. Each index is still processed exactly once, so runtime remains O(n). The tradeoff is mutating the input array, which may not be allowed in some environments but is perfectly acceptable in most coding interviews.
Recommended for interviews: Both approaches achieve optimal O(n) time by recognizing the permutation cycles. Start with the visited-array method because it clearly demonstrates cycle detection and safe traversal. If the interviewer asks about space optimization, transition to the in-place marking approach to reduce memory to O(1). Showing both demonstrates strong understanding of cycle traversal patterns in arrays.
Approach 1: Approach 1: Iterative Using Visited Array
In this approach, we use an auxiliary 'visited' array to keep track of the elements that have already been included in any set s[k]. For each unvisited element at index i, we keep iterating through the sequence by accessing nums[nums[i]] until we encounter an element already visited. Each time we reach an unvisited element, we mark it as visited, and increment the length of the current sequence. We keep track of the longest length among all sequences generated from each starting index.
class Solution:
def arrayNesting(self, nums):
visited = [False] * len(nums)
max_length = 0
for i in range(len(nums)):
if not visited[i]:
start, length = i, 0
while not visited[start]:
visited[start] = True
start = nums[start]
length += 1
max_length = max(max_length, length)
return max_length
if __name__ == '__main__':
solution = Solution()
nums = [5, 4, 0, 3, 1, 6, 2]
print(solution.arrayNesting(nums))import java.util.Arrays;
public class Solution {
public int arrayNesting(int[] nums) {
boolean[] visited = new boolean[nums.length];
int max_length = 0;
for (int i = 0; i < nums.length; i++) {
if (!visited[i]) {
int start = i, length = 0;
do {
visited[start] = true;
start = nums[start];
length++;
} while (!visited[start]);
max_length = Math.max(max_length, length);
}
}
return max_length;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {5, 4, 0, 3, 1, 6, 2};
System.out.println(solution.arrayNesting(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
template <typename T> void print_vector(const vector<T>& vec) {
for (const auto& x : vec)
cout << x << ' ';
cout << endl;
}
int arrayNesting(vector<int>& nums) {
vector<bool> visited(nums.size(), false);
int max_length = 0;
for (int i = 0; i < nums.size(); ++i) {
if (!visited[i]) {
int start = i, length = 0;
do {
visited[start] = true;
start = nums[start];
++length;
} while (!visited[start]);
max_length = max(max_length, length);
}
}
return max_length;
}
int main() {
vector<int> nums = {5, 4, 0, 3, 1, 6, 2};
cout << arrayNesting(nums) << endl;
return 0;
}var arrayNesting = function(nums) {
let visited = new Array(nums.length).fill(false);
let maxLength = 0;
for (let i = 0; i < nums.length; i++) {
if (!visited[i]) {
let start = i, length = 0;
while (!visited[start]) {
visited[start] = true;
start = nums[start];
length++;
}
maxLength = Math.max(maxLength, length);
}
}
return maxLength;
};
console.log(arrayNesting([5, 4, 0, 3, 1, 6, 2]));#include <stdio.h>
#include <stdbool.h>
int arrayNesting(int* nums, int numsSize){
bool visited[numsSize];
for (int i = 0; i < numsSize; i++) visited[i] = false;
int max_length = 0;
for (int i = 0; i < numsSize; i++) {
if (!visited[i]) {
int start = i, length = 0;
do {
visited[start] = true;
start = nums[start];
length++;
} while (!visited[start]);
if (length > max_length) max_length = length;
}
}
return max_length;
}
int main() {
int nums[] = {5, 4, 0, 3, 1, 6, 2};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", arrayNesting(nums, numsSize));
return 0;
}using System;
public class Solution {
public int ArrayNesting(int[] nums) {
bool[] visited = new bool[nums.Length];
int max_length = 0;
for (int i = 0; i < nums.Length; i++) {
if (!visited[i]) {
int start = i, length = 0;
do {
visited[start] = true;
start = nums[start];
length++;
} while (!visited[start]);
max_length = Math.Max(max_length, length);
}
}
return max_length;
}
public static void Main() {
Solution solution = new Solution();
int[] nums = {5, 4, 0, 3, 1, 6, 2};
Console.WriteLine(solution.ArrayNesting(nums));
}
}In Python, we utilize a list to track visited elements, iterating through each potential sequence start with an index and updating max length accordingly using inline checks and loops. The strategy replicates behavior seen in other solutions, iterating until all potential loops are processed.
Time Complexity: O(N), each number is processed once.
Space Complexity: O(N), based on the 'visited' list usage.
Approach 2: Approach 2: In-Place Modification without Extra Space
This approach minimizes space usage by modifying the input array itself as a marker of visited nodes. By setting each visited position to a sentinel value (e.g., -1 or a number outside the expected range), we can achieve the same iterative closure tracking. We simply iterate over each number and trace the sequence until we circle back to a marked node. This is an improvement on memory constraints when needing to handle particularly large datasets.
class Solution:
def arrayNesting(self, nums):
max_length = 0
for i in range(len(nums)):
if nums[i] != -1:
start, length = i, 0
while nums[start] != -1:
temp = nums[start]
nums[start] = -1
start = temp
length += 1
max_length = max(max_length, length)
return max_length
if __name__ == '__main__':
solution = Solution()
nums = [5, 4, 0, 3, 1, 6, 2]
print(solution.arrayNesting(nums))public class Solution {
public int arrayNesting(int[] nums) {
int max_length = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != -1) {
int start = i, length = 0;
while (nums[start] != -1) {
int temp = nums[start];
nums[start] = -1;
start = temp;
length++;
}
max_length = Math.max(max_length, length);
}
}
return max_length;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {5, 4, 0, 3, 1, 6, 2};
System.out.println(solution.arrayNesting(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
int arrayNesting(vector<int>& nums) {
int max_length = 0;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] != -1) {
int start = i, length = 0;
while (nums[start] != -1) {
int temp = nums[start];
nums[start] = -1;
start = temp;
++length;
}
max_length = max(max_length, length);
}
}
return max_length;
}
int main() {
vector<int> nums = {5, 4, 0, 3, 1, 6, 2};
cout << arrayNesting(nums) << endl;
return 0;
}var arrayNesting = function(nums) {
let maxLength = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] !== -1) {
let start = i, length = 0;
while (nums[start] !== -1) {
let temp = nums[start];
nums[start] = -1;
start = temp;
length++;
}
maxLength = Math.max(maxLength, length);
}
}
return maxLength;
};
console.log(arrayNesting([5, 4, 0, 3, 1, 6, 2]));#include <stdio.h>
int arrayNesting(int* nums, int numsSize){
int max_length = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] != -1) {
int start = i, length = 0;
while (nums[start] != -1) {
int temp = nums[start];
nums[start] = -1;
start = temp;
length++;
}
if (length > max_length) max_length = length;
}
}
return max_length;
}
int main() {
int nums[] = {5, 4, 0, 3, 1, 6, 2};
int numsSize = sizeof(nums)/sizeof(nums[0]);
printf("%d\n", arrayNesting(nums, numsSize));
return 0;
}using System;
public class Solution {
public int ArrayNesting(int[] nums) {
int max_length = 0;
for (int i = 0; i < nums.Length; i++) {
if (nums[i] != -1) {
int start = i, length = 0;
while (nums[start] != -1) {
int temp = nums[start];
nums[start] = -1;
start = temp;
length++;
}
max_length = Math.Max(max_length, length);
}
}
return max_length;
}
public static void Main() {
Solution solution = new Solution();
int[] nums = {5, 4, 0, 3, 1, 6, 2};
Console.WriteLine(solution.ArrayNesting(nums));
}
}Python processes with altered index-marks to determine the scope of each sequence. The use of negative integers as flags corroborates chain completion effectively, employing basic looping structures to fold each path into its minimum required representation without further data creation.
Time Complexity: O(N), achieved by one full iteration.
Space Complexity: O(1), resulting from markers substituting added arrays.
Approach 3: Default Approach
func arrayNesting(nums []int) int {
n := len(nums)
vis := make([]bool, n)
ans := 0
for i := 0; i < n; i++ {
if vis[i] {
continue
}
cur, m := nums[i], 1
vis[cur] = true
for nums[cur] != nums[i] {
cur = nums[cur]
m++
vis[cur] = true
}
if m > ans {
ans = m
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Iterative Using Visited Array | Time Complexity: O(N), each number is processed once. |
| Approach 2: In-Place Modification without Extra Space | Time Complexity: O(N), achieved by one full iteration. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Cycle Traversal with Visited Array | O(n) | O(n) | Best for clarity and when modifying the input array is not allowed |
| In-Place Modification (Mark Visited) | O(n) | O(1) | Memory-constrained scenarios or when the array can be safely modified |
Frequently asked questions
Is Array Nesting easy or hard?
Array Nesting is rated Medium difficulty on LeetCode. The main challenge is recognizing that the permutation forms cycles and that each cycle only needs to be processed once to achieve O(n) performance.
Array Nesting Python/Java solution
Python and Java solutions typically iterate through the array while maintaining a visited structure. For each unvisited index, repeatedly follow nums[i] until a visited node appears, counting the path length. The maximum length encountered is returned as the result.
How to solve Array Nesting in O(n)?
Traverse the array and treat each index as the start of a cycle. Follow nums[i] repeatedly until reaching a previously visited index, counting the length of that cycle. Mark elements as visited during traversal so each index is processed once, giving O(n) total time.
What is the best approach for Array Nesting?
The best approach is cycle traversal using a visited array. Since the input is a permutation of 0..n-1, following nums[i] forms disjoint cycles. By visiting each index once and counting the cycle length, you compute the maximum set size in O(n) time and O(n) space.
Is Array Nesting asked at Google/Amazon/Meta?
Array cycle and permutation traversal problems appear frequently in interviews at large tech companies including Google, Amazon, and Meta. The question tests graph traversal intuition, cycle detection, and ability to optimize space usage.
What data structure is used in Array Nesting?
The common implementation uses a boolean visited array to track processed indices. Conceptually the array forms a directed graph where each node points to another index, and the solution finds the length of cycles in that structure.
What is the time complexity of Array Nesting?
The optimal time complexity is O(n). Each element in the permutation is visited at most once while exploring cycles. Both the visited-array approach and the in-place marking approach achieve linear time.