1857. Largest Color Value in a Directed Graph - Explanation

1. Brute Force (DFS)

Intuition

The problem asks for the maximum count of any single color along any valid path in the graph. A direct approach is to try every possible starting node and every possible color, then use DFS to explore all paths and count how many nodes of that color we encounter. If we detect a cycle during DFS, the answer is -1 since valid paths cannot contain cycles.

Algorithm

Build an adjacency list from the edges.
For each node from 0 to n-1, and for each color from 0 to 25:
- Run DFS from that node, tracking visited nodes in the current path to detect cycles.
- Count nodes matching the target color along the path.
- If a cycle is detected, return -1 immediately.
- Track the maximum color count found.
Return the maximum count.

class Solution:
    def largestPathValue(self, colors: str, edges: list[list[int]]) -> int:
        n = len(colors)
        adj = [[] for _ in range(n)]
        for u, v in edges:
            adj[u].append(v)

        visit = [False] * n
        def dfs(node, c):
            if visit[node]:
                return float("inf")

            visit[node] = True
            clrCnt = 0
            for nei in adj[node]:
                cur = dfs(nei, c)
                if cur == float("inf"):
                    return cur
                clrCnt = max(clrCnt, cur)
            visit[node] = False
            return clrCnt + (c == (ord(colors[node]) - ord('a')))

        res = -1
        for i in range(n):
            for c in range(26):
                cnt = dfs(i, c)
                if cnt == float("inf"):
                    return -1
                res = max(res, cnt)
        return res

Time & Space Complexity

Time complexity: $O(V * (V + E))$
Space complexity: $O(V + E)$

Where $V$ is the number of verticies and $E$ is the number of edges.

2. Depth First Search

Intuition

Instead of checking one color at a time, we can track all 26 color counts simultaneously for each node. Using memoization, once we compute the maximum color counts reachable from a node, we store and reuse that result. We use two sets: one for globally visited nodes (already fully processed) and one for the current DFS path (to detect cycles).

Algorithm

Build an adjacency list from the edges.
Create a 2D array count[node][color] to store the maximum count of each color reachable from each node.
For each node, run DFS:
- If the node is in the current path, a cycle exists; return infinity.
- If already fully visited, return 0.
- Mark the node as in the current path and initialize its own color count to 1.
- For each neighbor, recursively compute counts and update the current node's counts by taking the maximum.
- Remove the node from the current path after processing.
Return the maximum value across all count[node][color], or -1 if a cycle was detected.

class Solution:
    def largestPathValue(self, colors: str, edges: list[list[int]]) -> int:
        adj = defaultdict(list)
        for src, dst in edges:
            adj[src].append(dst)

        def dfs(node):
            if node in path:
                return float("inf")
            if node in visit:
                return 0

            visit.add(node)
            path.add(node)
            colorIndex = ord(colors[node]) - ord('a')
            count[node][colorIndex] = 1

            for nei in adj[node]:
                if dfs(nei) == float("inf"):
                    return float("inf")
                for c in range(26):
                    count[node][c] = max(
                        count[node][c],
                        (1 if c == colorIndex else 0) + count[nei][c]
                    )

            path.remove(node)
            return 0

        n, res = len(colors), 0
        visit, path = set(), set()
        count = [[0] * 26 for _ in range(n)]

        for i in range(n):
            if dfs(i) == float("inf"):
                return -1
            res = max(res, max(count[i]))

        return res

Time & Space Complexity

Time complexity: $O(V + E)$
Space complexity: $O(V + E)$

Where $V$ is the number of verticies and $E$ is the number of edges.

3. Topological Sort (Kahn's Algorithm)

Intuition

Since we need valid paths in a directed graph, topological sorting naturally fits. We process nodes in topological order using Kahn's algorithm (BFS with indegree tracking). For each node, we propagate color counts to its neighbors before they are processed. If we cannot process all nodes, a cycle exists. This approach avoids recursion and handles cycle detection elegantly.

Algorithm

Build an adjacency list and compute the indegree of each node.
Initialize a 2D array count[node][color] for tracking color frequencies.
Add all nodes with indegree 0 to a queue.
Process nodes in BFS order:
- Increment the count for the node's own color.
- Update the result with this color count.
- For each neighbor, propagate the current node's color counts, then decrement the neighbor's indegree. If it becomes 0, add it to the queue.
If the number of processed nodes equals n, return the result. Otherwise, return -1 (cycle detected).

class Solution:
    def largestPathValue(self, colors: str, edges: list[list[int]]) -> int:
        n = len(colors)
        adj = [[] for _ in range(n)]
        indegree = [0] * n
        count = [[0] * 26 for _ in range(n)]

        for u, v in edges:
            adj[u].append(v)
            indegree[v] += 1

        q = deque()
        for i in range(n):
            if indegree[i] == 0:
                q.append(i)

        visit = res = 0
        while q:
            node = q.popleft()
            visit += 1
            colorIndex = ord(colors[node]) - ord('a')
            count[node][colorIndex] += 1
            res = max(res, count[node][colorIndex])

            for nei in adj[node]:
                for c in range(26):
                    count[nei][c] = max(count[nei][c], count[node][c])

                indegree[nei] -= 1
                if indegree[nei] == 0:
                    q.append(nei)

        return res if visit == n else -1

Time & Space Complexity

Time complexity: $O(V + E)$
Space complexity: $O(V + E)$

Where $V$ is the number of verticies and $E$ is the number of edges.