Get started

Largest Color Value in a Directed Graph — Hard Problem & Solution

A directed graph has n nodes numbered 0 to n - 1, where n == colors.length. Node i has the colour colors[i], a lowercase letter.

Problem statement

A directed graph has n nodes numbered 0 to n - 1, where n == colors.length. Node i has the colour colors[i], a lowercase letter. Each edges[j] = [aj, bj] is a directed edge from aj to bj.

A path is a sequence of nodes x1 → x2 → … → xk in which every consecutive pair is joined by an edge in that direction. The colour value of a path is the number of nodes on it that carry its most frequent colour.

Return the largest colour value of any path in the graph, or -1 if the graph contains a cycle.

Example 1

Input: colors = "xyxzx", edges = [[0,1],[1,2],[0,2],[2,3],[2,4]]
Output: 3
Explanation: The path 0 → 1 → 2 → 4 holds colour `x` three times.

Example 2

Input: colors = "abc", edges = [[0,1],[1,2],[2,1]]
Output: -1
Explanation: Nodes 1 and 2 form a cycle.

Example 3

Input: colors = "a", edges = []
Output: 1

Constraints

  • n == colors.length
  • 1 <= n <= 10^5
  • 0 <= edges.length <= 10^5
  • colors consists of lowercase English letters
  • 0 <= aj, bj < n

How to solve Largest Color Value in a Directed Graph

Run Kahn's topological sort while carrying, for every node, the best count of each of the 26 colours over all paths that end there.

Approach

  1. Build adjacency lists and in-degrees; start a queue with every node of in-degree 0.
  2. Pop a node u, add 1 to dp[u][colour(u)], and update the answer with the largest entry of dp[u].
  3. For each edge u → v, set dp[v][c] = max(dp[v][c], dp[u][c]) for every colour, decrement v's in-degree, and enqueue it when it reaches 0.
  4. If fewer than n nodes were popped, a cycle blocked the sort: return -1. Otherwise return the answer.

Why it works

A node is popped only after all its predecessors, so by then dp[v][c] already holds the maximum count of colour c over every path that reaches v from a predecessor; adding v's own colour completes the value for paths ending at v. Every path ends somewhere, so the maximum over all nodes and colours is the answer. Nodes on (or downstream of) a cycle never reach in-degree 0, which is exactly how the cycle is detected.

Complexity

  • Time — O(26 · (n + m))
  • Space — O(26 · n + m)

Pitfalls

  • A self-loop [i, i] is a cycle too; Kahn's algorithm handles it because the node's in-degree never drops to 0.
  • Recursive DFS on 10^5 nodes can overflow the stack in some languages — the queue-based version avoids that.
  • Increment a node's own colour exactly once, when it is popped, not when it is pushed or relaxed.

Reference solution

Python

from typing import List
from collections import deque

def largestPathValue(colors: str, edges: List[List[int]]) -> int:
    n = len(colors)
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for a, b in edges:
        adj[a].append(b)
        indeg[b] += 1
    col = [ord(ch) - 97 for ch in colors]
    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:
        u = q.popleft()
        seen += 1
        du = dp[u]
        du[col[u]] += 1
        top = max(du)
        if top > best:
            best = top
        for v in adj[u]:
            dv = dp[v]
            for c in range(26):
                if du[c] > dv[c]:
                    dv[c] = du[c]
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return best if seen == n else -1

JavaScript

var largestPathValue = function(colors, edges) {
    var n = colors.length;
    var adj = [], indeg = [], dp = [];
    for (var i = 0; i < n; i++) {
        adj.push([]);
        indeg.push(0);
        var row = [];
        for (var c = 0; c < 26; c++) row.push(0);
        dp.push(row);
    }
    for (var e = 0; e < edges.length; e++) {
        adj[edges[e][0]].push(edges[e][1]);
        indeg[edges[e][1]]++;
    }
    var queue = [];
    for (var s = 0; s < n; s++) if (indeg[s] === 0) queue.push(s);
    var best = 0;
    for (var h = 0; h < queue.length; h++) {
        var u = queue[h];
        dp[u][colors.charCodeAt(u) - 97]++;
        for (var k = 0; k < 26; k++) if (dp[u][k] > best) best = dp[u][k];
        for (var j = 0; j < adj[u].length; j++) {
            var v = adj[u][j];
            for (var t = 0; t < 26; t++) if (dp[u][t] > dp[v][t]) dp[v][t] = dp[u][t];
            if (--indeg[v] === 0) queue.push(v);
        }
    }
    return queue.length === n ? best : -1;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 304 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming · Graph Data Structure