1857. Largest Color Value in a Directed Graph LeetCode Solution

In this guide, you will get 1857. Largest Color Value in a Directed Graph LeetCode Solution with the best time and space complexity. The solution to Largest Color Value in a Directed Graph problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Largest Color Value in a Directed Graph solution in C++
Largest Color Value in a Directed Graph solution in Java
Largest Color Value in a Directed Graph solution in Python
Additional Resources

1857. Largest Color Value in a Directed Graph LeetCode Solution image

Problem Statement of Largest Color Value in a Directed Graph

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:

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:

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

Complexity Analysis

Time Complexity: O(|V| + |E|), where |V| = n and |E| = |\texttt{edges}|
Space Complexity: O(|V| + |E|), where |V| = n and |E| = |\texttt{edges}|

1857. Largest Color Value in a Directed Graph LeetCode Solution in C++

class Solution {
 public:
  int largestPathValue(string colors, vector<vector<int>>& edges) {
    const int n = colors.length();
    int ans = 0;
    int processed = 0;
    vector<vector<int>> graph(n);
    vector<int> inDegrees(n);
    queue<int> q;
    vector<vector<int>> count(n, vector<int>(26));

    // Build the graph.
    for (const vector<int>& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      graph[u].push_back(v);
      ++inDegrees[v];
    }

    // Perform topological sorting.
    for (int i = 0; i < n; ++i)
      if (inDegrees[i] == 0)
        q.push(i);

    while (!q.empty()) {
      const int out = q.front();
      q.pop();
      ++processed;
      ans = max(ans, ++count[out][colors[out] - 'a']);
      for (const int in : graph[out]) {
        for (int i = 0; i < 26; ++i)
          count[in][i] = max(count[in][i], count[out][i]);
        if (--inDegrees[in] == 0)
          q.push(in);
      }
    }

    return processed == n ? ans : -1;
  }
};
/* code provided by PROGIEZ */

1857. Largest Color Value in a Directed Graph LeetCode Solution in Java

class Solution {
  public int largestPathValue(String colors, int[][] edges) {
    final int n = colors.length();
    int ans = 0;
    int processed = 0;
    List<Integer>[] graph = new List[n];
    int[] inDegrees = new int[n];
    int[][] count = new int[n][26];

    for (int i = 0; i < n; ++i)
      graph[i] = new ArrayList<>();

    // Build the graph.
    for (int[] edge : edges) {
      final int u = edge[0];
      final int v = edge[1];
      graph[u].add(v);
      ++inDegrees[v];
    }

    // Perform topological sorting.
    Queue<Integer> q = IntStream.range(0, n)
                           .filter(i -> inDegrees[i] == 0)
                           .boxed()
                           .collect(Collectors.toCollection(ArrayDeque::new));

    while (!q.isEmpty()) {
      final int out = q.poll();
      ++processed;
      ans = Math.max(ans, ++count[out][colors.charAt(out) - 'a']);
      for (final int in : graph[out]) {
        for (int i = 0; i < 26; ++i)
          count[in][i] = Math.max(count[in][i], count[out][i]);
        if (--inDegrees[in] == 0)
          q.offer(in);
      }
    }

    return processed == n ? ans : -1;
  }
}
// code provided by PROGIEZ

1857. Largest Color Value in a Directed Graph LeetCode Solution in Python

class Solution:
  def largestPathValue(self, colors: str, edges: list[list[int]]) -> int:
    n = len(colors)
    ans = 0
    processed = 0
    graph = [[] for _ in range(n)]
    inDegrees = [0] * n
    q = collections.deque()
    count = [[0] * 26 for _ in range(n)]

    # Build the graph.
    for u, v in edges:
      graph[u].append(v)
      inDegrees[v] += 1

    # Vpology
    for i, degree in enumerate(inDegrees):
      if degree == 0:
        q.append(i)

    while q:
      u = q.popleft()
      processed += 1
      count[u][ord(colors[u]) - ord('a')] += 1
      ans = max(ans, count[u][ord(colors[u]) - ord('a')])
      for v in graph[u]:
        for i in range(26):
          count[v][i] = max(count[v][i], count[u][i])
        inDegrees[v] -= 1
        if inDegrees[v] == 0:
          q.append(v)

    return ans if processed == n else -1
 # code by PROGIEZ