Network Delay Time

This problem is a good example of how to use Dijkstra's algorithm to solve a problem.

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = collections.defaultdict(list)
        for f, t, w in times:
            graph[f].append((w, t))

        distances = [math.inf] * n

        min_heap = [(0, k)]
        while min_heap:
            d, n = heapq.heappop(min_heap)

            if distances[n - 1] != math.inf:
                continue

            distances[n - 1] = d
            for w, t in graph[n]:
                heapq.heappush(min_heap, (d + w, t))

        ans = max(distances)
        return ans if ans != math.inf else -1

Redundant Connection

This problem is a good example of how to use Union Find to solve a problem. The problem is to find the redundant connection in a graph.

class DSU:
    def __init__(self, total_node_count) -> None:
        self.parent = [i for i in range(total_node_count + 1)]
        self.rank = collections.defaultdict(int)

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        xp, yp = self.find(x), self.find(y)

        if xp == yp:
            return False
        elif self.rank[xp] < self.rank[yp]:
            self.parent[xp] = yp
        elif self.rank[xp] > self.rank[yp]:
            self.parent[yp] = xp
        else:
            self.parent[yp] = xp
            self.rank[xp] += 1

        return True

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        dsu = DSU(1000)
        for edge in edges:
            if not dsu.union(*edge):
                return edge

K Closest Points to Origin

This problem is quite easy as we can just sort the list using a custom comparator and return the k closest. However, finding the optimal is quite hard.

Usually we do binary search on a sorted list. Sometimes, we do it on a monotonic function. However, we use binary search on the distance here and reduce the search space by half each time. Binary search will give a O(n) time and space solution

Binary Search Solution:

class Solution:
    def distance(self, point: List[int]) -> int:
        return point[0] ** 2 + point[1] ** 2 # we avoid the square root operation here
    def split_distances(self, remaining, distances, mid):
        closer, farther = [], []
        for index in remaining:
            if distances[index] <= mid:
                closer.append(index)
            else:
                farther.append(index)
        return closer, farther
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        distances = [self.distance(point) for point in points]
        remaining = [i for i in range(len(points))]
        low, high = 0, max(distances)
        ans = []
        while k:
            mid = low + (high - low) / 2
            closer, farther = self.split_distances(remaining, distances, mid)
            # if we have more than enough points in the closer half, we can continue to search in the closer half for k closest
            if len(closer) > k:
                remaining = closer
                high = mid
            # else if we have less than k points in the closer half, we have to search for k - len(closer) closest points from the farther half
            else:
                k -= len(closer)
                ans.extend(closer)
                remaining = farther
                low = mid
        return [points[i] for i in ans]

However, the most optimal solution would be to use quickselect. For problems where we are tasked with finding the k (or kth) smallest/largest/etc, we should always consider whether QuickSort can be applied.

Topological sort - Course Schedule II

Topological sort is a graph traversal algorithm that can be used to sort a DAG in topological order.

Psuedo Code (Kahn's algorithm):

L = Empty list that will contain the sorted elements
S = Stack of all nodes with no incoming edge

while S is non-empty do
    remove a node n from S
    append n to L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S

if graph has edges then
    return error   (graph has at least one cycle)
else
    return L   (a topologically sorted order)

A good leetcode problem that uses topological sort is Course Schedule II.

class Node:
    def __init__(self):
        self.indegree = 0
        self.outgoing_nodes = []

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = defaultdict(Node)
        # make adj list with indegree as extra info
        total_deps = 0
        # add all nodes
        for i in range(numCourses):
            graph[i]
        # populate adj list
        for to_node, from_node in prerequisites:
            graph[from_node].outgoing_nodes.append(to_node)
            graph[to_node].indegree += 1
            total_deps += 1
        # add all nodes with no deps
        no_deps_courses = []
        for key, node in graph.items():
            if node.indegree == 0:
                no_deps_courses.append(key)
        # perform topological sort (Kahn's algo)
        topo_order = []
        removed_edges = 0
        while no_deps_courses:
            course = no_deps_courses.pop()
            topo_order.append(course)
            for to_node in graph[course].outgoing_nodes:
                removed_edges += 1
                graph[to_node].indegree -= 1
                if graph[to_node].indegree == 0:
                    no_deps_courses.append(to_node)
        return topo_order if removed_edges == total_deps else []

LRU Cache

This problem is a good example of how to use a doubly linked list and a hashmap to implement a cache.

class LinkedListNode {
public:
    int key, val;
    LinkedListNode *next, *prev;

    LinkedListNode(int key, int val) {
        this->key = key;
        this->val = val;
    }
};

class DLinkedList {
public:
    LinkedListNode *head, *tail;

    DLinkedList() {
        this->head = new LinkedListNode(0, 0);
        this->tail = new LinkedListNode(0, 0);

        this->head->next = this->tail;
        this->tail->prev = this->head;
    }

    void add(LinkedListNode *node) {
        auto head_next = this->head->next;
        head_next->prev = node;

        head->next = node;

        node->prev = head;
        node->next = head_next;
    }

    void remove(LinkedListNode *node) {
        auto node_prev = node->prev;
        auto node_next = node->next;

        node_prev->next = node_next;
        node_next->prev = node_prev;
    }
};

class LRUCache {
public:
    int capacity;
    unordered_map<int, LinkedListNode*> cache;
    DLinkedList *ll;

    LRUCache(int capacity) {
        this->capacity = capacity;
        ll = new DLinkedList();
    }

    int get(int key) {
        if (cache.find(key) == cache.end()) {
            return -1;
        }

        auto node = cache[key];
        ll->remove(node);
        ll->add(node);

        return node->val;
    }

    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            replace_value_for_key(key, value);
            return;
        }

        if (cache.size() >= capacity) {
            remove_lru();
        }

        auto node = new LinkedListNode(key, value);
        cache[key] = node;
        ll->add(node);
    }

private:
    void replace_value_for_key(int key, int value) {
        if (cache.find(key) == cache.end()) {
            return;
        }

        auto node = cache[key];
        ll->remove(node);
        node->val = value;
        ll->add(node);
        cache[key] = node;
    }

    void remove_lru() {
        if (cache.empty()) {
            return;
        }

        auto lru = ll->tail->prev;
        ll->remove(lru);
        cache.erase(lru->key);
    }
};

Here's a solution in python:

class LinkedListNode:
    def __init__(self, key: int, val: int):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class DLinkedList:
    def __init__(self):
        # Head and Tail are dummy nodes
        self.head = LinkedListNode(0, 0)
        self.tail = LinkedListNode(0, 0)

        # Link head and tail
        self.head.next = self.tail
        self.tail.prev = self.head

    def add(self, node: LinkedListNode) -> None:
        # Add node in the front after head
        head_next = self.head.next
        head_next.prev = node

        self.head.next = node

        node.prev = self.head
        node.next = head_next

    def remove(self, node: LinkedListNode) -> None:
        # Remove node from DLinkedList
        node_next = node.next
        node_prev = node.prev

        node_next.prev = node_prev
        node_prev.next = node_next

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.ll = DLinkedList()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1

        node = self.cache[key]
        self.ll.remove(node)
        self.ll.add(node)

        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.__replace_value_for_key(key, value)
            return

        if len(self.cache) >= self.capacity:
            self.__remove_least_recently_used()

        node = LinkedListNode(key, value)
        self.cache[key] = node
        self.ll.add(node)

    def __replace_value_for_key(self, key: int, value: int) -> None:
        if key not in self.cache:
            return

        node = self.cache[key]
        self.ll.remove(node)
        node.val = value
        self.ll.add(node)
        self.cache[key] = node

    def __remove_least_recently_used(self) -> None:
        if not self.cache:
            return

        lru = self.ll.tail.prev
        self.ll.remove(lru)
        self.cache.pop(lru.key)

In python this problem can be solved using a OrderedDict very easily.

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

Interesting LeetCode problems.

Network Delay Time

Redundant Connection

K Closest Points to Origin

Topological sort - Course Schedule II

LRU Cache