The longest path problem asks for the path with the most edges (or the largest total weight) in a graph. On a directed acyclic graph (DAG) you solve it in O(V + E) with a topological order and a small DP array. On a general graph with cycles it is NP-hard, so no known algorithm is fast on every input. Most interview problems that look like “longest path” are the DAG case in disguise: a grid with increasing values, a course schedule, or a tree.<\/p>\n
Shortest path has polynomial algorithms (BFS, Dijkstra, Bellman-Ford). Longest simple<\/em> path, where no node repeats, is NP-hard on general graphs, because it contains the Hamiltonian path problem: a path through all The naive idea of “negate the weights and run shortest path” fails. With cycles you get negative cycles, and the walk can loop forever. Without cycles, the idea works, but you don’t need it: a DAG has a much simpler solution.<\/p>\n In a DAG every edge goes “forward” in some ordering of the nodes (a topological order). So if you process nodes in that order, by the time you reach a node all the paths that can end at it are already accounted for. Define Kahn’s algorithm (repeatedly remove nodes with in-degree 0) gives the topological order and does the DP in one pass. It has a bonus: if fewer than These print 3, 0, -1 and 1. In the first graph the longest path is Time is O(V + E): each node enters the queue once and each edge is relaxed once. Space is O(V + E) for the adjacency list plus O(V) for the in-degree, distance and queue arrays.<\/p>\n You can get the same result top-down: the longest path starting at This version assumes the graph is acyclic. On a cycle it recurses without end, so check for cycles first if the input is not guaranteed to be a DAG (see detecting cycles in graphs<\/a>).<\/p>\n The most common wrong answer is off by one. A path with When nodes or edges carry weights, you add the weight instead of 1. LeetCode 2050, Parallel Courses III, is the standard example: each course has a duration in months, prerequisites form a DAG, you can take any number of courses in parallel, and you need the minimum total time. That time is the longest weighted path through the prerequisite graph. Here This is also how the critical path in project scheduling is computed, and the same shape appears in build systems: the longest dependency chain sets the minimum build time even with unlimited parallel workers.<\/p>\n For each node, the longest path that bends at it is To practice this one step by step, there is a Binary Tree Diameter lesson<\/a> on AlgoCademy.<\/p>\n Both grids give 4 (the first is If the problem allows cycles and wants a simple path, you are in NP-hard territory. In an interview that means one of three things: the input is small enough for backtracking (exponential, with a visited set that you undo), the graph has extra structure (a tree, a DAG, a bitmask DP over at most about 20 nodes), or you misread the problem. Say so out loud, and ask about constraints before choosing an approach.<\/p>\nn<\/code> nodes exists exactly when the longest simple path has n - 1<\/code> edges.<\/p>\nLongest path in a DAG<\/h2>\n
dist[v]<\/code> as the number of edges on the longest path that ends at v<\/code>. Start every node at 0 and relax each edge u -> v<\/code> with dist[v] = max(dist[v], dist[u] + 1)<\/code>. The answer is the largest value in dist<\/code>.<\/p>\nn<\/code> nodes get processed, the graph has a cycle, so you can reject invalid input instead of returning a wrong answer.<\/p>\nfrom collections import deque\n\n\ndef longest_path_dag(n, edges):\n \"\"\"Number of edges on the longest path in a DAG with nodes 0..n-1.\n Returns -1 if the graph has a cycle.\"\"\"\n if n == 0:\n return 0\n graph = [[] for _ in range(n)]\n indegree = [0] * n\n for u, v in edges:\n graph[u].append(v)\n indegree[v] += 1\n\n queue = deque(i for i in range(n) if indegree[i] == 0)\n dist = [0] * n # dist[v] = longest path (in edges) ending at v\n processed = 0\n while queue:\n u = queue.popleft()\n processed += 1\n for v in graph[u]:\n dist[v] = max(dist[v], dist[u] + 1)\n indegree[v] -= 1\n if indegree[v] == 0:\n queue.append(v)\n if processed < n:\n return -1\n return max(dist)\n\n\nprint(longest_path_dag(6, [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)])) # 3\nprint(longest_path_dag(3, [])) # 0\nprint(longest_path_dag(3, [(0, 1), (1, 2), (2, 0)])) # -1\nprint(longest_path_dag(4, [(0, 1), (2, 3)])) # 1\n<\/code><\/pre>\n0 -> 1 -> 3 -> 4<\/code>, with 3 edges. The last graph is disconnected, and the answer is still correct because every in-degree-0 node starts the queue.<\/p>\nComplexity<\/h3>\n
Memoized DFS version<\/h3>\n
u<\/code> is 0 if u<\/code> has no outgoing edges, otherwise 1 plus the best of its neighbors. Cache the result per node. This is the form to reach for when the graph is implicit, as in grid problems. Python’s default recursion limit is about 1000 frames, so a long chain of nodes needs an iterative version (like Kahn’s above) or a raised limit.<\/p>\nfrom functools import lru_cache\n\n\ndef longest_dfs(n, edges):\n g = [[] for _ in range(n)]\n for u, v in edges:\n g[u].append(v)\n\n @lru_cache(None)\n def f(u):\n return max((f(v) + 1 for v in g[u]), default=0)\n\n return max((f(i) for i in range(n)), default=0)\n\n\nprint(longest_dfs(6, [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)])) # 3\n<\/code><\/pre>\nNodes or edges? Read the statement<\/h2>\n
k<\/code> nodes has k - 1<\/code> edges, and problems differ on which they ask for. A single node is a path of length 0 in edges and 1 in nodes. Check this against the examples before you code. Also decide up front what an empty graph returns; the code above returns 0.<\/p>\nThe same idea with weights: Parallel Courses III<\/h2>\n
finish[c]<\/code> is the earliest month by which course c<\/code> can be finished.<\/p>\nfrom collections import deque\n\n\ndef minimum_time(n, relations, time):\n graph = [[] for _ in range(n + 1)]\n indegree = [0] * (n + 1)\n for a, b in relations: # a must finish before b starts\n graph[a].append(b)\n indegree[b] += 1\n finish = [0] * (n + 1)\n queue = deque()\n for c in range(1, n + 1):\n finish[c] = time[c - 1]\n if indegree[c] == 0:\n queue.append(c)\n while queue:\n u = queue.popleft()\n for v in graph[u]:\n finish[v] = max(finish[v], finish[u] + time[v - 1])\n indegree[v] -= 1\n if indegree[v] == 0:\n queue.append(v)\n return max(finish)\n\n\nprint(minimum_time(3, [[1, 3], [2, 3]], [3, 2, 5])) # 8\nprint(minimum_time(5, [[1, 5], [2, 5], [3, 5], [3, 4], [4, 5]], [1, 2, 3, 4, 5])) # 12\n<\/code><\/pre>\nLeetCode problems that are longest path in disguise<\/h2>\n
\n
Tree diameter<\/h3>\n
left_depth + right_depth<\/code>. Return the depth upward and keep the best bend seen so far.<\/p>\nclass TreeNode:\n def __init__(self, val=0, left=None, right=None):\n self.val, self.left, self.right = val, left, right\n\n\ndef diameter(root):\n best = 0\n\n def depth(node):\n nonlocal best\n if not node:\n return 0\n l, r = depth(node.left), depth(node.right)\n best = max(best, l + r)\n return 1 + max(l, r)\n\n depth(root)\n return best\n\n\nt = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))\nprint(diameter(t)) # 3 (4 -> 2 -> 1 -> 3, or 5 -> 2 -> 1 -> 3)\n<\/code><\/pre>\nLongest increasing path in a matrix<\/h3>\n
def longest_increasing_path(matrix):\n if not matrix or not matrix[0]:\n return 0\n m, n = len(matrix), len(matrix[0])\n memo = {}\n\n def dfs(i, j):\n if (i, j) in memo:\n return memo[(i, j)]\n best = 1 # the cell itself\n for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):\n x, y = i + di, j + dj\n if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:\n best = max(best, 1 + dfs(x, y))\n memo[(i, j)] = best\n return best\n\n return max(dfs(i, j) for i in range(m) for j in range(n))\n\n\nprint(longest_increasing_path([[9, 9, 4], [6, 6, 8], [2, 1, 1]])) # 4\nprint(longest_increasing_path([[3, 4, 5], [3, 2, 6], [2, 2, 1]])) # 4\n<\/code><\/pre>\n1 -> 2 -> 6 -> 9<\/code>). Without the memo the DFS re-explores the same cells exponentially often; with it, each cell is computed once. If memoization is new to you, see tabulation and memoization<\/a> or the Memoization lesson<\/a>. A closely related write-up is longest path in a DAG<\/a>.<\/p>\nCommon mistakes<\/h2>\n
\n
If the graph has cycles<\/h2>\n