algoadvance

Leetcode 565. Array Nesting

Problem Statement

Leetcode Problem 565: Array Nesting.

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 traversing the array from a start index i such that the set S contains the values:

S = {nums[i], nums[nums[i]], nums[nums[nums[i]]], ... }

The set stops adding values if a value that is already in the set is encountered. The goal is to find the longest length of set S.

Example:

Input: nums = [5, 4, 0, 3, 1, 6, 2]
Output: 4
Explanation: 
nums[0] = 5, nums[5] = 6, nums[6] = 2, nums[2] = 0
Thereby, `S` = {5, 6, 2, 0}

Clarifying Questions

  1. What is the range of the input values?
    • The input array nums consists of integers in the range [0, n-1].
  2. Are there any constraints on the size of n?
    • Yes, typically n is within the constraints for competitive programming (1 <= n <= 10^4).
  3. Can the input array be empty?
    • No, based on the problem constraints, the array will not be empty.

Strategy

  1. Initialization: Create a boolean vector visited of size n initialized to false. This will help us track if we have already visited an index.
  2. Iterate and Track: Loop through each index of nums. If an index has not been visited yet, start a new set and keep track of its size.
    • For each set, follow the elements of nums as given by the problem statement. Mark each index as visited.
    • Track the length of the current set and update the maximum length if this set is longer than the previously found ones.
  3. Break Loops: Since a cycle in the set would mean revisiting the same index, the process ensures that each element contributes to only one set.

Code

Here’s how you can implement this in C++:

#include <vector>
#include <algorithm>

class Solution {
public:
    int arrayNesting(std::vector<int>& nums) {
        int n = nums.size();
        std::vector<bool> visited(n, false);
        int maxLength = 0;

        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                int length = 0;
                int current = i;
                
                while (!visited[current]) {
                    visited[current] = true;
                    current = nums[current];
                    ++length;
                }
                
                maxLength = std::max(maxLength, length);
            }
        }

        return maxLength;
    }
};

Time Complexity

This efficient solution ensures that we achieve the goal within optimal time, adhering to competitive programming constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI