[Leetcode] Fancy Algorithm

Posted on | In , |

Eulerian Cycle & Hierholzer’s Algorithm

Video: https://www.youtube.com/watch?v=8MpoO2zA2l4

In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices).

In 1873, Hierholzer proposed an efficient algorithm to find the Eulerian cycle in linear time (\mathcal{O}(|E|)O(∣E∣)). One could find more details about the Hierholzer’s algorithm in this course.

The basic idea of Hierholzer’s algorithm is the stepwise construction of the Eulerian cycle by connecting disjunctive circles.

To be more specific, the algorithm consists of two steps:

  • It starts with a random node and then follows an arbitrary unvisited edge to a neighbor. This step is repeated until one returns to the starting node. This yields a first circle in the graph.
  • If this circle covers all nodes it is an Eulerian cycle and the algorithm is finished. Otherwise, one chooses another node among the cycles’ nodes with unvisited edges and constructs another circle, called subtour.

332. Reconstruct Itinerary

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution(object):
    def findItinerary(self, tickets):
        """
        :type tickets: List[List[str]]
        :rtype: List[str]
        """
        from collections import defaultdict
        self.flightMap = defaultdict(list)

        for ticket in tickets:
            origin, dest = ticket[0], ticket[1]
            self.flightMap[origin].append(dest)

        # sort the itinerary based on the lexical order
        for origin, itinerary in self.flightMap.items():
        # Note that we could have multiple identical flights, i.e. same origin and destination.
            itinerary.sort(reverse=True)

        self.result = []
        self.DFS('JFK')

        # reconstruct the route backwards
        return self.result[::-1]

    def DFS(self, origin):
        destList = self.flightMap[origin]
        while destList:
            #while we visit the edge, we trim it off from graph.
            nextDest = destList.pop()
            self.DFS(nextDest)
        self.result.append(origin)

Dijkstra Algorithm

Video: https://www.youtube.com/watch?v=XB4MIexjvY0

Find shortest path in weighted graph.
Relaxation:

1
2
if (d[u] + c(u, v) < d[v]>):
    d[v] = d[u] + c(u, v)

  • Once select a node, do relaxation to all direct neighbors (update neighbor’s distance)
  • Then move to the next smallest distanced neighbor
  • Works on directed and undirected graphs, and negative weighted edge

Worst time: O(N ^ 2)

Process:
1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty.
2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first.
3) While sptSet doesn’t include all vertices:

Pick a vertex u which is not there in sptSet and has minimum distance value.
Include u to sptSet.
Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if the sum of a distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v.

Use priority queue for weight ordering.

1514. Path with Maximum Probability

Leetcode: https://leetcode.com/problems/path-with-maximum-probability/

  1. Initialize all vertices probabilities as 0, except start, which is 1;
  2. Put all currently reachable vertices into a Priority Queue/heap, priority ordered by the corresponding current probability, REVERSELY;
  3. Whenever popped out a vertex with currently highest probability, check if it is the end vertex; If yes, we have already found the solution; otherwise, traverse all its neighbors to update neighbors’ probabilities if necessary; Note: when forwarding one step, multiply the corresponding succProb value with the probaboility of current vertex.
  4. Repeat 2 & 3 to find the max probability for end; If can NOT, return 0.0d.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
    graph = collections.defaultdict(list)
    for index, (a, b) in enumerate(edges):
        graph[a].append((b, index))
        graph[b].append((a, index))
        
    weights = [0 for _ in range(n)]
    weights[start] = 1
    heap = [(-weights[start], start)]
    while heap:
        curWeight, node = heappop(heap)
        if node == end:
            return -curWeight
        for neib, index in graph[node]:
            if -curWeight * succProb[index] > weights[neib]:
                weights[neib] = -curWeight * succProb[index]
                heapq.heappush(heap, (-weights[neib], neib))
    return 0

743. Network Delay Time

Leetcode: https://leetcode.com/problems/network-delay-time/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
    visited = set()
    graph = collections.defaultdict(dict)
    for time in times:
        frm, to, ti = time[0], time[1], time[2]
        graph[frm][to] = ti
    weights = [-1 for _ in range(n + 1)]
    weights[0] = 0
    weights[k] = 0
    heap = [(0, k)]
    
    while heap:
        time, node = heappop(heap)
        neibs = graph[node].keys()
        for nb in neibs:
            if weights[nb] == -1 or weights[nb] > time + graph[node][nb]:
                weights[nb] = time + graph[node][nb]
                heapq.heappush(heap, (weights[nb], nb))
    if -1 in weights:
        return -1
    return max(weights)

787. Cheapest Flights Within K Stops

Leetcode: https://leetcode.com/problems/cheapest-flights-within-k-stops/

  • Use another array hops to store the distance between each node with the src, if the new node has a shorter distance, we will need to consider it although it might have a higher price
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
    graph = collections.defaultdict(list)
    for start, end, price in flights:
        graph[start].append((end, price))
    
    heap = []
    maxHops = k + 1
    heapq.heappush(heap, (0, src, 0))
    costs = [float('inf') for _ in range(n)]
    hops = [float('inf') for _ in range(n)]
    costs[src] = 0
    hops[src] = 0
    
    while heap:
        price, cur, hop = heapq.heappop(heap)
        if hop <= maxHops and cur == dst:
            return price
        for nb, cost in graph[cur]:
            if costs[nb] > price + cost or hop + 1 < hops[nb]: # important step
                costs[nb] = price + cost
                hops[nb] = hop + 1
                heapq.heappush(heap, (costs[nb], nb, hop + 1))
        return -1

1976. Number of Ways to Arrive at Destination

Leetcode: https://leetcode.com/problems/number-of-ways-to-arrive-at-destination/

  • Use an additional DP array to memoize the ways to reach a single node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def countPaths(self, n: int, roads: List[List[int]]) -> int:
    costs = [float('inf') for _ in range(n)]
    graph = collections.defaultdict(list)
    heap = []
    ways = [0 for _ in range(n)]
    
    ways[0] = 1
    costs[0] = 0
    
    for u, v, time in roads:
        graph[u].append((v, time))
        graph[v].append((u, time))
    
    heapq.heappush(heap, (0, 0))
    while heap:
        dist, cur = heapq.heappop(heap)
        if dist > costs[cur]:
            continue
            
        for nb, cost in graph[cur]:
            if dist + cost < costs[nb]:
                costs[nb] = dist + cost
                ways[nb] = ways[cur]
                heapq.heappush(heap, (costs[nb], nb))
            elif dist + cost == costs[nb]:
                ways[nb] = ways[cur] + ways[nb]
                
    return ways[-1] % (10**9 + 7)

505. The Maze II

Leetcode: https://leetcode.com/problems/the-maze-ii/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def shortestDistance(self, maze, start, destination):
    m, n, q, stopped = len(maze), len(maze[0]), [(0, start[0], start[1])], {(start[0], start[1]):0}
    while q:
        dist, x, y = heapq.heappop(q)
        if [x, y] == destination:
            return dist
        for i, j in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            newX, newY, d = x, y, 0
            while 0 <= newX + i < m and 0 <= newY + j < n and maze[newX + i][newY + j] != 1:
                newX += i
                newY += j
                d += 1
            if (newX, newY) not in stopped or dist + d < stopped[(newX, newY)]:
                stopped[(newX, newY)] = dist + d
                heapq.heappush(q, (dist + d, newX, newY))
    return -1

A* Algorithm

Great Video: https://www.youtube.com/watch?v=ySN5Wnu88nE&ab_channel=Computerphile
Video (Huahua): https://www.youtube.com/watch?v=ibFvkG-7h38&ab_channel=HuaHua

An optimized (greedy) version of dijkstra

A (pronounced as A star) is also known as an informed search algorithm or best-first search. Because at each step of exploration, it makes the best and informed decision on the next steps, i.e. it prioritizes the steps that are the most promising. Specifically, this prioritization strategy can be expressed as A selects a path that minimizes the following function:

  • f(n) = g(n) + h(n)
  • n: a specific step during the exploration.
  • g(n): the cost to reach the step n. Here, the cost refers to the distance traveled so far to the step n.
  • h(n): a heuristic estimation on the cost to reach the destination from the step n. Here, the cost refers to the distance ahead.
  • f(n): the estimated total cost to reach the destination if one takes the step n.