1857. Largest Color Value in a Directed Graph

Hash Table Dynamic Programming Graph Topological Sort Memoization Counting

Time: O(n + E)

Space: O(n)

Intuition

Topological sort on directed graph of character dependencies. For each edge (a->b): must use b before a (b has smaller color). Find max score path.

Algorithm

1Topological sort (Kahn's). dp[node][c] = max count of color c on any path ending at node.
2Propagate DP along edges. Answer = max over all (node, color).

Common Pitfalls

•If cycle exists: return -1. Score = maximum color frequency on any path.

1857.cs

// Approach: Topological sort (Kahn's); DP tracks max frequency of each color along paths; detect cycles.
// Time: O(n + E) Space: O(n)

public class Solution
{
    public int LargestPathValue(string colors, int[][] edges)
    {
        int n = colors.Length;
        List<int>[] adjList = new List<int>[n];
        int[] inDegrees = new int[n];
        int[,] count = new int[n, 26];

        for (int i = 0; i < n; i++)
            adjList[i] = new List<int>();

        foreach (int[] edge in edges)
        {
            int u = edge[0];
            int v = edge[1];
            adjList[u].Add(v);
            inDegrees[v]++;
        }

        Queue<int> q = new Queue<int>();
        for (int i = 0; i < n; i++)
        {
            if (inDegrees[i] == 0)
                q.Enqueue(i);
        }

        int ans = 0, processed = 0;
        while (q.Count > 0)
        {
            int item = q.Dequeue();
            ans = Math.Max(ans, ++count[item, colors[item] - 'a']);
            ++processed;

            foreach (int adjNode in adjList[item])
            {
                inDegrees[adjNode]--;
                if (inDegrees[adjNode] == 0)
                    q.Enqueue(adjNode);

                for (int i = 0; i < 26; i++)
                    count[adjNode, i] = Math.Max(count[adjNode, i], count[item, i]);
            }
        }

        return processed == n ? ans : -1;
    }
}

Was this solution helpful?