Data Structures and Algorithms

Priority Queue

A heap data structure where we can access the smallest or largest element. It is usually implemented with an array, where the index $i$ is the parent of index $2 * i$ and $2 * i + 1$ (assuming 1 based indexing).

from heapq import heapify, heappush, heappop
 
pq = [1, 5, 3, 2, 0]
heapify(pq)     # Time Complexity: O(n)
heappush(pq, 9) # Time Complexity: O(log n)
heappop(pq)     # Time Complexity: O(log n)

Operation	Time Complexity
Heapify	O(n)
Heappush	O(n log n)
Heappop	O(log n)

Graph

Depth First Search

def dfs(src):
    visited[src] = True
    for neighbour in graph[src]:
        if visited[neighbour]: continue
        dfs(neighbour)

Breadth First Search

queue = deque([src])
visited[src] = True
while queue:
    node = queue.popleft()
    for neighbour in graph[node]:
        if visited[neighbour]: continue
        visited[neighbour] = True
        queue.append(neighbour)

Topological Sort

def dfs(node):
    visited[node] = True
    for neighbour in graph[node]:
        if visited[neighbour]: continue
        dfs(neighbour)
    stack.append(node)

Single Source Shortest Path

Bellman Ford

The time complexity of Bellman Ford is $O(VE)$ . It is unable to work on negative weighted cycle, but is able to detect them.

for i in range(n - 1):
    for src in graph:
        for dest, weight in graph[src]:
            if distance[src] + weight >= distance[dest]: continue
            distance[dest] = distance[src] + weight

Dijkstra

The time complexity of modified Dijkstra is $O((V + E) \log V)$ . Modified Dijkstra will not work only when there is negative weighted cycle.

visited = [False] * n
distances = [float("inf")] * n
distances[start] = 0
pq = [(0, start)]
while pq:
    d, u = heappop(pq)
    if d > distances[u]: continue
    for v, w in graph[u]:
        if distances[u] + w >= distances[v]: continue
        distances[v] = distances[u] + w
        heappush(pq, (distances[v], v))

Minimum Spanning Tree

A minimum spanning tree is a tree that connects all nodes in an undirected graph with the minimum cost. The time complexity of this algorithm is $O(E \log V)$ .

from heapq import heappush, heappop
from typing import List
 
def process(al: List[List[int]], visited: List[bool], pq: List[int], node: int):
    visited[node] = True
    for neighbour, cost in al[node]:
        if visited[neighbour]: continue
        heappush(pq, (cost, neighbour))
 
if __name__ == "__main__":
    # Logic to read n and graph here
    al = [[] for _ in range(n)]
    pq = []
    visited = [False] * n
    process(al, visited, pq, 0)
    nodes_processed = mst_cost = 0
    while pq and nodes_processed < n - 1:
        w, u = heappop(pq)
        if visited[u]: continue
        mst_cost += w
        nodes_processed += 1
        process(al, visited, pq, u)

Prefix Sum

For example, if we want to find the sum of subarray equals to $k$ , what we can do is to have a running sum and a hashmap of the previous running sum. Using the following concept:

$SUM(0, R) = SUM(0, L - 1) + SUM(L, R)$

$SUM(L, R) = SUM(0, R) - SUM(0, L - 1)$

We know that $k = SUM(0, R) - SUM(0, L - 1)$ which is similar to a 2-sum problem.

Introduction Networking