Largest Color Value in a Directed Graph — Problem & Solution
Largest Color Value in a Directed Graph solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Largest Color Value in a Directed Graph is a hard coding problem on dynamic programming, graph and memoization, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Dynamic Programming, Graph, Memoization, Topological Sort
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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.length1 <= n <= 10^50 <= edges.length <= 10^5colors consists of lowercase English letters0 <= aj, bj < n
Hints for Largest Color Value in a Directed Graph
Hint 1
If there is a cycle, the answer is -1 — a topological sort detects that for free.
Hint 2
For a DAG, think of a DP indexed by node and colour: the most nodes of colour c on any path ending at this node.
Hint 3
Process nodes in topological order (Kahn's algorithm), pushing each node's 26 counts forward along its out-edges and adding 1 for its own colour.
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
- Build adjacency lists and in-degrees; start a queue with every node of in-degree 0.
- Pop a node
u, add 1 todp[u][colour(u)], and update the answer with the largest entry ofdp[u]. - For each edge
u → v, setdp[v][c] = max(dp[v][c], dp[u][c])for every colour, decrementv's in-degree, and enqueue it when it reaches 0. - If fewer than
nnodes 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 -1Java
public static int largestPathValue(String colors, int[][] edges) {
int n = colors.length();
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
int[] indeg = new int[n];
for (int[] e : edges) { adj.get(e[0]).add(e[1]); indeg[e[1]]++; }
int[][] dp = new int[n][26];
int[] queue = new int[n];
int head = 0, tail = 0;
for (int i = 0; i < n; i++) if (indeg[i] == 0) queue[tail++] = i;
int best = 0;
while (head < tail) {
int u = queue[head++];
dp[u][colors.charAt(u) - 'a']++;
for (int c = 0; c < 26; c++) best = Math.max(best, dp[u][c]);
for (int v : adj.get(u)) {
for (int c = 0; c < 26; c++) if (dp[u][c] > dp[v][c]) dp[v][c] = dp[u][c];
if (--indeg[v] == 0) queue[tail++] = v;
}
}
return tail == n ? best : -1;
}C++
int largestPathValue(string colors, vector<vector<int>>& edges) {
int n = colors.size();
vector<vector<int>> adj(n);
vector<int> indeg(n, 0);
for (auto& e : edges) { adj[e[0]].push_back(e[1]); indeg[e[1]]++; }
vector<array<int, 26>> dp(n);
for (auto& row : dp) row.fill(0);
vector<int> queue;
for (int i = 0; i < n; i++) if (indeg[i] == 0) queue.push_back(i);
int best = 0;
for (size_t h = 0; h < queue.size(); h++) {
int u = queue[h];
dp[u][colors[u] - 'a']++;
for (int c = 0; c < 26; c++) best = max(best, dp[u][c]);
for (int v : adj[u]) {
for (int c = 0; c < 26; c++) if (dp[u][c] > dp[v][c]) dp[v][c] = dp[u][c];
if (--indeg[v] == 0) queue.push_back(v);
}
}
return (int)queue.size() == n ? best : -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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming · Graph Data Structure