{x}
blog image

Largest Color Value in a Directed Graph

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.

 

Example 1:

Input: colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]
Output: 3
Explanation: 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
Explanation: 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 Explanation

This problem asks to find the largest color value in any valid path within a directed graph. A valid path is a sequence of nodes where each node connects to the next via a directed edge. The color value of a path is the maximum frequency of any single color among the nodes in that path. The solution involves topological sorting and dynamic programming.

Approach:

  1. Cycle Detection: The presence of a cycle in the directed graph indicates that there's no valid topological ordering, implying infinitely long paths. We detect cycles by checking if the number of nodes processed in topological sort equals the total number of nodes. If not, it means a cycle exists, and we return -1.

  2. Topological Sort: We use Kahn's algorithm for topological sorting. This algorithm maintains an indegree array for each node, representing the number of incoming edges. Nodes with an indegree of 0 are added to a queue as starting points. The algorithm iteratively removes nodes from the queue, processing their outgoing edges and decrementing the indegree of their neighbors.

  3. Dynamic Programming: A 2D array dp is used to store the maximum frequency of each color for each node. dp[i][j] represents the maximum frequency of color j encountered in any path ending at node i. During the topological sort, we update dp[i][j] by considering the maximum frequency from its predecessors.

  4. Maximum Frequency Update: When a node is processed, we update the dp array for its neighbors. For each neighbor j and each color k, we take the maximum between the current dp[j][k] and dp[i][k] (frequency from predecessors) plus 1 if the neighbor's color is k. This ensures that the maximum frequency of each color is tracked along all possible paths.

Time Complexity: O(N + M), where N is the number of nodes and M is the number of edges. Topological sort and DP take linear time.

Space Complexity: O(N + M) to store the graph, indegree array, and dp array.

Code Explanation (Python):

from collections import defaultdict, deque
 
class Solution:
    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
        n = len(colors)
        indeg = [0] * n  # Indegree of each node
        g = defaultdict(list)  # Adjacency list representing the graph
 
        # Build the graph and indegree array
        for u, v in edges:
            g[u].append(v)
            indeg[v] += 1
 
        q = deque()  # Queue for topological sort
        dp = [[0] * 26 for _ in range(n)]  # DP array
 
        # Initialize queue with nodes having indegree 0
        for i, v in enumerate(indeg):
            if v == 0:
                q.append(i)
                c = ord(colors[i]) - ord('a')
                dp[i][c] = 1
 
        cnt = 0  # Count of processed nodes
        ans = 1  # Maximum color value
 
        # Topological sort and DP
        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])
 
        # Cycle detection: If cnt < n, a cycle exists
        return -1 if cnt < n else ans

The Java, C++, and Go code follow a similar structure, adapting the data structures and syntax to their respective languages. The core logic of topological sort and dynamic programming remains consistent across all implementations.