⚡Flashcard Drill➔
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

  1. Topological sort with a DP over colour counts: dp[node][c] is the maximum count of colour c on a path ending at node.
  2. When a node is popped (its in-degree reached 0), its dp is final; add 1 to its own colour and update the answer.
  3. Propagate dp[node] to each successor by taking the element-wise maximum.
  4. If fewer than n nodes 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems