Largest Color Value In A Directed Graph - Leetcode Solution

The problem "Largest Color Value In A Directed Graph" on LeetCode can be solved using dynamic programming and topological sorting.

Problem Statement:

Given a directed graph, containing N nodes, and edges, each node i is assigned a color colors[i]. Find the largest number of colors in a longest path starting from the source(s) and ending at any node of the graph. (If a cycle is detected, return -1.)

Solution:

Step 1: Topological Sorting

The problem requires finding the longest path in the directed graph starting from the source(s). To achieve this, we can use topological sorting. If a directed graph has cycles, then it cannot be topologically sorted, which means that there is no longest path. Therefore, we need to check if the graph contains any cycle or not.

Step 2: Detecting Cycles

To check if a graph contains cycles, we can use Depth First Search (DFS) algorithm, to traverse the graph and maintain a visited array and a recursion stack. The visited array keeps track of all the nodes that have been visited during the DFS traversal, and the recursion stack is used to detect cycles.

We start by selecting a node as the source and calling DFS on it. If during the DFS traversal, we visit a node that is already present in the recursion stack, then it is a cycle, and we return -1.

Step 3: Dynamic Programming

Once we have checked for cycles and topologically sorted the graph, we can start optimizing the solution using dynamic programming. We can use an array, colorCount, to keep track of the maximum count of colors seen so far for each node in the topological order.

For each node, we iterate over its outgoing edges, and for each edge, we update the colorCount of the destination node by taking the maximum between the colorCount of the current node and the colorCount of the destination node plus 1, if the color of the destination node is not already visited.

Finally, we return the maximum value in the colorCount array as the answer.

Pseudo Code:

def largestPathColors(graph: List[List[int]], colors: str) -> int:

n = len(colors)

# Step 1: Topological Sorting
queue, indegree = [], [0] * n    
for u in range(n):
    for v in graph[u]:
        indegree[v] += 1
for u in range(n):
    if indegree[u] == 0:
        queue.append(u)

# Step 2: Detecting Cycles
visited, stack = set(), set()
def hasCycle(u):
    if u in visited:
        return False             # Already visited node
    visited.add(u)
    stack.add(u)
    for v in graph[u]:
        if v in stack or hasCycle(v):
            return True          # Cycle detected
    stack.remove(u)
    return False

while queue:
    u = queue.pop(0)
    if hasCycle(u):
        return -1
   
    # Step 3: Dynamic Programming
    colorCount = [0] * n
    colorCount[u] = 1
    for v in graph[u]:
        for i in range(26):
            if ord(colors[v]) == (i + 97):
                colorCount[v] = max(colorCount[v], colorCount[u] + (i == ord(colors[v]) - 97))
                break
        indegree[v] -= 1
        if indegree[v] == 0:
            queue.append(v)
            
return max(colorCount)

Time Complexity:

The time complexity of the above solution is O(N + M), where N is the number of nodes and M is the number of edges in the graph. The cost of topological sorting is O(N + M), and the cost of detecting cycles using DFS is O(N + M). The cost of dynamic programming is also O(N + M) as we visit every edge exactly once.

Space Complexity:

The space complexity of the above solution is O(N) to store the visited set, recursion stack, queue, and colorCount array.

1