Array Nesting - Practice Coding Problems

Array Nesting - 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 element nums[k] of index = k. The next element in s[k] should be nums[nums[k]], and then nums[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].

Input & Output

Example 1 — Basic Case

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

› Output: 4

💡 Note: Starting from index 0: 0→5→6→2→0 forms a cycle of length 4. This is the longest cycle in the array.

Example 2 — Single Element Cycles

$ Input: nums = [0,1,2]

› Output: 1

💡 Note: Each element points to itself: 0→0, 1→1, 2→2. Each forms a cycle of length 1.

Example 3 — Two Cycles

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

› Output: 3

💡 Note: Two cycles exist: 0→1→2→0 (length 3) and 3→4→3 (length 2). Maximum is 3.

Constraints

1 ≤ nums.length ≤ 10⁵
0 ≤ nums[i] < nums.length
All values in nums are unique

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array where each value is a valid index

Follow Chains

Follow nums[i] → nums[nums[i]] → ... until cycle

Find Maximum

Return length of longest cycle found

Key Takeaway

🎯 Key Insight: Each element belongs to exactly one cycle, so mark visited elements globally to avoid redundant work

Asked in

G Google 15 a Amazon 12 F Facebook 8

The key insight is that each element can only belong to one cycle, so we can mark elements as visited globally to avoid redundant exploration. The optimal approach uses DFS with global visited array to find all cycles efficiently. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try Every Starting Point	O(n²)	O(n)	For each index, follow the chain until we find a cycle and track the maximum length
DFS with Global Visited Array	O(n)	O(n)	Use DFS to explore chains while marking visited elements globally to avoid redundant work

Brute Force - Try Every Starting Point — Algorithm Steps

Step 1: For each starting index k from 0 to n-1
Step 2: Follow the chain starting from nums[k] until we find a cycle
Step 3: Count the length of the chain and update maximum

Visualization

Tap to expand

Step-by-Step Walkthrough

Start from index 0

Follow chain: 0→1→2→0 (cycle detected)

Start from index 1

Follow chain: 1→2→0→1 (same cycle)

Find Maximum

Compare all chain lengths

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(int* nums, int numsSize) {
    int maxLength = 0;
    
    for (int start = 0; start < numsSize; start++) {
        bool* visited = (bool*)calloc(numsSize, sizeof(bool));
        int current = start;
        int length = 0;
        
        while (!visited[current]) {
            visited[current] = true;
            current = nums[current];
            length++;
        }
        
        if (length > maxLength) {
            maxLength = length;
        }
        free(visited);
    }
    
    return maxLength;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int size = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            nums[size++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    printf("%d\n", solution(nums, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n starting positions, we might traverse up to n elements in the worst case

⚠ Quadratic Growth

Space Complexity

O(n)

Need a visited set to track elements in current chain to detect cycles

⚡ Linearithmic Space

68.0K Views

Medium Frequency

~25 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try Every Starting Point — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler