Array nesting

Array Depth-First Search

56.5% acceptance

Jan 13, 2026

2276

159

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].

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn array_nesting(nums: Vec<i32>) -> i32 {
    let mut nums = nums;
    let n = nums.len();
    let mut max_len = 0;
    for i in 0..n {
      if nums[i] == i32::MAX { continue; }
      let mut j = i;
      let mut len = 0;
      while nums[j] != i32::MAX {
        let next = nums[j] as usize;
        nums[j] = i32::MAX;
        j = next;
        len += 1;
      }
      max_len = max_len.max(len);
    }
    max_len
  }
}