I’ve joined LeetCode’s Content Creator Team to publish official solutions since Oct 26, 2020. Here you may find some of my work that’s published on LeetCode:
Continue reading “LeetCode Authorized Author”LeetCode Authorized Author
Disjoint Set – Union & Find
Continue reading “Disjoint Set – Union & Find”In computer science, a disjoint-set data structure … is a data structure that stores a collection of disjoint (non-overlapping) sets. … It provides operations for adding new sets, merging sets (replacing them by their union), and finding a representative member of a set.
Source: https://en.wikipedia.org/wiki/Disjoint-set_data_structure
Minimum Spanning Tree – Prim
Continue reading “Minimum Spanning Tree – Prim”A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
Source: https://en.wikipedia.org/wiki/Minimum_spanning_tree
Binary Search – Find Upper and Lower Bound
This post will introduce one specific application of Binary Search, i.e., when you are asked to find the upper or lower bound, or more precisely, when you need to find the maximum of the smallest value or the minimum of the largest value.
Continue reading “Binary Search – Find Upper and Lower Bound”BFS and Bi-directional BFS
Apart from vanilla BFS introduced in Intro to Graph Algorithms – BFS & DFS, there’s another variant of BFS called bi-directional BFS. Instead of searching from source to target, bi-directional BFS starts with the source and the target at the same time, and search the graph simultaneously. The improvement of time complexities is shown as below, as referring to @Huahua.
Continue reading “BFS and Bi-directional BFS”Floyd’s Cycle Detection Algorithm – [Leetcode]142. Linked List Cycle II
The cycle detection problem is to find the cycle in a sequence, and Floyd’s cycle detection algorithm, aka Tortoise and Hare algorithm, is a two pointers algorithm to detect the cycle and the start of the cycle as well.
Continue reading “Floyd’s Cycle Detection Algorithm – [Leetcode]142. Linked List Cycle II”Intro to Trie (Prefix Tree) – FEAT. Leetcode 208. Implement Trie
A trie, or a prefix tree, refers to an ordered data structure that is usually used to store strings (Wikipedia). The picture on the above is an example where a trie stores [ape,apple,are,art]. Now let’s take a closer look at it and it’s not hard to find that:
Shortest Path Algorithms I – Dijkstra
The shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized. (Wikipedia) In this and coming posts some of the most common algorithms to solve the shortest path problems will be explained. Today’s topic is Dijkstra.
Continue reading “Shortest Path Algorithms I – Dijkstra”