# Largest Color Value in a Directed Graph
**Difficulty:** HARD
[External](https://leetcode.com/problems/largest-color-value-in-a-directed-graph)
Canonical: https://scaleengineer.com/dsa/problems/largest-color-value-in-a-directed-graph
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Topological Sort](https://scaleengineer.com/algorithms/topological-sort)
**Data structures:** Hash Table, Graph
**Companies:** [Juspay](https://scaleengineer.com/companies/juspay)
---
## 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_.

**Example 1:**

![](https://assets.glich.co/dsa/largest-color-value-in-a-directed-graph/image0.png)

**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:**

![](https://assets.glich.co/dsa/largest-color-value-in-a-directed-graph/image1.png)

**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`

# Approaches
## Dynamic Programming with DFS
This approach uses Depth First Search (DFS) combined with dynamic programming (memoization) to solve the problem. We define a state `dp[u][c]` as the maximum count of a specific color `c` on any path starting from node `u`. A recursive DFS function computes these DP values for all nodes. To handle cycles, which would lead to infinite paths, we keep track of the nodes currently in the recursion stack. If we encounter a node that's already in the stack, we've found a cycle.
**Time:** O(N + M). Each node and edge is visited once by the DFS. For each node, we perform a constant number of operations (26 color updates from its children and one for itself). The work is proportional to the number of nodes and edges. More precisely, it's O(26 * (N + M)). · **Space:** O(N + M), where N is the number of nodes and M is the number of edges. This is because we store the adjacency list (O(N+M)), the DP table (O(N * 26)), the recursion stack (O(N) in the worst case), and visited/path arrays (O(N)). Since 26 is a constant, this simplifies to O(N + M).
**Pros:** It's a conceptually clear extension of a standard DFS traversal.; Correctly solves the problem by handling path-dependent values and cycles simultaneously.
**Cons:** The recursive implementation can lead to a `StackOverflowError` if the graph contains very long paths, although this is unlikely given the problem constraints.; Requires managing two separate state arrays (`visited` and `path`) for correctness, which can be slightly more complex than the iterative approach.
### Explanation
In this method, we aim to compute the answer for each subproblem, where a subproblem is finding the largest color value for all paths starting at a particular node `u`. We use a 2D array `dp[n][26]` for memoization, where `dp[u][c]` stores the maximum count of color `c` on any path originating from node `u`.

The computation is done via a recursive DFS function, let's call it `dfs(u)`. This function is responsible for computing the values for `dp[u]`. To do this, it first recursively calls itself for all neighbors `v` of `u`. Once the `dp` values for all neighbors are computed, `dp[u][c]` can be determined by taking the maximum of `dp[v][c]` over all neighbors `v`, and then adding 1 if the color of node `u` is `c`.

To avoid recomputing for the same node multiple times, a `visited` array is used. More importantly, to detect cycles, we use a `path` (or `recursionStack`) array. Before exploring the neighbors of `u`, we mark `path[u] = true`. If we then try to visit a neighbor `v` that already has `path[v] = true`, we have found a back edge, indicating a cycle. If a cycle is found, we should immediately stop and return -1. After exploring all of `u`'s neighbors, we backtrack by setting `path[u] = false`.

The final answer is the maximum value found in the `dp` table after the DFS has been run for all unvisited nodes.

```java
class Solution {
    List<Integer>[] adj;
    int[][] dp;
    boolean[] visited;
    boolean[] path;
    String colors;

    public int largestColorValue(String colors, int[][] edges) {
        int n = colors.length();
        this.colors = colors;
        adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
        }

        dp = new int[n][26];
        visited = new boolean[n];
        path = new boolean[n];
        int maxVal = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                if (hasCycle(i)) {
                    return -1;
                }
            }
        }
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<26; j++) {
                maxVal = Math.max(maxVal, dp[i][j]);
            }
        }

        return maxVal;
    }

    private boolean hasCycle(int u) {
        visited[u] = true;
        path[u] = true;

        for (int v : adj[u]) {
            if (path[v]) {
                return true; // Cycle detected
            }
            if (!visited[v]) {
                if (hasCycle(v)) {
                    return true;
                }
            }
            // Update dp table for u based on v
            for (int i = 0; i < 26; i++) {
                dp[u][i] = Math.max(dp[u][i], dp[v][i]);
            }
        }

        dp[u][colors.charAt(u) - 'a']++;
        path[u] = false;
        return false;
    }
}
```
### Algorithm
- Build an adjacency list representation of the graph.
- Initialize a DP table `dp[n][26]`, where `dp[u][c]` will store the maximum count of color `c` on any path starting from node `u`.
- Use two boolean arrays, `visited[n]` to mark nodes for which the DP values have been computed, and `path[n]` to track nodes in the current recursion stack for cycle detection.
- Iterate through each node `i` from `0` to `n-1`. If `i` has not been visited, start a DFS from `i`.
- The `dfs(u)` function performs the following:
  1. Mark `u` as visiting (`path[u] = true`) and visited (`visited[u] = true`).
  2. For each neighbor `v` of `u`:
     - If `v` is already in the current `path`, a cycle is detected. Return a value indicating a cycle.
     - If `v` has not been visited, recursively call `dfs(v)`. Propagate the cycle detection signal if the recursive call finds one.
     - After the recursive call returns (and no cycle was found), update the DP values for `u` based on `v`: `dp[u][c] = max(dp[u][c], dp[v][c])` for all 26 colors `c`.
  3. After iterating through all neighbors, increment the count for the color of the current node `u`: `dp[u][colors.charAt(u) - 'a']++`.
  4. Unmark `u` from the current path (`path[u] = false`).
- If the DFS ever detects a cycle, terminate and return -1.
- After the DFS completes for all components, the `dp` table is filled. The answer is the maximum value in the entire `dp` table.

## Topological Sort (Kahn's Algorithm)
A more robust and typically preferred approach for problems on directed acyclic graphs (DAGs) is to use a topological sort. This method processes nodes in a linear order, such that for every directed edge from node `u` to node `v`, `u` comes before `v` in the ordering. We can use Kahn's algorithm, an iterative approach to topological sorting, to process nodes and propagate the color counts along the paths. If a topological sort cannot be completed (i.e., not all nodes are visited), it signifies the presence of a cycle.
**Time:** O(N + M). Building the graph and in-degrees takes O(N + M). Each node is enqueued and dequeued once. When processing a node, we iterate through its neighbors. Thus, each edge is processed once. For each edge, we do O(26) work. Finding the max at each node also takes O(26). The total time is O(N*26 + M*26), which simplifies to O(N + M). · **Space:** O(N + M). We store the adjacency list (O(N+M)), the `counts` table (O(N * 26)), the in-degree array (O(N)), and the queue (O(N) in the worst case). This simplifies to O(N + M).
**Pros:** Iterative nature avoids recursion and potential stack overflow issues.; Cycle detection is a natural outcome of the algorithm, making the logic clean.; Generally considered more efficient in practice due to lower overhead than recursion.
**Cons:** Requires pre-computation of in-degrees and building the adjacency list, which adds some initial setup.; The logic of propagating counts iteratively might be slightly less intuitive to some compared to the recursive DP formulation.
### Explanation
This approach reformulates the problem to fit an iterative, breadth-first-search-like traversal based on the graph's topology. It avoids recursion and its potential pitfalls.

1.  **Graph Representation and In-degrees**: First, we construct an adjacency list for the graph and an array to store the in-degree of each node. An edge `u -> v` increments the in-degree of `v`.

2.  **Initialization**: We use a `counts[n][26]` table, where `counts[u][c]` will store the maximum count of color `c` on any path ending at node `u`. A queue is initialized with all nodes having an in-degree of 0. For these source nodes, we initialize their own color count in the `counts` table, e.g., `counts[u][color of u] = 1`.

3.  **Processing Nodes**: We process nodes from the queue one by one. When a node `u` is dequeued, we know that we have found the maximum color counts for all paths ending at `u`. We can then update the global maximum color value. For each neighbor `v` of `u`, we propagate the counts from `u`. The new count for a color `c` on a path to `v` through `u` is `counts[u][c]`, plus one if `v` itself has color `c`. We update `counts[v][c]` by taking the maximum over all its incoming neighbors. After processing `u`'s influence on `v`, we decrement `v`'s in-degree. If it becomes 0, `v` is ready to be processed and is added to the queue.

4.  **Cycle Detection**: We keep track of the number of nodes processed. If this number is less than the total number of nodes `n` after the queue becomes empty, it means some nodes were part of a cycle and could never have their in-degree reduced to 0. In this case, we return -1.

5.  **Result**: If no cycle is detected, the maximum value found during the process is the answer.

```java
class Solution {
    public int largestColorValue(String colors, int[][] edges) {
        int n = colors.length();
        List<Integer>[] adj = new ArrayList[n];
        int[] inDegree = new int[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
            inDegree[edge[1]]++;
        }

        int[][] counts = new int[n][26];
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
                counts[i][colors.charAt(i) - 'a'] = 1;
            }
        }

        int maxVal = 0;
        int processedNodes = 0;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            processedNodes++;

            int maxCountAtU = 0;
            for(int count : counts[u]) {
                maxCountAtU = Math.max(maxCountAtU, count);
            }
            maxVal = Math.max(maxVal, maxCountAtU);

            for (int v : adj[u]) {
                for (int i = 0; i < 26; i++) {
                    int newCount = counts[u][i] + (colors.charAt(v) - 'a' == i ? 1 : 0);
                    counts[v][i] = Math.max(counts[v][i], newCount);
                }
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        if (processedNodes < n) {
            return -1; // Cycle detected
        }

        return maxVal;
    }
}
```
### Algorithm
- Build an adjacency list and compute the in-degree for every node.
- Initialize a queue and add all nodes with an in-degree of 0. These are the starting points of paths in the graph.
- Create a `counts[n][26]` table. `counts[u][c]` will store the maximum count of color `c` on any path from a source node to `u`.
- For each source node `u` added to the queue, initialize its own color count: `counts[u][colors.charAt(u) - 'a'] = 1`.
- Initialize a counter for processed nodes, `processedNodes = 0`, and the answer, `maxColorValue = 0`.
- Start a loop that continues as long as the queue is not empty:
  1. Dequeue a node `u`. Increment `processedNodes`.
  2. Find the maximum value in `counts[u]` and update `maxColorValue = max(maxColorValue, max_in_counts_u)`.
  3. For each neighbor `v` of `u`:
     - Update the counts for `v` based on `u`. For each color `c`, `counts[v][c] = max(counts[v][c], counts[u][c] + (colors.charAt(v) - 'a' == c ? 1 : 0))`.
     - Decrement the in-degree of `v`.
     - If the in-degree of `v` becomes 0, enqueue `v`.
- After the loop, if `processedNodes < n`, it means some nodes were not visited. This is only possible if there is a cycle in the graph. In this case, return -1.
- Otherwise, the graph is a DAG, and we can return the computed `maxColorValue`.

# Solutions
### Java

```java
class Solution {
public
  int largestPathValue(String colors, int[][] edges) {
    int n = colors.length();
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, k->new ArrayList<>());
    int[] indeg = new int[n];
    for (int[] e : edges) {
      int a = e[0], b = e[1];
      g[a].add(b);
      ++indeg[b];
    }
    Deque<Integer> q = new ArrayDeque<>();
    int[][] dp = new int[n][26];
    for (int i = 0; i < n; ++i) {
      if (indeg[i] == 0) {
        q.offer(i);
        int c = colors.charAt(i) - 'a';
        ++dp[i][c];
      }
    }
    int cnt = 0;
    int ans = 1;
    while (!q.isEmpty()) {
      int i = q.pollFirst();
      ++cnt;
      for (int j : g[i]) {
        if (--indeg[j] == 0) {
          q.offer(j);
        }
        int c = colors.charAt(j) - 'a';
        for (int k = 0; k < 26; ++k) {
          dp[j][k] = Math.max(dp[j][k], dp[i][k] + (c == k ? 1 : 0));
          ans = Math.max(ans, dp[j][k]);
        }
      }
    }
    return cnt == n ? ans : -1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int largestPathValue(string colors, vector<vector<int>> &edges) {
    int n = colors.size();
    vector<vector<int>> g(n);
    vector<int> indeg(n);
    for (auto &e : edges) {
      int a = e[0], b = e[1];
      g[a].push_back(b);
      ++indeg[b];
    }
    queue<int> q;
    vector<vector<int>> dp(n, vector<int>(26));
    for (int i = 0; i < n; ++i) {
      if (indeg[i] == 0) {
        q.push(i);
        int c = colors[i] - 'a';
        dp[i][c]++;
      }
    }
    int cnt = 0;
    int ans = 1;
    while (!q.empty()) {
      int i = q.front();
      q.pop();
      ++cnt;
      for (int j : g[i]) {
        if (--indeg[j] == 0)
          q.push(j);
        int c = colors[j] - 'a';
        for (int k = 0; k < 26; ++k) {
          dp[j][k] = max(dp[j][k], dp[i][k] + (c == k));
          ans = max(ans, dp[j][k]);
        }
      }
    }
    return cnt == n ? ans : -1;
  }
};

```

### Python

```python
class Solution:
    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int: n = len(colors) indeg = [0] * n g = defaultdict(list) for a, b in edges: g[a]. append(b) indeg[b] += 1 q = deque() dp = [[0] * 26 for _ in range(n)] for i, v in enumerate(indeg): if v == 0: q . append(i) c = ord(colors[i]) - ord('a') dp[i][c] += 1 cnt = 0 ans = 1 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]) return - 1 if cnt < n else ans

```