Largest Color Value in a Directed Graph

🎯

Largest Color Value in a Directed Graph

hardGRAPHGoogleAmazon

Imagine you have a complex project with tasks represented as nodes, each task painted a color. You want to find the maximum number of times a single color appears along any valid sequence of tasks respecting dependencies.

💡 This problem combines graph traversal with counting frequencies along paths. Beginners often struggle because it requires detecting cycles, performing topological sorting, and tracking color counts simultaneously, which is more complex than standard graph problems.

📋

Problem Statement

Given a directed graph with n nodes labeled from 0 to n-1, each node has a color represented by a lowercase English letter. The graph is described by a list of directed edges. A path's color value is the maximum number of occurrences of any single color along that path. Return the largest color value of any valid path in the graph. If the graph contains a cycle, return -1.

1 ≤ n ≤ 10^5colors.length == ncolors consists of lowercase English letters0 ≤ edges.length ≤ 10^5edges[i].length == 20 ≤ edges[i][0], edges[i][1] < n

💡

Example

Input"colors = \"abaca\", edges = [[0,1],[0,2],[2,3],[3,4]]"

Output3

The path 0 -> 2 -> 3 -> 4 has colors 'a', 'a', 'c', 'a'. The color 'a' appears 3 times, which is the largest color value.

Input"colors = \"a\", edges = [[0,0]]"

Output-1

There is a cycle (0 -> 0), so return -1.

• Graph with a single node and no edges → output is 1
• Graph with multiple disconnected components → consider all components
• Graph with cycles → output is -1
• Graph where all nodes have the same color → output is length of longest path

⚠️

Common Mistakes

Not detecting cycles properly

Algorithm may enter infinite recursion or produce incorrect results

✅ Use in-degree counts and topological sort or track recursion stack states

Counting colors incorrectly by not aggregating from neighbors

Underestimates color counts, leading to wrong maximum values

✅ When processing a node, update color counts by taking max with neighbors' counts plus current node's color

Using recursion without memoization

Excessive recomputation causes timeouts

✅ Cache results for each node after first computation

Not handling disconnected components

Misses paths in isolated subgraphs, leading to incorrect max color value

✅ Process all nodes, not just those reachable from a single start node

Incorrectly updating DP arrays leading to off-by-one errors

Final answer is off by one or incorrect

✅ Carefully increment color count for current node before propagating

🧠

Brute Force (DFS with Path Tracking)

💡 Starting with brute force helps understand the problem's complexity by trying all paths explicitly, which is intuitive but inefficient for large graphs.

Intuition

Try all possible paths from every node, track colors along the path, and record the maximum frequency of any color. If a cycle is detected during traversal, return -1.

Algorithm

1. For each node, perform a DFS to explore all paths starting from it.
2. Track the frequency of colors along the current path.
3. If a cycle is detected (node revisited in current path), return -1.
4. Update the global maximum color frequency found on any path.

💡 This approach is straightforward but the exponential number of paths makes it impractical for large inputs.

</>

Code

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)

def largestPathValue(colors, edges):
    n = len(colors)
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    max_color_value = [0]  # Use list to allow updates inside dfs
    visited = [0] * n  # 0=unvisited,1=visiting,2=visited

    def dfs(node, path_colors):
        if visited[node] == 1:
            return -1  # cycle detected
        if visited[node] == 2:
            return 0  # already processed

        visited[node] = 1
        path_colors[colors[node]] += 1
        current_max = path_colors[colors[node]]

        for nei in graph[node]:
            res = dfs(nei, path_colors)
            if res == -1:
                return -1
            current_max = max(current_max, res)

        max_color_value[0] = max(max_color_value[0], current_max)
        path_colors[colors[node]] -= 1
        visited[node] = 2
        return current_max

    for i in range(n):
        res = dfs(i, defaultdict(int))
        if res == -1:
            return -1
    return max_color_value[0]

# Example usage
if __name__ == '__main__':
    print(largestPathValue("abaca", [[0,1],[0,2],[2,3],[3,4]]))  # Output: 3
    print(largestPathValue("a", [[0,0]]))  # Output: -1

Line Notes

sys.setrecursionlimit(10**7)Increase recursion limit to avoid stack overflow on deep recursion

visited = [0] * nTrack node states to detect cycles and avoid reprocessing

if visited[node] == 1:Detect cycle if node is currently in recursion stack

path_colors[colors[node]] += 1Increment count of current node's color along the path

max_color_value[0] = max(max_color_value[0], current_max)Update global max color value during DFS

import java.util.*;

public class LargestColorValue {
    public static int largestPathValue(String colors, int[][] edges) {
        int n = colors.length();
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] e : edges) graph.get(e[0]).add(e[1]);

        int[] visited = new int[n]; // 0=unvisited,1=visiting,2=visited
        int[] maxColorValue = new int[1];

        for (int i = 0; i < n; i++) {
            if (dfs(i, graph, colors, visited, new HashMap<>(), maxColorValue) == -1) return -1;
        }
        return maxColorValue[0];
    }

    private static int dfs(int node, List<List<Integer>> graph, String colors, int[] visited, Map<Character, Integer> pathColors, int[] maxColorValue) {
        if (visited[node] == 1) return -1; // cycle
        if (visited[node] == 2) return 0;

        visited[node] = 1;
        char c = colors.charAt(node);
        pathColors.put(c, pathColors.getOrDefault(c, 0) + 1);
        int currentMax = pathColors.get(c);

        for (int nei : graph.get(node)) {
            int res = dfs(nei, graph, colors, visited, pathColors, maxColorValue);
            if (res == -1) return -1;
            currentMax = Math.max(currentMax, res);
        }

        maxColorValue[0] = Math.max(maxColorValue[0], currentMax);
        pathColors.put(c, pathColors.get(c) - 1);
        if (pathColors.get(c) == 0) pathColors.remove(c);
        visited[node] = 2;
        return currentMax;
    }

    public static void main(String[] args) {
        System.out.println(largestPathValue("abaca", new int[][]{{0,1},{0,2},{2,3},{3,4}})); // 3
        System.out.println(largestPathValue("a", new int[][]{{0,0}})); // -1
    }
}

Line Notes

int[] visited = new int[n];Track node visitation state for cycle detection

if (visited[node] == 1) return -1;Detect cycle by revisiting node in current path

pathColors.put(c, pathColors.getOrDefault(c, 0) + 1);Increment color count for current path

maxColorValue[0] = Math.max(maxColorValue[0], currentMax);Update global max color value

pathColors.put(c, pathColors.get(c) - 1);Backtrack color count after DFS call

if (pathColors.get(c) == 0) pathColors.remove(c);Clean up map to avoid stale entries

#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<int>> graph;
string colors;
vector<int> visited; // 0=unvisited,1=visiting,2=visited
int maxColorValue = 0;

int dfs(int node, unordered_map<char,int>& pathColors) {
    if (visited[node] == 1) return -1; // cycle
    if (visited[node] == 2) return 0;

    visited[node] = 1;
    pathColors[colors[node]]++;
    int currentMax = pathColors[colors[node]];

    for (int nei : graph[node]) {
        int res = dfs(nei, pathColors);
        if (res == -1) return -1;
        currentMax = max(currentMax, res);
    }

    maxColorValue = max(maxColorValue, currentMax);
    pathColors[colors[node]]--;
    if (pathColors[colors[node]] == 0) pathColors.erase(colors[node]);
    visited[node] = 2;
    return currentMax;
}

int largestPathValue(string _colors, vector<vector<int>>& edges) {
    colors = _colors;
    n = colors.size();
    graph.assign(n, vector<int>());
    for (auto& e : edges) graph[e[0]].push_back(e[1]);
    visited.assign(n, 0);
    maxColorValue = 0;

    for (int i = 0; i < n; i++) {
        unordered_map<char,int> pathColors;
        int res = dfs(i, pathColors);
        if (res == -1) return -1;
    }
    return maxColorValue;
}

int main() {
    cout << largestPathValue("abaca", vector<vector<int>>{{0,1},{0,2},{2,3},{3,4}}) << "\n"; // 3
    cout << largestPathValue("a", vector<vector<int>>{{0,0}}) << "\n"; // -1
    return 0;
}

Line Notes

visited.assign(n, 0);Initialize visitation states for all nodes

if (visited[node] == 1) return -1;Cycle detection by checking recursion stack

pathColors[colors[node]]++;Count current node's color in path

maxColorValue = max(maxColorValue, currentMax);Update global maximum color count

pathColors[colors[node]]--;Backtrack color count after DFS call

if (pathColors[colors[node]] == 0) pathColors.erase(colors[node]);Remove color entry if count is zero

function largestPathValue(colors, edges) {
    const n = colors.length;
    const graph = Array.from({length: n}, () => []);
    for (const [u, v] of edges) graph[u].push(v);

    const visited = new Array(n).fill(0); // 0=unvisited,1=visiting,2=visited
    let maxColorValue = 0;

    function dfs(node, pathColors) {
        if (visited[node] === 1) return -1; // cycle
        if (visited[node] === 2) return 0;

        visited[node] = 1;
        pathColors.set(colors[node], (pathColors.get(colors[node]) || 0) + 1);
        let currentMax = pathColors.get(colors[node]);

        for (const nei of graph[node]) {
            const res = dfs(nei, pathColors);
            if (res === -1) return -1;
            currentMax = Math.max(currentMax, res);
        }

        maxColorValue = Math.max(maxColorValue, currentMax);
        pathColors.set(colors[node], pathColors.get(colors[node]) - 1);
        if (pathColors.get(colors[node]) === 0) pathColors.delete(colors[node]);
        visited[node] = 2;
        return currentMax;
    }

    for (let i = 0; i < n; i++) {
        const pathColors = new Map();
        const res = dfs(i, pathColors);
        if (res === -1) return -1;
    }
    return maxColorValue;
}

// Example usage
console.log(largestPathValue("abaca", [[0,1],[0,2],[2,3],[3,4]])); // 3
console.log(largestPathValue("a", [[0,0]])); // -1

Line Notes

const visited = new Array(n).fill(0);Track node states to detect cycles and avoid reprocessing

if (visited[node] === 1) return -1;Detect cycle if node is currently in recursion stack

pathColors.set(colors[node], (pathColors.get(colors[node]) || 0) + 1);Increment count of current node's color along the path

maxColorValue = Math.max(maxColorValue, currentMax);Update global maximum color count

pathColors.set(colors[node], pathColors.get(colors[node]) - 1);Backtrack color count after DFS call

if (pathColors.get(colors[node]) === 0) pathColors.delete(colors[node]);Remove color entry if count is zero

⏱

Complexity

TimeO(n * (n + e)) in worst case due to exploring all paths

SpaceO(n) recursion stack + O(n) for path color counts

DFS explores all paths from each node, which can be exponential in worst case due to repeated paths and no memoization.

💡 For n=20, this could mean billions of operations, making it impractical for large inputs.

Interview Verdict: TLE

This approach is too slow for large graphs but is useful to understand the problem and why optimization is needed.

🧠

Topological Sort + DFS with Memoization

💡 Memoization avoids recomputing results for nodes by caching, drastically improving efficiency over brute force.

Intuition

Perform a topological sort to process nodes in dependency order, then use DFS with memoization to compute the largest color value starting from each node.

Algorithm

1. Build the graph and compute in-degree for each node.
2. Perform topological sort to detect cycles and get processing order.
3. Use DFS with memoization to compute color counts for each node.
4. Return the maximum color count found or -1 if a cycle exists.

💡 Topological sort ensures no cycles and memoization prevents redundant DFS calls, making the approach efficient.

</>

Code

from collections import defaultdict, deque

def largestPathValue(colors, edges):
    n = len(colors)
    graph = defaultdict(list)
    indegree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    queue = deque([i for i in range(n) if indegree[i] == 0])
    topo_order = []
    while queue:
        node = queue.popleft()
        topo_order.append(node)
        for nei in graph[node]:
            indegree[nei] -= 1
            if indegree[nei] == 0:
                queue.append(nei)

    if len(topo_order) < n:
        return -1  # cycle detected

    memo = [None] * n

    def dfs(node):
        if memo[node] is not None:
            return memo[node]
        count = [0] * 26
        count[ord(colors[node]) - ord('a')] = 1
        for nei in graph[node]:
            nei_count = dfs(nei)
            for i in range(26):
                count[i] = max(count[i], nei_count[i] + (1 if i == ord(colors[node]) - ord('a') else 0))
        memo[node] = count
        return count

    max_color_value = 0
    for node in topo_order:
        counts = dfs(node)
        max_color_value = max(max_color_value, max(counts))

    return max_color_value

# Example usage
if __name__ == '__main__':
    print(largestPathValue("abaca", [[0,1],[0,2],[2,3],[3,4]]))  # 3
    print(largestPathValue("a", [[0,0]]))  # -1

Line Notes

indegree = [0] * nTrack number of incoming edges to detect cycles and start topological sort

queue = deque([i for i in range(n) if indegree[i] == 0])Initialize queue with nodes having no dependencies

if len(topo_order) < n:If not all nodes processed, a cycle exists

memo = [None] * nCache results of DFS to avoid recomputation

import java.util.*;

public class LargestColorValue {
    public static int largestPathValue(String colors, int[][] edges) {
        int n = colors.length();
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        int[] indegree = new int[n];
        for (int[] e : edges) {
            graph.get(e[0]).add(e[1]);
            indegree[e[1]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) if (indegree[i] == 0) queue.offer(i);

        List<Integer> topoOrder = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            topoOrder.add(node);
            for (int nei : graph.get(node)) {
                indegree[nei]--;
                if (indegree[nei] == 0) queue.offer(nei);
            }
        }

        if (topoOrder.size() < n) return -1;

        int[][] memo = new int[n][26];
        boolean[] visited = new boolean[n];

        int maxColorValue = 0;

        for (int node : topoOrder) {
            if (!visited[node]) dfs(node, graph, colors, memo, visited);
        }

        for (int i = 0; i < n; i++) {
            for (int c = 0; c < 26; c++) {
                maxColorValue = Math.max(maxColorValue, memo[i][c]);
            }
        }

        return maxColorValue;
    }

    private static void dfs(int node, List<List<Integer>> graph, String colors, int[][] memo, boolean[] visited) {
        visited[node] = true;
        int cIndex = colors.charAt(node) - 'a';
        memo[node][cIndex] = 1;
        for (int nei : graph.get(node)) {
            if (!visited[nei]) dfs(nei, graph, colors, memo, visited);
            for (int i = 0; i < 26; i++) {
                memo[node][i] = Math.max(memo[node][i], memo[nei][i] + (i == cIndex ? 1 : 0));
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(largestPathValue("abaca", new int[][]{{0,1},{0,2},{2,3},{3,4}})); // 3
        System.out.println(largestPathValue("a", new int[][]{{0,0}})); // -1
    }
}

Line Notes

int[] indegree = new int[n];Count incoming edges to detect cycles and start topological sort

if (topoOrder.size() < n) return -1;Cycle detected if topological sort doesn't include all nodes

int[][] memo = new int[n][26];Store max color counts for each node and color

memo[node][cIndex] = 1;Initialize count for current node's color

#include <bits/stdc++.h>
using namespace std;

int n;
string colors;
vector<vector<int>> graph;
vector<int> indegree;
vector<vector<int>> memo;
vector<bool> visited;

void dfs(int node) {
    visited[node] = true;
    int cIndex = colors[node] - 'a';
    memo[node][cIndex] = 1;
    for (int nei : graph[node]) {
        if (!visited[nei]) dfs(nei);
        for (int i = 0; i < 26; i++) {
            memo[node][i] = max(memo[node][i], memo[nei][i] + (i == cIndex ? 1 : 0));
        }
    }
}

int largestPathValue(string _colors, vector<vector<int>>& edges) {
    colors = _colors;
    n = colors.size();
    graph.assign(n, vector<int>());
    indegree.assign(n, 0);
    for (auto& e : edges) {
        graph[e[0]].push_back(e[1]);
        indegree[e[1]]++;
    }

    queue<int> q;
    for (int i = 0; i < n; i++) if (indegree[i] == 0) q.push(i);

    int count = 0;
    while (!q.empty()) {
        int node = q.front(); q.pop();
        count++;
        for (int nei : graph[node]) {
            indegree[nei]--;
            if (indegree[nei] == 0) q.push(nei);
        }
    }

    if (count < n) return -1; // cycle

    memo.assign(n, vector<int>(26, 0));
    visited.assign(n, false);

    for (int i = 0; i < n; i++) {
        if (!visited[i]) dfs(i);
    }

    int maxColorValue = 0;
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 26; c++) {
            maxColorValue = max(maxColorValue, memo[i][c]);
        }
    }
    return maxColorValue;
}

int main() {
    cout << largestPathValue("abaca", vector<vector<int>>{{0,1},{0,2},{2,3},{3,4}}) << "\n"; // 3
    cout << largestPathValue("a", vector<vector<int>>{{0,0}}) << "\n"; // -1
    return 0;
}

Line Notes

indegree.assign(n, 0);Initialize in-degree counts for cycle detection

if (count < n) return -1;Detect cycle if topological sort does not cover all nodes

memo.assign(n, vector<int>(26, 0));Initialize memo table for color counts

memo[node][cIndex] = 1;Set base count for current node's color

function largestPathValue(colors, edges) {
    const n = colors.length;
    const graph = Array.from({length: n}, () => []);
    const indegree = new Array(n).fill(0);
    for (const [u, v] of edges) {
        graph[u].push(v);
        indegree[v]++;
    }

    const queue = [];
    for (let i = 0; i < n; i++) if (indegree[i] === 0) queue.push(i);

    let count = 0;
    while (queue.length) {
        const node = queue.shift();
        count++;
        for (const nei of graph[node]) {
            indegree[nei]--;
            if (indegree[nei] === 0) queue.push(nei);
        }
    }

    if (count < n) return -1;

    const memo = Array.from({length: n}, () => new Array(26).fill(0));
    const visited = new Array(n).fill(false);

    function dfs(node) {
        visited[node] = true;
        const cIndex = colors.charCodeAt(node) - 97;
        memo[node][cIndex] = 1;
        for (const nei of graph[node]) {
            if (!visited[nei]) dfs(nei);
            for (let i = 0; i < 26; i++) {
                memo[node][i] = Math.max(memo[node][i], memo[nei][i] + (i === cIndex ? 1 : 0));
            }
        }
    }

    for (let i = 0; i < n; i++) {
        if (!visited[i]) dfs(i);
    }

    let maxColorValue = 0;
    for (let i = 0; i < n; i++) {
        for (let c = 0; c < 26; c++) {
            maxColorValue = Math.max(maxColorValue, memo[i][c]);
        }
    }
    return maxColorValue;
}

// Example usage
console.log(largestPathValue("abaca", [[0,1],[0,2],[2,3],[3,4]])); // 3
console.log(largestPathValue("a", [[0,0]])); // -1

Line Notes

const indegree = new Array(n).fill(0);Track incoming edges to detect cycles and start topological sort

if (count < n) return -1;Cycle detected if topological sort does not include all nodes

const memo = Array.from({length: n}, () => new Array(26).fill(0));Store max color counts per node and color

memo[node][cIndex] = 1;Initialize count for current node's color

⏱

Complexity

TimeO(n + e + 26 * (n + e)) ≈ O(n + e)

SpaceO(n + e + 26 * n) for graph, memo, and recursion stack

Topological sort takes O(n + e), DFS with memoization visits each node once, updating 26 color counts per node.

💡 For n=10^5 and e=10^5, this approach is efficient enough to run within time limits.

Interview Verdict: Accepted

This approach is efficient and practical for large inputs, making it the preferred solution in interviews.

🧠

Topological Sort + Iterative DP

💡 Using iterative DP with topological order avoids recursion and can be easier to implement in some languages or environments.

Intuition

Process nodes in topological order, updating color counts for each node based on its predecessors, and track the maximum color value iteratively.

Algorithm

1. Build graph and compute in-degree for each node.
2. Initialize a DP array to store max color counts per node and color.
3. Use a queue to perform topological sort iteratively.
4. For each node dequeued, update DP for its neighbors and track max color value.
5. If cycle detected (not all nodes processed), return -1.

💡 This approach uses the same logic as memoized DFS but avoids recursion by processing nodes in order.

</>

Code

from collections import defaultdict, deque

def largestPathValue(colors, edges):
    n = len(colors)
    graph = defaultdict(list)
    indegree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    dp = [[0]*26 for _ in range(n)]
    queue = deque([i for i in range(n) if indegree[i] == 0])
    count = 0
    max_color_value = 0

    while queue:
        node = queue.popleft()
        count += 1
        c_index = ord(colors[node]) - ord('a')
        dp[node][c_index] += 1
        max_color_value = max(max_color_value, dp[node][c_index])

        for nei in graph[node]:
            for i in range(26):
                dp[nei][i] = max(dp[nei][i], dp[node][i])
            indegree[nei] -= 1
            if indegree[nei] == 0:
                queue.append(nei)

    if count < n:
        return -1
    return max_color_value

# Example usage
if __name__ == '__main__':
    print(largestPathValue("abaca", [[0,1],[0,2],[2,3],[3,4]]))  # 3
    print(largestPathValue("a", [[0,0]]))  # -1

Line Notes

dp = [[0]*26 for _ in range(n)]Initialize DP table to track max color counts per node

queue = deque([i for i in range(n) if indegree[i] == 0])Start topological sort with nodes having zero in-degree

dp[node][c_index] += 1Increment count for current node's color

dp[nei][i] = max(dp[nei][i], dp[node][i])Propagate max color counts to neighbors

import java.util.*;

public class LargestColorValue {
    public static int largestPathValue(String colors, int[][] edges) {
        int n = colors.length();
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        int[] indegree = new int[n];
        for (int[] e : edges) {
            graph.get(e[0]).add(e[1]);
            indegree[e[1]]++;
        }

        int[][] dp = new int[n][26];
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) if (indegree[i] == 0) queue.offer(i);

        int count = 0, maxColorValue = 0;

        while (!queue.isEmpty()) {
            int node = queue.poll();
            count++;
            int cIndex = colors.charAt(node) - 'a';
            dp[node][cIndex]++;
            maxColorValue = Math.max(maxColorValue, dp[node][cIndex]);

            for (int nei : graph.get(node)) {
                for (int i = 0; i < 26; i++) {
                    dp[nei][i] = Math.max(dp[nei][i], dp[node][i]);
                }
                indegree[nei]--;
                if (indegree[nei] == 0) queue.offer(nei);
            }
        }

        return count < n ? -1 : maxColorValue;
    }

    public static void main(String[] args) {
        System.out.println(largestPathValue("abaca", new int[][]{{0,1},{0,2},{2,3},{3,4}})); // 3
        System.out.println(largestPathValue("a", new int[][]{{0,0}})); // -1
    }
}

Line Notes

int[][] dp = new int[n][26];DP table to store max color counts per node

Queue<Integer> queue = new LinkedList<>();Queue for iterative topological sort

dp[node][cIndex]++;Increment count for node's color

dp[nei][i] = Math.max(dp[nei][i], dp[node][i]);Update neighbor's DP with max counts

#include <bits/stdc++.h>
using namespace std;

int largestPathValue(string colors, vector<vector<int>>& edges) {
    int n = colors.size();
    vector<vector<int>> graph(n);
    vector<int> indegree(n, 0);
    for (auto& e : edges) {
        graph[e[0]].push_back(e[1]);
        indegree[e[1]]++;
    }

    vector<vector<int>> dp(n, vector<int>(26, 0));
    queue<int> q;
    for (int i = 0; i < n; i++) if (indegree[i] == 0) q.push(i);

    int count = 0, maxColorValue = 0;
    while (!q.empty()) {
        int node = q.front(); q.pop();
        count++;
        int cIndex = colors[node] - 'a';
        dp[node][cIndex]++;
        maxColorValue = max(maxColorValue, dp[node][cIndex]);

        for (int nei : graph[node]) {
            for (int i = 0; i < 26; i++) {
                dp[nei][i] = max(dp[nei][i], dp[node][i]);
            }
            indegree[nei]--;
            if (indegree[nei] == 0) q.push(nei);
        }
    }

    if (count < n) return -1;
    return maxColorValue;
}

int main() {
    cout << largestPathValue("abaca", vector<vector<int>>{{0,1},{0,2},{2,3},{3,4}}) << "\n"; // 3
    cout << largestPathValue("a", vector<vector<int>>{{0,0}}) << "\n"; // -1
    return 0;
}

Line Notes

vector<vector<int>> dp(n, vector<int>(26, 0));DP table for max color counts per node

queue<int> q;Queue for topological order processing

dp[node][cIndex]++;Increment count for current node's color

dp[nei][i] = max(dp[nei][i], dp[node][i]);Propagate max counts to neighbors

function largestPathValue(colors, edges) {
    const n = colors.length;
    const graph = Array.from({length: n}, () => []);
    const indegree = new Array(n).fill(0);
    for (const [u, v] of edges) {
        graph[u].push(v);
        indegree[v]++;
    }

    const dp = Array.from({length: n}, () => new Array(26).fill(0));
    const queue = [];
    for (let i = 0; i < n; i++) if (indegree[i] === 0) queue.push(i);

    let count = 0, maxColorValue = 0;
    while (queue.length) {
        const node = queue.shift();
        count++;
        const cIndex = colors.charCodeAt(node) - 97;
        dp[node][cIndex]++;
        maxColorValue = Math.max(maxColorValue, dp[node][cIndex]);

        for (const nei of graph[node]) {
            for (let i = 0; i < 26; i++) {
                dp[nei][i] = Math.max(dp[nei][i], dp[node][i]);
            }
            indegree[nei]--;
            if (indegree[nei] === 0) queue.push(nei);
        }
    }

    return count < n ? -1 : maxColorValue;
}

// Example usage
console.log(largestPathValue("abaca", [[0,1],[0,2],[2,3],[3,4]])); // 3
console.log(largestPathValue("a", [[0,0]])); // -1

Line Notes

const dp = Array.from({length: n}, () => new Array(26).fill(0));DP table to track max color counts per node

const queue = [];Queue for iterative topological sort

dp[node][cIndex]++;Increment count for current node's color

dp[nei][i] = Math.max(dp[nei][i], dp[node][i]);Update neighbor's DP with max counts

⏱

Complexity

TimeO(n + e + 26 * (n + e)) ≈ O(n + e)

SpaceO(n + e + 26 * n) for graph, DP table, and queue

Topological sort and DP updates each node and edge once, updating 26 color counts per node.

💡 This approach is efficient and avoids recursion, suitable for large graphs.

Interview Verdict: Accepted

Iterative DP with topological sort is a robust and interview-friendly solution.

📊

All Approaches - One-Glance Tradeoffs

💡 Approach 2 or 3 are best for interviews due to efficiency and clarity; brute force is only for initial explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n * (n + e)) exponential worst case	O(n) recursion stack + O(n) path colors	Yes (deep recursion)	No	Mention only - never code
2. Topological Sort + DFS with Memoization	O(n + e)	O(n + e + 26*n) for memo and graph	Possible but less likely with memoization	Yes	Preferred solution to code
3. Topological Sort + Iterative DP	O(n + e)	O(n + e + 26*n)	No	Yes	Good alternative to recursion

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem constraints and ask about cycles.Step 2: Present brute force DFS with path tracking to show understanding.Step 3: Explain inefficiency and introduce topological sort with memoized DFS.Step 4: Discuss iterative DP as an alternative to recursion.Step 5: Analyze time and space complexity and handle edge cases.

Time Allocation

Clarify: 3min → Approach: 7min → Code: 15min → Test: 5min. Total ~30min

What the Interviewer Tests

Ability to detect cycles, perform topological sort, combine graph traversal with frequency counting, and optimize with memoization or DP.

Common Follow-ups

• What if colors are not limited to 26 letters? → Use hash maps instead of fixed arrays.
• Can you return the actual path with the largest color value? → Track predecessors during DP.

💡 These follow-ups test adaptability to variations and ability to extend solutions beyond the base problem.

🔍

Pattern Recognition

When to Use

1) Problem involves directed graph with dependencies, 2) Need to detect cycles, 3) Need to find max frequency or count along paths, 4) Colors or labels affect path values.

Signature Phrases

largest color valuedirected graphcycle detectiontopological order

NOT This Pattern When

Problems that only require simple BFS/DFS without cycle detection or path aggregation are different.

Similar Problems

Course Schedule II - also uses topological sort and cycle detectionLongest Path in a DAG - similar path-based DP on DAGAlien Dictionary - topological sort with character ordering

Practice

1. You are given a directed graph where each node represents a state, and edges represent transitions. Some states lead to cycles, while others eventually lead to terminal states with no outgoing edges. Which algorithmic approach guarantees finding all states that are "eventually safe" (i.e., cannot reach any cycle) in an efficient manner?

easy

A. Use a greedy approach to repeatedly remove nodes with no outgoing edges until no nodes remain.

B. Construct the reverse graph and apply Kahn's algorithm (topological sort using in-degree) to identify safe nodes.

C. Apply dynamic programming with memoization on node states to mark safe and unsafe nodes.

D. Perform a brute force DFS from each node to detect cycles and mark safe nodes accordingly.

Solution

1. Step 1: Understand problem requirements

   The problem requires identifying nodes that cannot reach any cycle, i.e., nodes that eventually lead to terminal nodes.

2. Step 2: Recognize optimal approach

   Reversing the graph and applying Kahn's algorithm on in-degree allows us to efficiently find all nodes that lead to terminal nodes by processing nodes with zero out-degree in the original graph.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Reverse graph + Kahn's algorithm is the known optimal solution for eventual safe states [OK]

Hint: Reverse graph + Kahn's algorithm finds safe nodes efficiently [OK]

Common Mistakes:

• Confusing brute force DFS with optimal topological approach
• Assuming greedy removal without reversing graph suffices
• Misapplying DP without graph reversal

2. Consider the following buggy implementation of Kahn's Algorithm for course scheduling. Which line contains the subtle bug that can cause incorrect or infinite behavior?

medium

A. Line 6: graph[a].append(b) -- edge direction reversed

B. Line 7: in_degree[a] += 1 -- incorrect in-degree increment

C. Line 10: queue initialization -- wrong nodes enqueued

D. Line 15: in_degree[nei] -= 1 -- decrementing in-degree incorrectly

Solution

1. Step 1: Analyze edge construction

   Prerequisite pairs are (a, b) meaning b -> a edge; reversing to graph[a].append(b) flips direction.

2. Step 2: Consequences of reversed edges

   In-degree counts and BFS queue become invalid, causing wrong order or infinite loop.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct edge direction is critical for topological sort correctness [OK]

Hint: Check edge direction carefully when building graph [OK]

Common Mistakes:

• Reversing edges when building adjacency list
• Incrementing in-degree on wrong node
• Forgetting to decrement in-degree

3. Suppose the problem is modified so that edges can be dynamically added or removed, and you need to repeatedly query which nodes are eventually safe after each update. Which approach is best suited to efficiently handle these dynamic queries?

hard

A. Maintain in-degree counts and update them incrementally, adjusting the queue of safe nodes dynamically.

B. Use a DFS with memoization approach and invalidate memoization only for affected nodes after each update.

C. Re-run the entire reversed graph + Kahn's algorithm from scratch after each update.

D. Use a brute force DFS cycle detection from every node after each update.

Solution

1. Step 1: Understand dynamic graph updates

   Recomputing from scratch is expensive; brute force DFS is too slow for repeated queries.

2. Step 2: Incremental in-degree updates

   Maintaining in-degree counts and adjusting the queue of safe nodes incrementally allows efficient updates without full recomputation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incremental updates leverage Kahn's algorithm structure for dynamic graphs [OK]

Hint: Incremental in-degree updates enable efficient dynamic queries [OK]

Common Mistakes:

• Re-running full algorithm after each update
• Using brute force DFS repeatedly
• Invalidating all memoization unnecessarily

4. Suppose the problem is modified so that some courses can be taken multiple times (repeatedly) and prerequisites must be satisfied each time before retaking. Which of the following statements about adapting the BFS topological sort approach is correct?

hard

A. We should switch to a dynamic programming approach because BFS topological sort cannot handle repeated courses.

B. The original BFS topological sort can be used without changes since it handles cycles by returning -1.

C. We can use BFS topological sort by resetting indegrees after each semester and reprocessing courses as needed.

D. The problem becomes invalid because repeated courses create cycles; BFS topological sort cannot be applied directly.

Solution

1. Step 1: Understand repeated courses and prerequisites

   Allowing repeated courses with prerequisites means cycles can form because a course depends on itself indirectly.

2. Step 2: Analyze BFS topological sort applicability

   BFS topological sort requires a DAG; cycles break this assumption, so it cannot be applied directly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Repeated courses induce cycles -> BFS topological sort invalid [OK]

Hint: Repeated courses create cycles, breaking DAG assumption [OK]

Common Mistakes:

• Assuming BFS topological sort handles cycles by returning -1
• Thinking resetting indegrees can simulate repeats correctly
• Believing DP is always needed without analyzing graph structure

5. Suppose the problem is modified so that elements in the sequences can be reused multiple times (i.e., sequences may contain repeated elements). Which of the following changes to the DFS postorder topological sort approach is necessary to correctly determine if the original sequence can be uniquely reconstructed?

hard

A. No changes needed; the existing DFS approach handles repeated elements naturally.

B. Modify graph construction to allow multiple edges between the same nodes and adjust cycle detection accordingly.

C. Switch to BFS topological sort with a queue that tracks in-degree counts considering repeated edges.

D. Preprocess sequences to remove duplicates before building the graph, then run the original DFS approach.

Solution

1. Step 1: Understand impact of repeated elements

   Repeated elements mean multiple edges between same nodes may exist, affecting graph structure and cycle detection.

2. Step 2: Adjust graph and DFS accordingly

   Graph must allow multiple edges or count edge multiplicity; cycle detection must consider these to avoid false negatives or infinite recursion.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Handling repeated edges is essential for correctness with reused elements [OK]

Hint: Repeated elements require multi-edge aware graph and cycle detection [OK]

Common Mistakes:

• Assuming no changes needed
• Removing duplicates loses info
• Switching to BFS without handling repeats