Problem
There is a directed graph of n
colored nodes and m
edges. The nodes are numbered from 0
to n - 1
.
You are given a string colors
where colors[i]
is a lowercase English letter representing the color of the ith
node in this graph (0-indexed). You are also given a 2D array edges
where edges[j] = [aj, bj]
indicates that there is a directed edge from node aj
to node bj
.
A valid path in the graph is a sequence of nodes x1 -> x2 -> x3 -> ... -> xk
such that there is a directed edge from xi
to xi+1
for every 1 <= i < k
. The color value of the path is the number of nodes that are colored the most frequently occurring color along that path.
Return the largest color value of any valid path in the given graph, or -1
if the graph contains a cycle.
Examples
Example 1:
graph LR; A(0):::red --> C(2):::red --> D(3):::blue --> E(4):::red A --> B(1):::purple classDef red fill:#FF0000,stroke:#000,stroke-width:1px,color:#fff; classDef blue fill:#ADD8E6,stroke:#000,stroke-width:1px; classDef purple fill:#DDA0DD,stroke:#333,stroke-width:2px;
|
|
Example 2:
graph LR; A(0):::red --> A classDef red fill:#FF0000,stroke:#000,stroke-width:1px,color:#fff;
|
|
Constraints:
n == colors.length
m == edges.length
1 <= n <= 105
0 <= m <= 105
colors
consists of lowercase English letters.0 <= aj, bj < n
Solution
Method 1 - Using Topological Sort
We need to compute the maximum colour count along paths in a directed graph while detecting cycles (in which case the problem becomes invalid). Topological Sorting is ideal for processing nodes in a directed acyclic graph. While traversing, maintain colour frequencies at each node from incoming neighbours.
Approach
- Build the Graph:
- Construct adjacency list from the
edges
. - Count incoming edges (in-degree) for each node to determine the starting points for topological sorting.
- Construct adjacency list from the
- Topological Sort:
- Use a queue to perform BFS-based topological sort, starting with nodes having
0 in-degree
. - Maintain the count of visited nodes to detect cycles.
- Use a queue to perform BFS-based topological sort, starting with nodes having
- Track Colour Counts:
- During BFS, propagate colour frequency counts to successor nodes.
- Update the counts if higher frequencies are found.
- Cycle Detection:
- If the number of processed nodes is fewer than
n
, a cycle is present (return-1
).
- If the number of processed nodes is fewer than
- Output Maximum Value:
- Return the maximum colour count among all paths.
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n + m * c)
n
: Number of nodes,m
: Number of edges,c
: Number of distinct colours (bounded by 26 since colours are lowercase English letters).- Graph traversal and updating counts at each edge dominate.
- 🧺 Space complexity:
O(n * c + m)
- Colour count array per node (
n * c
), adjacency list (m
).
- Colour count array per node (