Decrease and conquer on LeetCode is the habit of proving that a whole block of candidates cannot possibly hold the answer, and then deleting it without looking. Twelve problems here run on that one move: 167, 11, 42, 121, 53, 1014, 169, 240, 277, 280, plus two that are worth including precisely because one of them isn’t this pattern at all and the other should be. All the code here compiles and runs against the sample cases plus the edge cases listed at the bottom. More problems: the LeetCode series. The twelve problems at a glance # Problem Difficulty Shape READ MORE
Tag: coding interview
Prefix Sum in C++: Nine LeetCode Problems and One Equation
Prefix sum on LeetCode is one equation wearing nine costumes. Once you write down that the sum of a slice equals one running total minus another, every problem below turns into a question about what to store and what to look up. Nine of them are here: 1480, 303, 304, 560, 974, 325, 1524, 525, and 523. All the code here compiles and runs against the sample cases plus the edge cases listed at the bottom. More problems: the LeetCode series. The nine problems at a glance # Problem Difficulty Family 1480 Running Sum of 1d Array Easy Build the READ MORE
Cycle Sort in C++: Six LeetCode Array Problems That Are the Same Problem
Cycle sort on LeetCode is the pattern behind a group of array problems that look unrelated on the problem list and turn out to be the same eight lines of C++ with a different last paragraph. Six of them are below: 268, 448, 287, 645, 442, and 41. If you can write the skeleton from memory, you can solve all six, and the Hard one stops being a Hard. All the code here compiles and runs against the sample cases plus the edge cases listed at the bottom. More problems: the LeetCode series. The six problems at a glance # READ MORE
Leetcode 377. Combination Sum IV
This post explains how to solve leetcode 377. combination sum IV problem. It starts with brute force idea and optimize to efficiently solve the problem. Please refer to this link for problem detail. In this problem, you have two arguments – target and nums array. You are supposed to find the number of combinations to make the target amount only using numbers in nums array. In this problem, the order matters as you see in the example. Let’s think about brute force idea – enumerate all the possible subsets of nums array. For each subset, you also need to check READ MORE
Dijkstra’s Algorithm Shortest Path
Dijkstra’s algorithm is the most popular algorithm to find the shortest paths from a certain vertex in a weighted graph.In fact, the algorithm will find the shortest paths to every vertex from the start vertex.The algorithm takes both greedy and dynamic programming approach that it will try to find local optimum paths first and use them to find the shortest paths.Let’s take a look at how it works! How does Dijkstra’s algorithm work? Let’s say we need to find the shortest path from node A to node E. There are five nodes and each edge is weighted with the cost READ MORE
Intro to Union-Find Data Structure
Union-Find is a data structure that mimics tree data structure except that nodes point to their parent instead of children. The union-find is very useful for set operations such as the following.1. find – find the root of the current node2. same component – check if two trees have the same root node. (belongs to the same set)3. union (merge) – merge two trees (sets) into one Such operations are very useful for problems like connected components – each node belongs to only one connected component – and vertex coloring. The union-find is useful for algorithms such as minimum-spanning tree READ MORE
How to detect a loop (cycle) in a linked list
Traversing linked list is easy but what would happen if there is a cycle in the linked list?It will just fall into an infinity loop if traversing is implemented without a cycle prevention code.Thankfully, there is already a known algorithm for this kind of problem. How to detect if a cycle exists? Suppose there is a linked list that has a cycle like below.Now the question is how to detect the cycle. Let’s first think about what would happen if there is a cycle. Iterating linked list typically happens in a while loop like these steps. Check if the node READ MORE
Intro to Topological Sort
Topological sort is an important algorithm in DAG – directed acyclic graphs. It orders each vertex in line from left to right such that left most vertex could be considered as the highest level or root or entrance of the graph and rightmost as the lowest of the graph. In the end, topological sort tells you the order of vertices you need to go through from one node to the other without missing any middle vertices. There could be multiple topological sorts in the same graph. Let’s take a look at an example for a better understanding Course Prerequisite Example READ MORE
Intro to Depth First Search (DFS)
Depth first search is one of the popular graph traversal algorithms that work well for certain purposes.As you can infer from the name DFS is quite different from BFS – breadth first search.Therefore the applications of DFS are different from BFS.In this post, I am going to discuss how DFS works with examples.Please refer to my other post of BFS if you are interested in. How does DFS work? I am going to start by explaining DFS by comparing it with BFS.Please note that BFS searches all the neighbors at the same level or degree before you move to the READ MORE
Intro to Breadth First Search (BFS)
When dealing with a graph it might be necessary to traverse the graph.Graph traversal is a systemic method to traverse the graph.Breadth first search is one of the most popular graph traversal algorithms that work very well for certain purposes.Today, I am going to introduce breadth first search in this post. How does breadth first search traverse? BFS is a graph traversal algorithm to visit vertices from one starting point in a certain way.How does it visit other nodes? It first visits its nearest neighbors and processes them before reaching any further nodes.And it marks nodes as it visits so READ MORE