Largest Color Value in a Directed Graph

🔁 Problem Restatement (in simpler terms)

You are given:

• A directed graph with n nodes.
• Each node i has a color, colors[i] ∈ {a-z}.
• Each path from one node to another has a color frequency – how many times each color appears.
• You want the maximum frequency of any single color on any valid path.
• If there is a cycle, return -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).

🧠 What is a path?

A path is a sequence of nodes:

 x₁ → x₂ → x₃ → ... → xₖ

Now suppose the colors string is:

colors = "abaca" → so:

• node 0 → 'a'
• node 1 → 'b'
• node 2 → 'a'
• node 3 → 'c'
• node 4 → 'a'

And your edges are:

edges = [[0,1],[0,2],[2,3],[3,4]]

Let’s pick a path:

0 → 2 → 3 → 4

On this path, the colors are:

• node 0 = 'a'
• node 2 = 'a'
• node 3 = 'c'
• node 4 = 'a'

So the color frequency for this path is:

• 'a': 3 times
• 'c': 1 time

✅ What this does imply:

You need to consider all possible valid paths in the graph, because:

• The largest color value might only appear on one specific path.
• So, your algorithm must effectively evaluate all valid paths to compare their results.

✅ Example:

Let’s say:

• colors = "abaca"
• edges = [[0,1],[0,2],[2,3],[3,4]]
• Path: 0 → 2 → 3 → 4

Instead of tracking that whole path, you just do:

0  1  2  3  4
a  b  a  c  a


@ node 0,
Start with colorCount[0]['a'] = 1


Move to node 2:
it’s also 'a' → colorCount[2]['a'] = 2


Move to node 3: 
it's 'c' → colorCount[3]['c'] = 1
but no update on 'a' as colorCount[3]['a'] = 2

Move to 4: it's 'a' → colorCount[4]['a'] = 3

Done. You got the best possible counts, no path-tracking needed.

🧠 Why not 1D array ?

1D tells you nothing about which color that count corresponds to.

⚠️ The core issue:

You need to track all 26 colors separately at each node,

because any one of them might be the one with the max frequency on the best path.

🧪 Example to show why 1D fails:

Let’s say:

• Node 0 is 'a'
• Node 1 is 'b'
• Node 2 is 'a'

Suppose two paths go to node 2:

• Path 1: 0 → 2, gives color frequency 'a': 2
• Path 2: 1 → 2, gives color frequency 'a': 1, 'b': 1

With 1D, you might store:

colorCount[2] = 2

But:

• You don’t know which color made that count 2.
• And you lose the information that color 'b' appeared once on some path.

That matters because future nodes need to know not just the count, but which color had that count so they can update their own color-specific counts.

✅ Why 2D works:

colorCount[node][colorIndex] = max number of times color c appears on any path ending at node

• You have n nodes and 26 colors → n x 26 matrix
• This lets you propagate and update color frequencies correctly, color by color.

🧠 Analogy:

Think of it like tracking the highest GPA in every subject per student:

• 1D: just one number — tells you GPA but not which subject.
• 2D: GPA per subject — now you can compare and update Math, English, CS individually.

/**
 * @param {string} colors
 * @param {number[][]} edges
 * @return {number}
 */
var largestPathValue = function(colors, edges) {
    const n = colors.length
    const indegrees = new Array(n).fill(0)
    const graph = new Array(n).fill(0).map(o => [])
    const colorCounts = new Array(n).fill(0).map(o => new Array(26).fill(0))
    let maxColorCode = 0

for(let [prereq, course] of edges){
    indegrees[course]++
    graph[prereq].push(course)
}

const queue = []
for(let i = 0 ; i < indegrees.length; i++){
  if(indegrees[i] === 0){
   queue.push(i)
   }
}

function updateColorCode(node) {
    let colorIndex = colors.charCodeAt(node) - 97
    colorCode[node][colorIndex]++
    maxColorCode = Math.max(maxColorCode, colorCode[node][colorIndex])
}

let visited = 0
while (0 < queue.length) {
    const node = queue.shift()
    visited++
    updateColorCode(node)

    for (let neighbour of graph[node]) {     

for (let color = 0; color < 26; color++) {
   colorCounts[neighbour][color] = Math.max(colorCounts[neighbour][color], colorCounts[node][color])
}

        indegrees[neighbour]--
        if (indegrees[neighbour] === 0) {
            queue.push(neighbour)
        }
    }
}

Final Space Complexity:

1. indegrees O(N)
2. graph O(N + E)
3. colorCounts O(N × 26) = O(N)
4. queue O(N)
5. Total O(N + E)

Because 26 is constant → drops out in Big-O notation.

Space Complexity = O(N + E)

(where N = number of nodes, E = number of edges)

Final Time Compelxity:

1. Build graph, indegreesO(E)
2. Topological sort O(N + E)
3. Color propagation per edge O(E × 26) = O(E)
4. Node-level color updateO(N)

Total O(N+E)