Largest Color Value in a Directed Graph

Hard
1529.

Largest Color Value in a Directed Graph

Largest Color Value in a Directed Graph is a hard coding problem on dynamic programming, graph and memoization, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} colors
 * @param {number[][]} edges
 * @return {number}
 */
var largestPathValue = function(colors, edges) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

Hints for Largest Color Value in a Directed Graph

  1. Hint 1

    If there is a cycle, the answer is -1 — a topological sort detects that for free.

  2. 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.

  3. 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

  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

Java

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