565. Array Nesting

📝 Problem Details

• Title: 565. Array Nesting
• Link: https://leetcode.com/problems/array-nesting/
• Difficulty: Medium
• Tags/Categories: Arrays DFS

💭What Were My Initial Thoughts?

- every element in nums has to be between 0 and n-1
- return the starting element that forms the longest path across indices in the array
	- treating the problem as a graph or traversal problem should help
	- treat each "set" as a path in a graph, we go as far or deep as possible, recording the depth

🤔What Did I Struggle With?

~ the wording of the question is confusing in an interview setting
- defining the DFS lambda function 

💡 Explanation of Solution

- use a visited array to keep track of indices that have already been part of a cycle 
	- this avoids recomputation of already encountered paths
- for every unvisited index, start a DFS traversal to explore the cycle 
- track the length of the current cycle during DFS and update the maximum length encountered

⌛ Complexity Analysis

Time Complexity: O(n) each index is visited exactly once 
Space Complexity: O(n) due to the use of the visited boolean array

💻 Implementation of Solution

class Solution {
public:
    int arrayNesting(vector<int>& nums) {
    
        int n = nums.size();
        vector<bool> visited (n, false);
        int maxLen = 0;
 
        auto dfs = [&](int start) -> int {
            int count = 0, index = start;
            
            while(!visited[index]) {
                visited[index] = true;
                index = nums[index];
                count++;
            }
            return count;
        };
 
        for(int i=0; i < n; i++) {
            maxLen = max(maxLen, dfs(i));
        }
        return maxLen;
    }
};