Largest Color Value in a Directed Graph

How it works

Since we need valid paths in a directed graph, topological sorting naturally fits. We process nodes in topological order using Kahn's algorithm (BFS with indegree tracking). For each node, we propagate color counts to its neighbors before they are processed. If we cannot process all nodes, a cycle exists. This approach avoids recursion and handles cycle detection elegantly.

Steps

1. Build an adjacency list and compute the indegree of each node.
2. Initialize a 2D array count[node][color] for tracking color frequencies.
3. Add all nodes with indegree 0 to a queue.
4. Process nodes in BFS order:
   • Increment the count for the node's own color.
   • Update the result with this color count.
   • For each neighbor, propagate the current node's color counts, then decrement the neighbor's indegree. If it becomes 0, add it to the queue.
5. If the number of processed nodes equals n, return the result. Otherwise, return -1 (cycle detected).

Complexity

• Time complexity: O(V + E)
• Space complexity: O(V + E)

Where V is the number of verticies and E is the number of edges.

Things to watch for

Failing to Detect Cycles

The problem requires returning -1 if the graph contains a cycle, since cycles mean there are infinitely long paths. A common mistake is forgetting to track the current DFS path separately from globally visited nodes. Using only a single visited set will not distinguish between nodes that are ancestors in the current path (indicating a cycle) versus nodes that were visited in a completely different traversal.

Confusing Path Tracking with Global Visited

When using DFS with memoization, you need two separate tracking mechanisms: one for nodes currently in the recursion stack (to detect cycles) and one for nodes that have been fully processed (to avoid recomputation). Mixing these up leads to either false cycle detection or infinite loops.

Not Propagating Color Counts Correctly

When computing the maximum color count for a node, you must consider the counts from all reachable nodes, not just immediate neighbors. The DP state count[node][color] should represent the maximum count of that color on any path starting from that node. Forgetting to take the maximum across all neighbors or failing to add the current node's color contribution leads to incorrect results.

Processing Nodes Before All Predecessors Are Complete

In the topological sort approach, a node should only be processed after all its incoming edges have been handled. If you process a node too early (before all predecessors have propagated their color counts), you'll miss potential maximum values from paths that haven't been fully computed yet.

Off-by-One Errors in Color Indexing

Colors are given as lowercase letters but need to be converted to indices 0-25 for array access. A common bug is incorrectly converting characters (e.g., forgetting to subtract 'a') or mixing up when to add the current node's color contribution (should be added exactly once per node on the path).

from collections import deque

class Solution:
    def largestPathValue(self, colors: str, edges: list[list[int]]) -> int:
        n = len(colors)
        adj = [[] for _ in range(n)]
        indegree = [0] * n
        count = [[0] * 26 for _ in range(n)]

        for u, v in edges:
            adj[u].append(v)
            indegree[v] += 1

        q = deque()
        for i in range(n):
            if indegree[i] == 0:
                q.append(i)

        visit = res = 0
        while q:
            node = q.popleft()
            visit += 1
            colorIndex = ord(colors[node]) - ord('a')
            count[node][colorIndex] += 1
            res = max(res, count[node][colorIndex])

            for nei in adj[node]:
                for c in range(26):
                    count[nei][c] = max(count[nei][c], count[node][c])

                indegree[nei] -= 1
                if indegree[nei] == 0:
                    q.append(nei)

        return res if visit == n else -1

class Solution {
public:
    int largestPathValue(string colors, vector<vector<int>>& edges) {
        int n = colors.size();
        vector<vector<int>> adj(n);
        vector<int> indegree(n);
        vector<vector<int>> count(n, vector<int>(26));

        for (auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            indegree[edge[1]]++;
        }

        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }

        int visit = 0, res = 0;
        while (!q.empty()) {
            int node = q.front();q.pop();
            visit++;
            int colorIndex = colors[node] - 'a';
            count[node][colorIndex]++;
            res = max(res, count[node][colorIndex]);

            for (int& nei : adj[node]) {
                for (int c = 0; c < 26; c++) {
                    count[nei][c] = max(count[nei][c], count[node][c]);
                }
                if (--indegree[nei] == 0) {
                    q.push(nei);
                }
            }
        }

        return visit == n ? res : -1;
    }
};