[Leetcode] 1857. Largest Color Value in a Directed Graph

https://leetcode.com/problems/largest-color-value-in-a-directed-graph/description/?envType=daily-question&envId=2025-05-26

initial

a very hard question
so i got a hint of topo sort but how do we "propagate" or remember the previous path's character frequency? I thought of putting counter inside the queue's element and popping it with the node but its impossible.

sol

instead, we should use a 2d dp table where
dp[i][c] = maximum number of times colour c appears on a valid path ending on node i.

in simple terms, how many times have we seen this colour c on a path ending on node i?

So lets take for example

0 → 2 → 3 → 4
a     a     c     a

dp[4][a] = dp[3][a] + 1 (+1 cuz its char a itself)
dp[4][c] = dp[4][c]

another example is
Let's say:

Node 2 gets color 'a'

Its predecessor (node 0) had 1 'a'

So:
dp[2]['a'] = max(dp[2]['a'], dp[0]['a']) + (colors[2] == 'a' ? 1 : 0) = 1 + 1 = 2

The answer is max value of dp[i][c] in any i. So we should update ans whenever updating dp[i][c].

2 things to noe:
1) notice that we are updating the dp value of neighbours too!! thats cuz we have the from and to node (to node is neigh bour node and from node is the node that we just popped from queue)

2) to detect a cycle, if number of nodes popped from queue isnt equal to n, then there is a cycle. This is cuz if theres a cycle, their indegree will never be 0 so we can process those nodes.

sol

class Solution {
    public int largestPathValue(String colors, int[][] edges) {
        Queue<Integer> queue = new LinkedList<>();
        int n = colors.length();
        int[] indegree=new int[n];
        int count=0;
        int ans =0;
        List<List<Integer>> graph = new ArrayList<>();
        for(int i=0;i<n;i++){
            graph.add(new ArrayList<>());
        }

        for(int[] edge:edges){
            int a = edge[0], b = edge[1];
            indegree[b]+=1;
            graph.get(a).add(b);
        }
        int[][] dp = new int[n][26];
        for(int i=0;i<n;i++){
            if(indegree[i]==0) queue.offer(i);
        }
        while(!queue.isEmpty()){
            int node = queue.poll();
            count+=1;
            char c = colors.charAt(node);
            dp[node][c-'a']+=1;
            ans=Math.max(ans, dp[node][c-'a']);
            for(int neigh:graph.get(node)){
                for(int i =0; i<26;i++){
                    dp[neigh][i]=Math.max(dp[neigh][i], dp[node][i]);
                }
                indegree[neigh]-=1;
                if(indegree[neigh]==0) queue.offer(neigh);
            }
        }
        return count==n? ans:-1;
    }
}

complexity

n time
n*(n-1) space?

nope
time is v+e
cuz the topo sort processes each node and edge once

space is for graph, we have n lists for each of the n node and across those lists, we store m edges.
Notice we are not storing m edge per list, but we are storing m edges across n lists.
So its n+m space (v+e)