LeetCode Problem Solutions
851. Loud and Rich
Algorithm:
Build graph g where g[v] lists all richer than v.
Initialize res = -1 for all.
DFS(i):
If res[i] known, return it.
Set res[i] = i.
For each richer neighbor nei, find DFS(nei).
Update res[i] to quieter among res[i] and res[nei].
Run DFS for all nodes.
Return res.
Code:
def loudAndRich(richer, quiet):
n = len(quiet)
g = [[] for _ in range(n)]
for u,v in richer: g[v].append(u)
res = [-1]*n
def dfs(i):
if res[i]>=0: return res[i]
res[i] = i
for nei in g[i]:
c = dfs(nei)
if quiet[c] < quiet[res[i]]:
res[i] = c
return res[i]
for i in range(n): dfs(i)
return res
Input:
richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]]
quiet = [3,2,5,4,6,1,7,0]
Output:
[5,5,2,5,4,5,6,7]
990. Satisfiability of Equality Equations
Algorithm:
Create Union-Find for 26 letters.
For each a==b, union sets of a and b.
For each a!=b, if roots equal, return False.
Else, return True.
Code:
class UF:
def __init__(self):
self.p = list(range(26))
def find(self, x):
if self.p[x] != x:
self.p[x] = [Link](self.p[x])
return self.p[x]
def union(self, x, y):
self.p[[Link](x)] = [Link](y)
def equationsPossible(equations):
uf = UF()
for e in equations:
if e[1:3] == "==":
[Link](ord(e[0]) - 97, ord(e[3]) - 97)
for e in equations:
if e[1:3] == "!=":
if [Link](ord(e[0]) - 97) == [Link](ord(e[3]) - 97):
return False
return True
Input:
["a==b","b!=a"]
Output:
False
997. Find the Town Judge
Algorithm:
Initialize arrays for indegree and outdegree.
For each [a,b] in trust: outdegree[a]+=1, indegree[b]+=1.
Judge: indegree[i]==n-1 and outdegree[i]==0.
Return judge or -1.
Code:
def findJudge(n, trust):
indeg = [0] * (n+1)
outdeg = [0] * (n+1)
for a,b in trust:
outdeg[a] += 1
indeg[b] += 1
for i in range(1, n+1):
if indeg[i] == n-1 and outdeg[i] == 0:
return i
return -1
Input:
n=3, trust=[[1,3],[2,3]]
Output:
3
1311. Get Watched Videos by Your Friends
Algorithm:
BFS from id for level steps, track visited.
Collect videos of friends at distance level.
Count frequencies, sort by freq asc, then lex order asc.
Return sorted videos list.
Code:
from collections import deque, Counter
def watchedVideosByFriends(watched, friends, id, level):
visited = [False]*len(watched)
visited[id] = True
q = deque([id])
for _ in range(level):
for _ in range(len(q)):
curr = [Link]()
for nei in friends[curr]:
if not visited[nei]:
visited[nei] = True
[Link](nei)
videos = []
while q:
[Link](watched[[Link]()])
count = Counter(videos)
return sorted(count, key=lambda x: (count[x], x))
Input:
watched = [["A","B"],["C"],["B","C"],["D"]]
friends = [[1,2],[0,3],[0,3],[1,2]]
id = 0, level = 1
Output:
["B","C"]
1514. Path with Maximum Probability
Algorithm:
Build weighted graph from edges and probabilities.
Initialize prob array with 0, prob[start]=1.
Use max-heap for Dijkstra:
Extract max prob node.
Update neighbors if higher prob path found.
Return prob[end] or 0 if unreachable.
Code:
import heapq
def maxProbability(n, edges, succProb, start, end):
graph = [[] for _ in range(n)]
for (u,v), p in zip(edges, succProb):
graph[u].append((v,p))
graph[v].append((u,p))
prob = [0]*n
prob[start] = 1
heap = [(-1, start)]
while heap:
p, node = [Link](heap)
p = -p
if node == end:
return p
if p < prob[node]:
continue
for nei, w in graph[node]:
np = p * w
if np > prob[nei]:
prob[nei] = np
[Link](heap, (-np, nei))
return 0
Input:
n=3
edges=[[0,1],[1,2],[0,2]]
succProb=[0.5,0.5,0.2]
start=0, end=2
Output:
0.25