HardNo. 1857
Largest Color Value in a Directed Graph — LeetCode 1857 Python Solution
- Pattern
- Topological Sort
- Topics
- Graph, Topological Sort, Memoization, Hash Table, Dynamic Programming, Counting
- Reading time
- 5 min
- Source
- leetcode.com
The problem
There is a directed graph of n colored nodes and m edges. The nodes are numbered from 0 to n - 1.
Example
- 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).
Python solution
class Solution:
def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
n = len(colors)
indeg = [0] * n
g = defaultdict(list)
for a, b in edges:
g[a].append(b)
indeg[b] += 1
q = deque()
dp = [[0] * 26 for _ in range(n)]
for i, v in enumerate(indeg):
if v == 0:
q.append(i)
c = ord(colors[i]) - ord('a')
dp[i][c] += 1
cnt = 0
ans = 1
while q:
i = q.popleft()
cnt += 1
for j in g[i]:
indeg[j] -= 1
if indeg[j] == 0:
q.append(j)
c = ord(colors[j]) - ord('a')
for k in range(26):
dp[j][k] = max(dp[j][k], dp[i][k] + (c == k))
ans = max(ans, dp[j][k])
return -1 if cnt < n else ansComplexity
- Time
- O((n + m) × |Σ|)
- Space · auxiliary
- O(m + n × |Σ|)
Pattern: Topological Sort
Order a set of tasks so that every dependency comes before the thing that needs it. LeetCode 1857. Largest Color Value in a Directed Graph is filed here because LeetCode tags it Topological Sort, which is the vocabulary this hub collects.
The topological sort guide has the Python template for the pattern and the 32 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0139 | Word Break | Medium |
| 0140 | Word Break II | Hard |
| 0691 | Stickers to Spell Word | Hard |
| 1255 | Maximum Score Words Formed by Letters | Hard |
| 1782 | Count Pairs Of Nodes | Hard |
| 1994 | The Number of Good Subsets | Hard |
Frequently asked questions
- How hard is LeetCode 1857. Largest Color Value in a Directed Graph?
LeetCode 1857. Largest Color Value in a Directed Graph is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1857. Largest Color Value in a Directed Graph?
The Python solution on this page runs in O((n + m) × |Σ|).
- What is the space complexity of LeetCode 1857. Largest Color Value in a Directed Graph?
The Python solution on this page uses O(m + n × |Σ|) auxiliary space.
- What topics does LeetCode 1857. Largest Color Value in a Directed Graph cover?
LeetCode 1857. Largest Color Value in a Directed Graph is tagged Graph, Topological Sort, Memoization, Hash Table, Dynamic Programming and Counting on LeetCode.