Largest Color Value in a Directed Graph

Hard

#1696Time: 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).1 company

Patterns

Dynamic Programming Memoization Counting

Algorithms

Topological Sort

Data structures

Hash Table Graph

Companies

Juspay

Prompt

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 i^th node in this graph (0-indexed). You are also given a 2D array edges where edges[j] = [a_j, b_j] indicates that there is a directed edge from node a_j to node b_j.

A valid path in the graph is a sequence of nodes x₁ -> x₂ -> x₃ -> ... -> x_k such that there is a directed edge from x_i to x_i+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:

"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 <= 10⁵
0 <= m <= 10⁵
colors consists of lowercase English letters.
0 <= a_j, b_j < n

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    List<Integer>[] adj;3    int[][] dp;4    boolean[] visited;5    boolean[] path;6    String colors;7 8    public int largestColorValue(String colors, int[][] edges) {9        int n = colors.length();10        this.colors = colors;11        adj = new ArrayList[n];12        for (int i = 0; i < n; i++) {13            adj[i] = new ArrayList<>();14        }15        for (int[] edge : edges) {16            adj[edge[0]].add(edge[1]);17        }18 19        dp = new int[n][26];20        visited = new boolean[n];21        path = new boolean[n];22        int maxVal = 0;23 24        for (int i = 0; i < n; i++) {25            if (!visited[i]) {26                if (hasCycle(i)) {27                    return -1;28                }29            }30        }31        32        for(int i=0; i<n; i++) {33            for(int j=0; j<26; j++) {34                maxVal = Math.max(maxVal, dp[i][j]);35            }36        }37 38        return maxVal;39    }40 41    private boolean hasCycle(int u) {42        visited[u] = true;43        path[u] = true;44 45        for (int v : adj[u]) {46            if (path[v]) {47                return true; // Cycle detected48            }49            if (!visited[v]) {50                if (hasCycle(v)) {51                    return true;52                }53            }54            // Update dp table for u based on v55            for (int i = 0; i < 26; i++) {56                dp[u][i] = Math.max(dp[u][i], dp[v][i]);57            }58        }59 60        dp[u][colors.charAt(u) - 'a']++;61        path[u] = false;62        return false;63    }64}

Complexity

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).

Trade-offs

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.

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.

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.

Walkthrough

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.

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.
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.
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.
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.
Result: If no cycle is detected, the maximum value found during the process is the answer.

1class Solution {2    public int largestColorValue(String colors, int[][] edges) {3        int n = colors.length();4        List<Integer>[] adj = new ArrayList[n];5        int[] inDegree = new int[n];6        for (int i = 0; i < n; i++) {7            adj[i] = new ArrayList<>();8        }9        for (int[] edge : edges) {10            adj[edge[0]].add(edge[1]);11            inDegree[edge[1]]++;12        }13 14        int[][] counts = new int[n][26];15        Queue<Integer> queue = new LinkedList<>();16 17        for (int i = 0; i < n; i++) {18            if (inDegree[i] == 0) {19                queue.offer(i);20                counts[i][colors.charAt(i) - 'a'] = 1;21            }22        }23 24        int maxVal = 0;25        int processedNodes = 0;26 27        while (!queue.isEmpty()) {28            int u = queue.poll();29            processedNodes++;30 31            int maxCountAtU = 0;32            for(int count : counts[u]) {33                maxCountAtU = Math.max(maxCountAtU, count);34            }35            maxVal = Math.max(maxVal, maxCountAtU);36 37            for (int v : adj[u]) {38                for (int i = 0; i < 26; i++) {39                    int newCount = counts[u][i] + (colors.charAt(v) - 'a' == i ? 1 : 0);40                    counts[v][i] = Math.max(counts[v][i], newCount);41                }42                inDegree[v]--;43                if (inDegree[v] == 0) {44                    queue.offer(v);45                }46            }47        }48 49        if (processedNodes < n) {50            return -1; // Cycle detected51        }52 53        return maxVal;54    }55}

Complexity

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).

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int largestPathValue(String colors, int[][] edges) {4    int n = colors.length();5    List<Integer>[] g = new List[n];6    Arrays.setAll(g, k->new ArrayList<>());7    int[] indeg = new int[n];8    for (int[] e : edges) {9      int a = e[0], b = e[1];10      g[a].add(b);11      ++indeg[b];12    }13    Deque<Integer> q = new ArrayDeque<>();14    int[][] dp = new int[n][26];15    for (int i = 0; i < n; ++i) {16      if (indeg[i] == 0) {17        q.offer(i);18        int c = colors.charAt(i) - 'a';19        ++dp[i][c];20      }21    }22    int cnt = 0;23    int ans = 1;24    while (!q.isEmpty()) {25      int i = q.pollFirst();26      ++cnt;27      for (int j : g[i]) {28        if (--indeg[j] == 0) {29          q.offer(j);30        }31        int c = colors.charAt(j) - 'a';32        for (int k = 0; k < 26; ++k) {33          dp[j][k] = Math.max(dp[j][k], dp[i][k] + (c == k ? 1 : 0));34          ans = Math.max(ans, dp[j][k]);35        }36      }37    }38    return cnt == n ? ans : -1;39  }40}

1class Solution {2public:3  int largestPathValue(string colors, vector<vector<int>> &edges) {4    int n = colors.size();5    vector<vector<int>> g(n);6    vector<int> indeg(n);7    for (auto &e : edges) {8      int a = e[0], b = e[1];9      g[a].push_back(b);10      ++indeg[b];11    }12    queue<int> q;13    vector<vector<int>> dp(n, vector<int>(26));14    for (int i = 0; i < n; ++i) {15      if (indeg[i] == 0) {16        q.push(i);17        int c = colors[i] - 'a';18        dp[i][c]++;19      }20    }21    int cnt = 0;22    int ans = 1;23    while (!q.empty()) {24      int i = q.front();25      q.pop();26      ++cnt;27      for (int j : g[i]) {28        if (--indeg[j] == 0)29          q.push(j);30        int c = colors[j] - 'a';31        for (int k = 0; k < 26; ++k) {32          dp[j][k] = max(dp[j][k], dp[i][k] + (c == k));33          ans = max(ans, dp[j][k]);34        }35      }36    }37    return cnt == n ? ans : -1;38  }39};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem