1857. Largest Color Value in a Directed Graph

HardGraphTopological SortMemoizationHash TableDynamic ProgrammingCounting
Leetcode Link

Problem Description

In this problem, we are given a directed graph with n nodes, each node having its own color represented by a lowercase letter. Edges in the graph are represented by an array of tuples, each tuple representing a directed edge from one node to another.

The objective is to find the largest color value of any valid path within the graph. A valid path is a sequence of nodes connected by directed edges, and the color value of this path is the number of nodes in that path having the most common color. However, if the graph has a cycle, then there is no largest color value, and we have to return -1.

Intuition

The solution's intuition is based on two main concepts:

  1. Topological Sorting:

    • A valid path cannot contain cycles. Thus, we can use topological sorting to check for cycles and, if there are none, process the nodes in a way that each node is considered after all the nodes leading to it.
    • Since a topological ordering respects the direction of edges, we can dynamically calculate the largest color value for each node in that order.

  2. Dynamic Programming:

    • We can maintain a 2D array dp, where dp[i][c] will represent the maximum number of nodes with color c that we can achieve by traveling to node i through any path.
    • As we process the graph in topological order, we can update the dp values for a node by considering all dp values from its predecessor nodes plus one if the current node has the same color.

By combining these two concepts, the algorithm populates the dp table while performing a topological sort. If it goes through all nodes without encountering a cycle, it returns the maximum value from the dp table. If a cycle is detected (by checking if the number of processed nodes is less than n), it returns -1. This approach ensures that we find the path with the largest color value while also checking for cycles in a directed graph.

Learn more about Graph, Topological Sort, Memoization and Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What are the most two important steps in writing a depth first search function? (Select 2)

Solution Approach

The given solution implements a combination of topological sorting and dynamic programming. Here is a breakdown of the solution approach step by step:

  1. Initialization:

    • The number of nodes n is determined by the length of the colors string.
    • An array indeg is created to track the in-degree (number of incoming edges) of each node.
    • A graph g is represented using a defaultdict of lists. It will store all outbound edges for each node.
    • A 2D array dp is used for dynamic programming, with dp[i][c] representing the number of times color c appears on the best path ending at node i.

  2. Building the Graph and Calculating In-Degrees:

    • For each directed edge in edges, the graph g is updated, and the in-degree indeg[b] is incremented for the destination node b.

  3. Preparation for Topological Sort:

    • A queue q is used to store all nodes with an in-degree of 0 (nodes with no incoming edges).
    • The 2D array dp is then updated for each of these starting nodes, setting the count of their respective colors to 1 (since each color appears at least once at the starting node).

  4. Topological Sort and Dynamic Programming:

    • A variable cnt is used to count the number of nodes processed.
    • The algorithm processes nodes in the queue, following a topological order. When a node i is popped from the queue, it's considered 'visited'.
    • For each adjacent node j of node i, the algorithm decreases the in-degree of node j by 1.
    • When the in-degree of node j reaches 0, it's ready to be processed, so it's added to the queue.
    • The dp table is updated for node j using the dp values of node i. If the color of node j is the same as one considered in the loop, the count is incremented by 1.
    • The value of the most frequent color (maximum color value) seen so far is updated by comparing dp[j][k] with ans.

  5. Checking for Cycles and Returning the Result:

    • If the number of nodes processed (cnt) is less than n, this implies that the graph contains a cycle, and in such cases, -1 is returned.
    • Otherwise, the graph doesn't contain any cycles, and the largest color value found, stored in ans, is returned.

The solution employs a breadth-first search (BFS) to ensure the topological order and dynamically updates the path color values, efficiently combining the graph traversal with the dynamic programming principles to solve the problem.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Example Walkthrough

Let's go through a small example using the solution approach described above.

Given:

  • A graph with the following edges: edges = [(0,1), (1,2), (0,2)]
  • Each node has a color, represented in an array: colors = ["r", "g", "r"]

Our task is to find the largest color value of any valid path.

Step-by-step solution:

  1. Initialization:

    • The number of nodes n is 3 (length of the colors array).
    • Initialize indeg as [0, 0, 0] to track the in-degree of each node.
    • Create a graph g using a dictionary, which will map each node to its outbound edges (i.e., g = {0: [1, 2], 1: [2], 2: []}).
    • Prepare the dp array with 0 values, with dimensions [n][number_of_unique_colors], which for simplicity will be [3][2] for "r" and "g" and set it all to 0s, for now, dp = [[0, 0], [0, 0], [0, 0]].

  2. Building the Graph and Calculating In-Degrees:

    • For the edge (0,1), add 1 to indeg[1]. For the edge (1,2), add 1 to indeg[2]. For the edge (0,2), add 1 to indeg[2] again. Now, indeg becomes [0, 1, 2].

  3. Preparation for Topological Sort:

    • Place node 0 in queue q because indeg[0] is 0.
    • Update the dp table for node 0, set dp[0][color_index_of_r] to 1, as "r" is the color of node 0. Hence, dp = [[1, 0], [0, 0], [0, 0]].

  4. Topological Sort and Dynamic Programming:

    • Set cnt = 0. Process nodes in the topological order using BFS.
    • Pop 0 from q, increment cnt to 1.
    • Node 0 connects to nodes 1 and 2. Decrease indeg[1] and indeg[2] by 1. Now, indeg = [0, 0, 1].
    • Node 1 now has an in-degree of 0, so add it to q.
    • Pop 1 from q, increment cnt to 2.
    • Update dp[1][color_index_of_g] to 1 (color of node 1) and dp[1][color_index_of_r] to dp[0][color_index_of_r], since node 0's color "r" contributes to the path color value. Now, dp = [[1, 0], [1, 1], [0, 0]].
    • Node 1 connects to node 2. Decrease indeg[2] to 0. Add node 2 to q.
    • Pop 2 from q, increment cnt to 3.
    • Update dp[2][color_index_of_r] to max(dp[0][color_index_of_r], dp[1][color_index_of_r]) + 1 because node 2's color is "r" and it's connected to nodes 0 and 1. Now, dp = [[1, 0], [1, 1], [2, 0]].
    • The value of ans is the max value found in dp, which is 2 (from dp[2][color_index_of_r]).

  5. Checking for Cycles and Returning the Result:

    • The number of nodes processed (cnt) is 3, which equals n, so there are no cycles.
    • The graph doesn't contain any cycles, so we return the largest color value, which is 2.

Finally, according to our example, the largest color value found in any valid path in the graph is 2, corresponding to the color "r".

Solution Implementation

1from collections import defaultdict, deque
2
3class Solution:
4    def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
5        # Number of nodes
6        num_nodes = len(colors)
7      
8        # Incoming degree count for each node
9        incoming_degree = [0] * num_nodes
10      
11        # Adjacency list representation of graph
12        graph = defaultdict(list)
13      
14        # Building graph and updating the incoming degree for each node
15        for start, end in edges:
16            graph[start].append(end)
17            incoming_degree[end] += 1
18
19        # Queue for BFS
20        queue = deque()
21      
22        # Dynamic Programming table: dp[node][color] will store the maximum path value for color at node
23        dp = [[0] * 26 for _ in range(num_nodes)]
24      
25        # Initialize queue with nodes having zero incoming degree and update dp for their color
26        for node, degree in enumerate(incoming_degree):
27            if degree == 0:
28                queue.append(node)
29                color_index = ord(colors[node]) - ord('a')
30                dp[node][color_index] += 1
31
32        # Count of nodes processed
33        processed_count = 0
34      
35        # Variable to keep track of the maximum path value found so far
36        max_path_value = 1
37      
38        # BFS traversal of graph
39        while queue:
40            current_node = queue.popleft()
41            processed_count += 1
42          
43            # Iterate over all the nodes that can be reached from the current node
44            for neighbor in graph[current_node]:
45                # Decrement incoming degree for the neighboring node
46                incoming_degree[neighbor] -= 1
47              
48                # If the neighbor has no more incoming edges, add it to the queue
49                if incoming_degree[neighbor] == 0:
50                    queue.append(neighbor)
51              
52                neighbor_color_index = ord(colors[neighbor]) - ord('a')
53              
54                # Update the dp table with maximum path values and check if the current path
55                # creates a new maximum for the color at the neighbor node
56                for color in range(26):
57                    # Increment path value if color matches the neighbor's color
58                    dp[neighbor][color] = max(dp[neighbor][color], dp[current_node][color] + (neighbor_color_index == color))
59                  
60                    # Update the maximum path value found so far
61                    max_path_value = max(max_path_value, dp[neighbor][color])
62
63        # If the processed count is less than the total number of nodes, there exists a cycle; return -1
64        return -1 if processed_count < num_nodes else max_path_value
65
1class Solution {
2    public int largestPathValue(String colors, int[][] edges) {
3        int numVertices = colors.length();
4        List<Integer>[] adjacencyList = new List[numVertices];
5      
6        // Initialize adjacency list
7        Arrays.setAll(adjacencyList, element -> new ArrayList<>());
8      
9        // Array to keep track of indegree of each vertex
10        int[] indegree = new int[numVertices];
11
12        // Build the adjacency list and update the indegree of each vertex
13        for (int[] edge : edges) {
14            int fromVertex = edge[0], toVertex = edge[1];
15            adjacencyList[fromVertex].add(toVertex);
16            ++indegree[toVertex];
17        }
18      
19        // Deque for BFS (Breadth-First Search) traversal
20        Deque<Integer> queue = new ArrayDeque<>();
21      
22        // DP array to keep track of maximum color count at each vertex
23        int[][] maxColorCountAtVertex = new int[numVertices][26];
24      
25        // Enqueue vertices with 0 indegree and update their color count
26        for (int vertex = 0; vertex < numVertices; ++vertex) {
27            if (indegree[vertex] == 0) {
28                queue.offer(vertex);
29                int colorIndex = colors.charAt(vertex) - 'a';
30                ++maxColorCountAtVertex[vertex][colorIndex];
31            }
32        }
33      
34        // Processing vertices count
35        int processedVerticesCount = 0;
36      
37        // Answer to store the maximum color count in any path
38        int answer = 1;
39
40        // Process vertices until the queue is empty
41        while (!queue.isEmpty()) {
42            int currentVertex = queue.pollFirst();
43            ++processedVerticesCount;
44          
45            // Iterate over adjacent vertices
46            for (int adjacentVertex : adjacencyList[currentVertex]) {
47              
48                // Reduce indegree and enqueue if it reaches 0
49                if (--indegree[adjacentVertex] == 0) {
50                    queue.offer(adjacentVertex);
51                }
52              
53                // Update DP array to find the path with max color count
54                int colorIndex = colors.charAt(adjacentVertex) - 'a';
55                for (int color = 0; color < 26; ++color) {
56                    int currentMax = maxColorCountAtVertex[currentVertex][color] +
57                                     (colorIndex == color ? 1 : 0);
58                    maxColorCountAtVertex[adjacentVertex][color] = 
59                        Math.max(maxColorCountAtVertex[adjacentVertex][color], currentMax);
60                  
61                    // Update the answer with the maximum color count found so far
62                    answer = Math.max(answer, maxColorCountAtVertex[adjacentVertex][color]);
63                }
64            }
65        }
66      
67        // If all vertices are processed, return answer; otherwise, return -1
68        return processedVerticesCount == numVertices ? answer : -1;
69    }
70}
71
1class Solution {
2public:
3    int largestPathValue(string colors, vector<vector<int>>& edges) {
4        int numVertices = colors.size(); // Number of vertices in the graph
5        vector<vector<int>> graph(numVertices); // Adjacency list representation of graph
6        vector<int> inDegree(numVertices); // In-degree of each vertex
7
8        // Construct the graph and populate inDegree array
9        for (auto& edge : edges) {
10            int from = edge[0], to = edge[1];
11            graph[from].push_back(to);
12            ++inDegree[to];
13        }
14
15        queue<int> processingQueue; // Queue for processing vertices
16        vector<vector<int>> dp(numVertices, vector<int>(26)); // DP table: dp[i][c] represents max count of color c in vertex i's paths
17
18        // Initialize the queue with vertices having no incoming edges
19        // and update the DP table for the first character of each such vertex
20        for (int i = 0; i < numVertices; ++i) {
21            if (inDegree[i] == 0) {
22                processingQueue.push(i);
23                int colorIndex = colors[i] - 'a'; // Map the color to an index 0-25
24                dp[i][colorIndex]++;
25            }
26        }
27
28        int processedCount = 0; // Keep track of processed vertices
29        int maxPathValue = 1; // Maximum path value (minimum is 1 since at least one vertex is processed)
30
31        // Process the vertices in topological order
32        while (!processingQueue.empty()) {
33            int currentVertex = processingQueue.front();
34            processingQueue.pop();
35            ++processedCount;
36
37            // Update DP table for neighbors and detect cycles
38            for (int neighbor : graph[currentVertex]) {
39                --inDegree[neighbor];
40                if (inDegree[neighbor] == 0) {
41                    processingQueue.push(neighbor);
42                }
43                int neighborColorIndex = colors[neighbor] - 'a';
44                for (int color = 0; color < 26; ++color) {
45                    // Transfer max count of color c to its neighbors, increment if matches neighbor's color
46                    dp[neighbor][color] = max(dp[neighbor][color], dp[currentVertex][color] + (neighborColorIndex == color));
47                    // Update the max path value found so far
48                    maxPathValue = max(maxPathValue, dp[neighbor][color]);
49                }
50            }
51        }
52
53        // If processedCount is equal to numVertices, the graph is a DAG
54        // Else, it has a cycle, return -1
55        return processedCount == numVertices ? maxPathValue : -1;
56    }
57};
58
1// A function to find the largest path value in a graph given colors and edges
2function largestPathValue(colors: string, edges: number[][]): number {
3  const numVertices: number = colors.length;
4  const graph: number[][] = new Array(numVertices).fill(0).map(() => []);
5  const inDegree: number[] = new Array(numVertices).fill(0);
6
7  // Construct the graph and populate the inDegree array
8  edges.forEach(edge => {
9    const [from, to] = edge;
10    graph[from].push(to);
11    inDegree[to]++;
12  });
13
14  const queue: number[] = [];
15  const dp: number[][] = new Array(numVertices).fill(0).map(() => new Array(26).fill(0));
16
17  // Initialize the queue with vertices that have no incoming edges and
18  // update the dp table for the corresponding character of each such vertex
19  for (let i = 0; i < numVertices; ++i) {
20    if (inDegree[i] === 0) {
21      queue.push(i);
22      const colorIndex: number = colors.charCodeAt(i) - 'a'.charCodeAt(0);
23      dp[i][colorIndex]++;
24    }
25  }
26
27  let processedCount = 0;
28  let maxPathValue = 1;  // The minimum path value is 1 since at least one vertex will be processed
29
30  // Process the vertices in topological order
31  while (queue.length > 0) {
32    const currentVertex: number = queue.shift()!;
33    processedCount++;
34
35    // Update the dp table for neighbors and check for cycles
36    graph[currentVertex].forEach(neighbor => {
37      inDegree[neighbor]--;
38
39      if (inDegree[neighbor] === 0) {
40        queue.push(neighbor);
41      }
42
43      const neighborColorIndex: number = colors.charCodeAt(neighbor) - 'a'.charCodeAt(0);
44      for (let color = 0; color < 26; ++color) {
45        // Transfer the max count of color to its neighbors; if it matches the neighbor's color, increment it
46        dp[neighbor][color] = Math.max(dp[neighbor][color], dp[currentVertex][color] + (neighborColorIndex === color));
47        // Update the maxPathValue found so far
48        maxPathValue = Math.max(maxPathValue, dp[neighbor][color]);
49      }
50    });
51  }
52
53  // If processedCount equals numVertices, then the graph is a Directed Acyclic Graph (DAG),
54  // otherwise, it contains a cycle and we return -1
55  return processedCount === numVertices ? maxPathValue : -1;
56}
57
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of these properties could exist for a graph but not a tree?

Time and Space Complexity

Time Complexity

The time complexity of the algorithm is determined by several factors:

  1. The construction of the graph and the indegree array takes O(V + E) time, where V is the number of vertices (color characters) and E is the number of edges.

  2. The initialization of the dp (dynamic programming) array takes O(V * 26) time since we have a 2D array whose first dimension is the number of vertices and the second dimension is 26, representing all possible colors.

  3. The BFS (Breadth-First Search) traversal of the graph along with updating the dp array, in the worst case, involves visiting each vertex once and traversing each edge once. Within each visit of an edge, we iterate over all possible 26 colors to update the dp values, which takes O(26 * E) time.

Adding it all up, the overall time complexity is O(V + E + V * 26 + 26 * E). Because the factor of 26 is constant and does not depend on the size of the input, it can be simplified to O(V + E) in terms of the number of vertices and edges.

Space Complexity

The space complexity is determined by:

  1. The indeg array, which has a length equal to the number of vertices V, taking O(V) space.

  2. The graph g, which in the worst case can store all edges E, taking O(E) space.

  3. The dp array, which takes O(V * 26) space due to having a row for each vertex and 26 columns for each possible color.

  4. The BFS queue, which in the worst case can contain all vertices, taking O(V) space.

Summing these up, the overall space complexity is O(V + E + V * 26 + V), which simplifies to O(V * 26 + E) since the number of colors (26) is a constant.

Hence, the space complexity is largely influenced by the size of the dp array and the graph storage. For large graphs, the term involving E and the term involving V * 26 dominate the space usage.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following uses divide and conquer strategy?

Recommended Readings

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

Topological Sort Introduction

Topological Sort Topological Order Prereq Breadth First Search Review problems graph_bfs Directed Graph Before we get started on topological order let's talk about directed graphs first A graph is directed when its edges have directions these edges are also called arcs Suppose that v w are vertices in a directed

Memoization

Memoization Prereq Backtracking problems backtracking Memoization is a fancy word for a simple concept so is the case for a lot of things we learn in school It means saving the previous function call result in a dictionary and reading from it when we do the exact same call again

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ