#1857

Hard

auto_awesomeGraph indegree plus topological ordering

LeetCode Problem Workspace

Largest Color Value in a Directed Graph

Compute the maximum color frequency along any valid path in a directed graph using topological ordering and dynamic programming.

hash table dynamic programming graph topological sort memoization

Problem Statement

You are given a directed graph with n nodes numbered 0 to n-1, each node assigned a lowercase letter representing its color. Edges are provided as a 2D array where edges[j] = [aj, bj] indicates a directed edge from node aj to node bj. Your task is to determine the largest color value along any valid path, defined as the maximum frequency of a single color within that path.

A valid path is a sequence of nodes where each consecutive pair is connected by a directed edge. If the graph contains a cycle, return -1, since a color value cannot be determined reliably. Compute efficiently for up to 10^5 nodes and edges, considering all paths and color distributions.

Examples

Example 1

Input: colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]

Output: 3

The path 0 -> 2 -> 3 -> 4 contains 3 nodes that are colored "a" (red in the above image).

Example 2

Input: colors = "a", edges = [[0,0]]

Output: -1

There is a cycle from 0 to 0.

Constraints

n == colors.length
m == edges.length
1 <= n <= 105
0 <= m <= 105
colors consists of lowercase English letters.
0 <= aj, bj < n

Solution Approach

Cycle Detection via Indegree Tracking

Begin by computing the indegree of every node to identify nodes without incoming edges. Use these nodes as starting points for topological sort. If any node remains with indegree > 0 after processing, the graph contains a cycle, and return -1.

Dynamic Programming with Color Count Propagation

Maintain a DP table where dp[node][color] records the maximum count of color along paths ending at node. Traverse nodes in topological order, updating neighbor counts by taking the maximum between current and propagated color counts plus one if the neighbor matches the color.

Compute the Largest Color Value

After propagating counts along all edges, iterate through the DP table to identify the maximum value across all colors and nodes. This represents the largest color frequency along any valid path in the graph.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + m + 26*(n + m)) accounting for topological sort and color count propagation for 26 letters. Space complexity is O(26*n) for the DP table tracking color counts per node.

What Interviewers Usually Probe

Check if you can detect cycles before processing paths to avoid invalid results.
Use topological sort to guarantee that color counts propagate correctly without revisiting nodes.
Verify the maximum color frequency along each path, not just cumulative edge counts.

Common Pitfalls or Variants

Common pitfalls

Failing to detect cycles leading to incorrect color value calculation.
Updating color counts incorrectly when multiple predecessors share different color distributions.
Assuming only a single color propagates along a path rather than tracking all 26 letters.

Follow-up variants

Compute the smallest color value along a path instead of the largest.
Handle graphs where nodes can have multiple colors assigned and count maximum frequency.
Find the number of distinct paths that achieve the largest color value.

FAQ

What is the main strategy to solve Largest Color Value in a Directed Graph?

Use indegree-based cycle detection followed by topological sort while dynamically propagating color counts along edges.

Why is topological ordering essential for this problem?

Topological ordering ensures that each node's color counts are updated after all predecessors, preventing incorrect propagation.

How do I handle cycles in the graph?

If a node remains with non-zero indegree after processing all nodes, a cycle exists, and the problem requires returning -1.

What is the role of dynamic programming here?

DP records the maximum occurrence of each color along paths ending at each node, efficiently combining counts from multiple predecessors.

Can this approach scale to 10^5 nodes and edges?

Yes, the method runs in linear time relative to nodes and edges with extra factor 26 for colors, fitting within reasonable computational limits.

terminal

Solution

Solution 1: Topological Sort + Dynamic Programming

Calculate the in-degree of each node and perform a topological sort.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

class Solution:
    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
        n = len(colors)
        indeg = [0] * n
        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            indeg[b] += 1
        q = deque()
        dp = [[0] * 26 for _ in range(n)]
        for i, v in enumerate(indeg):
            if v == 0:
                q.append(i)
                c = ord(colors[i]) - ord('a')
                dp[i][c] += 1
        cnt = 0
        ans = 1
        while q:
            i = q.popleft()
            cnt += 1
            for j in g[i]:
                indeg[j] -= 1
                if indeg[j] == 0:
                    q.append(j)
                c = ord(colors[j]) - ord('a')
                for k in range(26):
                    dp[j][k] = max(dp[j][k], dp[i][k] + (c == k))
                    ans = max(ans, dp[j][k])
        return -1 if cnt < n else ans

Continue Practicing

#1728 cat and mouse ii #2328 number of increasing paths in a grid #913 cat and mouse