What is the time complexity of Longest Cycle in a Graph?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Longest Cycle in a Graph?

This problem uses Depth-First Search, Breadth-First Search, Graph, Topological Sort. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Longest Cycle in a Graph?

Insight 1: The graph is a directed graph where each node has at most one outgoing edge. This means each connected component of the graph resembles a 'linked list' with a possible 'cycle' at its end. Insight 2: We can use Depth-First Search (DFS) to traverse the graph and detect cycles. We need to keep track of the distance from the starting node during the traversal to calculate the cycle length if we encounter a node already visited in the current path.

Which companies ask LeetCode 2360. Longest Cycle in a Graph in interviews?

This problem is frequently asked at Juspay.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Longest Cycle in a Graph - LeetCode 2360 Solution

Longest Cycle in a Graph - Complete Solution Guide

Longest Cycle in a Graph is LeetCode problem 2360, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

You are given a directed graph of n nodes numbered from 0 to n - 1 , where each node has at most one outgoing edge. The graph is represented with a given 0-indexed array edges of size n , indicating that there is a directed edge from node i to node edges[i] . If there is no outgoing edge from node i , then edges[i] == -1 . Return the length of the longest cycle in the graph . If no cycle exists, return -1 . A cycle is a path that starts and ends at the same node. Example 1: Input: edges = [3,3,4

Detailed Explanation

The problem asks us to find the longest cycle in a directed graph. The graph is represented by an array `edges` where `edges[i]` indicates the node to which node `i` points. If `edges[i]` is -1, then node `i` has no outgoing edge. We need to find the length of the longest cycle in this graph. A cycle is a path that starts and ends at the same node. If there are no cycles, we should return -1. The constraints are that the number of nodes (n) is between 2 and 10^5, and each node has at most one outgoing edge.

Solution Approach

The solution uses a modified Depth-First Search (DFS) approach to traverse the graph and detect cycles. It iterates through each node in the graph. If a node hasn't been visited yet, it starts a DFS traversal from that node. During the traversal, it maintains a 'path_map' (HashMap/unordered_map) to store the distance of each node from the starting node in the current path. If a node is encountered that is already present in the 'path_map', it means a cycle has been detected. The length of the cycle is calculated as the difference between the current distance and the distance of the node in the 'path_map'. The maximum cycle length is updated accordingly. After each DFS traversal, all nodes in the current 'path_map' are marked as visited to avoid re-exploring them in subsequent iterations.

Step-by-Step Algorithm

Step 1: Initialize an array 'visited' of boolean values, all set to 'false'. This array will keep track of globally visited nodes.
Step 2: Initialize 'longest_cycle' to -1. This variable will store the length of the longest cycle found so far.
Step 3: Iterate through each node 'i' from 0 to n-1.
Step 4: If 'visited[i]' is 'false', start a DFS traversal from node 'i'.
Step 5: Inside the DFS traversal, create a 'path_map' (dictionary/hashmap) to store the distance of each node from the starting node 'i' in the current path.
Step 6: Initialize 'dist' to 0, representing the current distance from the starting node.
Step 7: Initialize 'curr' to 'i', representing the current node being visited.
Step 8: While 'curr' is not -1 and 'visited[curr]' is 'false', do the following:
Step 9: If 'curr' is already present in 'path_map', calculate the cycle length as 'dist - path_map[curr]' and update 'longest_cycle' with the maximum value. Break the inner loop (cycle detected).
Step 10: If 'curr' is not in 'path_map', add it to 'path_map' with its distance 'dist'.
Step 11: Increment 'dist' by 1.
Step 12: Move to the next node by setting 'curr' to 'edges[curr]'.
Step 13: After the DFS traversal is complete (inner loop terminates), mark all nodes present in 'path_map' as visited by setting 'visited[node]' to 'true' for each node in 'path_map'.
Step 14: After iterating through all nodes, return 'longest_cycle'.

Key Insights

Insight 1: The graph is a directed graph where each node has at most one outgoing edge. This means each connected component of the graph resembles a 'linked list' with a possible 'cycle' at its end.
Insight 2: We can use Depth-First Search (DFS) to traverse the graph and detect cycles. We need to keep track of the distance from the starting node during the traversal to calculate the cycle length if we encounter a node already visited in the current path.
Insight 3: To avoid re-processing parts of the graph, we can use a 'visited' array to mark nodes that have been fully explored. Once a path is fully processed, its nodes will be globally 'visited' and won't be explored again.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Depth-First Search, Breadth-First Search, Graph, Topological Sort.

Companies

Asked at: Juspay.

Longest Cycle in a Graph | LeetCode 2360

Hard

Depth-First Search Breadth-First Search Graph Topological Sort

Time: O(n)Space: O(n)

Solution Code

Available in:

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int longestCycle(int[] edges) {
        int n = edges.length;
        boolean[] visited = new boolean[n];
        int longest_cycle = -1;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                Map<Integer, Integer> path_map = new HashMap<>();
                int dist = 0;
                int curr = i;
                
                while (curr != -1 && !visited[curr]) {
                    if (path_map.containsKey(curr)) {
                        int cycle_len = dist - path_map.get(curr);
                        longest_cycle = Math.max(longest_cycle, cycle_len);
                        break;
                    }
                    
                    path_map.put(curr, dist);
                    dist += 1;
                    curr = edges[curr];
                }
                
                // Mark all nodes in the current path as globally visited
                // to avoid re-processing.
                for (int node : path_map.keySet()) {
                    visited[node] = true;
                }
            }
        }
        
        return longest_cycle;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 2360: Longest Cycle in a Graph - Detailed explanation and solution approaches.

Topics

Depth-First Search Breadth-First Search Graph Topological Sort

Companies

Juspay

Stats

Difficulty:Hard

Languages:4

Companies:1

Problem #:2360

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

14 steps

1
Step 1: Initialize an array 'visited' of boolean values, all set to 'false'. This array will keep track of globally visited nodes.
2
Step 2: Initialize 'longest_cycle' to -1. This variable will store the length of the longest cycle found so far.
3
Step 3: Iterate through each node 'i' from 0 to n-1.
4
Step 4: If 'visited[i]' is 'false', start a DFS traversal from node 'i'.
5
Step 5: Inside the DFS traversal, create a 'path_map' (dictionary/hashmap) to store the distance of each node from the starting node 'i' in the current path.
6
Step 6: Initialize 'dist' to 0, representing the current distance from the starting node.
7
Step 7: Initialize 'curr' to 'i', representing the current node being visited.
8
Step 8: While 'curr' is not -1 and 'visited[curr]' is 'false', do the following:
9
Step 9: If 'curr' is already present in 'path_map', calculate the cycle length as 'dist - path_map[curr]' and update 'longest_cycle' with the maximum value. Break the inner loop (cycle detected).
10
Step 10: If 'curr' is not in 'path_map', add it to 'path_map' with its distance 'dist'.
11
Step 11: Increment 'dist' by 1.
12
Step 12: Move to the next node by setting 'curr' to 'edges[curr]'.
13
Step 13: After the DFS traversal is complete (inner loop terminates), mark all nodes present in 'path_map' as visited by setting 'visited[node]' to 'true' for each node in 'path_map'.
14
Step 14: After iterating through all nodes, return 'longest_cycle'.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The outer loop iterates n times. The inner while loop visits each unvisited node at most once across all iterations of the outer loop. The marking of nodes as visited in the path_map prevents revisiting nodes. Therefore, the overall time complexity is O(n). The space complexity is O(n) due to the visited array and path_map, both of which can potentially store information about all n nodes.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Topological Sort

We could try to perform a topological sort. Nodes that can't be sorted (i.e., are part of a cycle) could then be analyzed to find the longest cycle. This is harder to implement efficiently given the single outgoing edge constraint.

Time: O(n)Space: O(n)

Trade-offs: While theoretically possible, it would likely be more complex to implement and potentially less efficient in practice compared to the DFS approach due to the overhead of the topological sort algorithm and the subsequent cycle detection.

✨

Key Insights

1Insight 1: The graph is a directed graph where each node has at most one outgoing edge. This means each connected component of the graph resembles a 'linked list' with a possible 'cycle' at its end.
2Insight 2: We can use Depth-First Search (DFS) to traverse the graph and detect cycles. We need to keep track of the distance from the starting node during the traversal to calculate the cycle length if we encounter a node already visited in the current path.
3Insight 3: To avoid re-processing parts of the graph, we can use a 'visited' array to mark nodes that have been fully explored. Once a path is fully processed, its nodes will be globally 'visited' and won't be explored again.

📚

Key Terms Explained

For Students

Graph

Nodes connected by edges. Like a social network or city map!

Edge Cases

Edge case 1: No cycle exists in the graph. The algorithm correctly returns -1 because the 'longest_cycle' variable is initialized to -1 and only updated if a cycle is found.
Edge case 2: A cycle of length 1 exists (a node pointing to itself). The algorithm correctly identifies this and returns 1.
Edge case 3: Multiple cycles exist in the graph. The algorithm correctly finds the longest cycle among all cycles.
Edge case 4: A node points to -1. This represents a node with no outgoing edge, and the algorithm handles it correctly by terminating the DFS traversal from that node.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the case where a node points to -1 properly, causing potential errors or infinite loops.

✗Common mistake 2: Forgetting to mark nodes as visited after exploring a path, leading to re-exploration of the same nodes and incorrect cycle length calculations.

✗Common mistake 3: Incorrectly calculating the cycle length (e.g., forgetting to subtract the distance of the starting node of the cycle).

✗Common mistake 4: Not considering the case when there is no cycle present in the graph and returning an incorrect value instead of -1.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Detecting loops in dependency graphs (e.g., in software build systems, task scheduling, or data processing pipelines). The 'edges' would represent dependencies, and cycles would indicate circular dependencies.

🏦Real-world scenario 2: Finding loops in financial transactions or supply chains to identify potential fraud or inefficiencies. Each node could be a transaction or a step in the supply chain, and cycles would represent circular flows.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

These problems test your ability to optimize. Start with a brute force solution, then improve.

⚠️ Watch Out

Always test your solution with edge cases: empty input, single element, and boundary values.

👨‍💻 From Experience

I encountered a variation of this problem in a system design interview. The key was recognizing the underlying pattern.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 21, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 14

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 7

❓

Frequently Asked Questions

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Longest Cycle in a Graph"?

For this hard-level Depth-First Search problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether breadth-first search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?