We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Largest Color Value in a Directed Graph

Number: 1986

Difficulty: Hard

Paid? No

Companies: Juspay, Google, Adobe, Microsoft

Problem Description

Given a directed graph with n nodes where each node is colored (denoted by a lowercase letter from a given colors string) and m directed edges, the task is to find the largest color value along any valid path. A path's color value is defined as the frequency count of the most frequent color in that path. If the graph contains a cycle, return -1.

Key Insights

  • This problem involves detecting cycles and handling paths in a directed graph.
  • Topological sort (using Kahn's algorithm) is useful to process nodes in order.
  • Use dynamic programming (DP) where dp[node][color] captures the maximum count of a given color along a path ending at that node.
  • The final result is the maximum value in the DP table and if not all nodes can be processed (cycle detection), return -1.

Space and Time Complexity

Time Complexity: O(n + m + 26 * n) ≈ O(n + m)
Space Complexity: O(26 * n + n + m), which simplifies to O(n + m)

Solution

We approach the problem by performing a topological sort on the graph to ensure that nodes are processed only after all their predecessors have been handled. We maintain a DP table dp[node][color] where each entry represents the highest frequency of the given color along any path ending at that node. Initially, each node inherits a frequency of 1 for its own color. As each node is processed from the queue (from Kahn's algorithm), we update the dp values for its neighbors by taking the maximum of their current value and the dp value from the current node (and adding one if the neighbor's color matches the current color index). If we detect that not all nodes have been processed (i.e., the graph had a cycle), we return -1. Otherwise, we extract the largest frequency from the DP table as our answer.

Code Solutions

from collections import deque

def largestPathValue(colors: str, edges: list) -> int:
    n = len(colors)
    # build graph and in-degree array
    graph = [[] for _ in range(n)]
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1

    # dp[node][color] -> max frequency for color along path ending at node
    dp = [[0] * 26 for _ in range(n)]
    
    q = deque()
    for i in range(n):
        if in_degree[i] == 0:
            q.append(i)
        # initialize own color count
        dp[i][ord(colors[i]) - ord('a')] = 1
        
    processed = 0
    result = 0

    while q:
        node = q.popleft()
        processed += 1
        # update final answer using node best value
        result = max(result, max(dp[node]))
        for neighbor in graph[node]:
            # update dp for neighbor
            for c in range(26):
                # if neighbor has the same color, increase count
                add = 1 if c == (ord(colors[neighbor]) - ord('a')) else 0
                dp[neighbor][c] = max(dp[neighbor][c], dp[node][c] + add)
            # decrease in-degree and add to queue if ready
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                q.append(neighbor)
    
    # if not all nodes processed, there's a cycle
    return result if processed == n else -1

# Example usage:
if __name__ == "__main__":
    colors = "abaca"
    edges = [[0,1],[0,2],[2,3],[3,4]]
    print(largestPathValue(colors, edges))  # Output: 3
← Back to All Questions