NeetCode #620LC-1857HardGraphs
← Back to All Problems#620 · #1857 · Largest Color Value in a Directed Graph(有向图中最大颜色值)
📌 Problem Statement & Constraints
You are given a directed graph of
n coloured nodes (colors[i] is a lowercase letter) and edges. A valid path follows the edge directions. The path's colour value is the maximum count of any single colour along it. Return the maximum colour value over all valid paths, or -1 if the graph contains a cycle. Constraints: 1 <= n <= 10^5, 0 <= edges.length <= 10^5, colors.length == n.💡 Core Algorithmic Approaches
- Topological sort with a DP over colour counts:
dp[node][c]is the maximum count of colourcon a path ending atnode. - When a node is popped (its in-degree reached 0), its
dpis final; add 1 to its own colour and update the answer. - Propagate
dp[node]to each successor by taking the element-wise maximum. - If fewer than
nnodes are popped, the graph has a cycle and the answer is -1.
💻 Benchmark Python3 Implementation
class Solution:
def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
from collections import defaultdict, deque
n = len(colors)
g = defaultdict(list)
indeg = [0] * n
for a, b in edges:
g[a].append(b)
indeg[b] += 1
# dp[i][c] = max count of colour c on a path ending at i
dp = [[0] * 26 for _ in range(n)]
q = deque(i for i in range(n) if indeg[i] == 0)
seen = 0
best = 0
while q:
node = q.popleft()
seen += 1
ci = ord(colors[node]) - 97
dp[node][ci] += 1 # this node contributes its own colour
best = max(best, dp[node][ci])
for nxt in g[node]:
for c in range(26):
if dp[node][c] > dp[nxt][c]:
dp[nxt][c] = dp[node][c] # propagate the best counts
indeg[nxt] -= 1
if indeg[nxt] == 0:
q.append(nxt)
return best if seen == n else -1⚡ Complexity Deep Dive
⏱️ Time Complexity
O((V + E) * 26): each edge triggers a 26-element merge.
💾 Space Complexity
O(26V) for the DP table.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the cycle check: a cyclic graph has no valid path, so the answer is -1.
- Propagating before adding the node's own colour: the successor would miss this node's contribution.
- Using a DFS with memoisation: a cyclic graph would recurse forever; the topological order handles it.
- Initialising the DP to 1 for each node's colour: the increment happens on pop instead.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.