Sliding Window Concepts

The Sliding Window technique is usually used to find the shortest or longest qualified subarray. For example, find the shortest subarray whose sum is no less than K. A Naive Idea The problem is straightforward if, for every right index, we could find the rightmost left index so that the window has sum >= K….

Minimum Spinning Tree

Summary A spanning tree of some graph G is a subgraph that is a tree which includes all of the vertices of G, with a minimum possible number of edges. A Minimum Spanning Tree (MST) is a spanning tree whose sum of edge weights is as small as possible. Kruskal’s Algorithm Please refer to this page for its concepts and pseudo codes. The following code…

Eulerian Path

Summary An Eulerian path is a path in a finite graph that visits every edge exactly once (allowing for revisiting vertices). An Eulerian cycle is a Eulerian path that starts and ends on the same vertex. We give the following properties without proof. An undirected graph has an Eulerian trail iif exactly 0 or 2 vertices have odd degree, its…

Lowest Common Ancestor

Summary Lowest Common Ancestor (LCA) is a typical rooted tree related problem. A simple solution is use dfs to traverse the graph from root to leaves. If at some point it is first time we find out two nodes are in the same subtree, the current node is the LCA. The solution costs O(n) time….

Quick Select & Quick Sort

Summary Quick Select is typical technique to select the top k elements (the rest of array is not sorted) from an array in amortized O(n) time. If we use a smart way to choose pivot (Introselect), the algorithm is guaranteed to have O(n) worst case performance. Quick Sort is an unstable sort. It has amortized…

Shortest Path

Summary A common problem in undirected or directed graph is to calculate the shortest path between two nodes. There are several typical technologies that we could use. Floyd-Warshall Shortest paths (multiple sources) in such graphs that: Edges are undirected or directed; Edges have positive or negative weights; No circles have negative weights; It is actually…

Calculator

Summary There are a number of questions in the form that given a string, evaluate the value of it. These questions can be all solved by the routine Infix Notation to Reverse Polish Notation and Evaluate Reverse Polish Notation.

Bit Manipulation Tricks

Summary Bit manipulation is all about tricks. bitset is also a common data structure in set problems. Details Flip Last Set Bit The last set bit is the rightmost set bit. i&(i-1) does the trick to reset that bit. It is commonly used in Binary Indexed Tree (BIT). (i-1)  flips all the bits to the…

Pure Geometry

LC 1453. Maximum Number of Darts Inside of a Circular Dartboard Given 2 points and 1 radius, there will be 2 or 1 or 0 circles where the 2 points are at the boundary. When dist(p0, p1)>2r, there will be 0 circles. The difficulty is how to get the center of the circle in clean…

DP in Linear Structures (Extra States)

Summary In some problems, the index i is not enough to make subproblems alg[i] independent to the previous sequences s[0,i-1]. We need one or several extra states to make subproblem self-contained. The intuition is: if we brute force the problem, there might be many duplicate visitings. For example, two different dfs enter the same index…

Monotonic Queue Concepts

Summary Usually, the monotonic queue can be used in the following situations. Next Greater/Greatest: find the first larger or smaller element (or the largest or smallest element) from the current index to the very right index; Sliding Window Max: find the smallest or largest value in a sliding window Length s.t. Max: find the longest…

DP in Intervals (Break in Middle)

Summary In this category, given a range alg[i,j], we need to identify a middle point k and change the problem into alg[i,k] and alg[k+1, j]. Details LC 375. Guess Number Higher or Lower II Once we identify this problem as a DP problem, it is not difficult. Given a number from 1 to n, actually…

Sliding Window & Monotonic Queue

Summary A typical sliding window problem requires the longest or shortest subarray which satisfies certain constraints. The constraint must satisfy a monotonic property: as the right end of the window increases, the left end won’t decrease. If the constrain is related to maximum or minimum, we could use Monotonic Queues, which are perfect data structures…

Rolling Hash

Summary Rolling hash is a common technique to compare if two substrings are equal or not. Given O(n) preprocessing time, the comparison becomes O(1) at the best case. OJ Details We use two large coprime numbers for base and for mod. We use a polynomial to calculate the hash value. Typical values are and  …

Combination & Permutation & DP Counting

Summary A majority of DP counting problems would define a rule of combination or permutation, under which, you have to calculate the total number of different combinations or permutations. Some typical rules and corresponding solutions are listed below. At most x same consecutive elements; the solution is to use a dimension to record the consecutive…

Monotonic Queue in DP

Summary In this post, I will introduce some DP problems involving the Monotonic Queue. Details LC 1425. Constrained Subset Sum It is not difficult to get the following O(n^2) solution. However, the complexity is not good. What we need for {alg[i+j] for j=[1, k]} is only the maximum. So we need to keep tracking the…

Reduce Time Complexity in DP

Summary In this post, I will introduce some DP problems. It might not be difficult at the first glance. However, the optimal solution might have lower complexity if one carefully defines the state or uses some other techniques while transferring states. OJ Details LC 1027. Longest Arithmetic Sequence It is not difficult to get the…

State Compression DP

Summary State compression is a common technique in some DP problems when number of states are limited and each state consists of bits, where each bit has specific physical meaning. OJ Details LC 1349. Maximum Students Taking Exam Difficulty: 6 points. We could use bit manipulation and state compression DP. For each row, when a…

Built-in C++ String Functions

This post contains some useful functions in the standard library which simplify your codes regarding string processing. std::rotate* Performs a left rotation on a range of elements. Specifically, std::rotate swaps the elements in the range [first, last) in such a way that the element n_first becomes the first element of the new range and n_first…

Linear Recurrence Relation & Binary Exponentiation & DP Counting

Summary In this post, I will introduce a common technique in some DP counting problems: binary exponentiation. Typically, in these problems, you will be given a number n and you are asked to return the number of valid combinations. You need to figure out the initial state and the transform function between states. The problems…

Hard-to-Detect DP

Summary In this post, I will introduce some problems that seem difficult. But once we think of them in another way, they will become DP problems in linear structures or intervals, which are not difficult to solve. OJ Details LC 1049. Last Stone Weight II Think of it in this way: we divide the numbers into…

Pure Greedy

Summary In this post, I will introduce some problems which could solved by pure greedy technique. “Pure” means no other techniques are needed in this category of problems. Actually greedy can be combined by other techniques like DP. Note that usually greedy will be faster than Pure Dynamic Programming. But in case one could not…

Binary Search the Result

Summary In this post, I will introduce some problems which could binary search the best result. The problems in this category usually ask for a best value. The value could fall into the range of [min, max]. Another important property is that if the value at the middle is not achievable, we could eliminate a…

Palindrome & DP

Summary In this post, I will introduce some problems related to palindrome and dynamic programming. A palindrome has a property that, if we add two equal characters in both side of it, it is still a palindrome. OJ Details LC 1278 Palindrome Partitioning III Difficulty: 6-7 points Given a string s containing lowercase letters and an integer k….

Merge Sort

Summary In this post, I will introduce some problems using the merge sort technique. These problems often ask, for an element at index , how many are there which satisfies a formula. OJ Details The Master Theorem     If is of complexity , then is of complexity So in these problems, a key point…

DP in Linear Structures & Real Result

Summary Some problems require returning real result not just a number. To do this, a good method is that we create another table to store the optimal choices we made on each state. To return any optimal result, the choice table will be as large as the alg table. The result can we achieved by…

Divisors & Factors

Summary In this post, I will introduce some common techniques related to divisors and factors.  Details Number of Divisors GCD

KMP

Summary In this post, I will introduce some problems related to KMP. OJ Details Pi     is the length of the longest prefix of substring , such that this prefix is also the suffix of . Note that this prefix excludes itself. By the definition, we have . For example, we have, Please refer…

Pure Bit Manipulation

Summary In this post, I will introduce problems related to bit manipulation. Before that, you may want to learn the std::bitset<> class template. Detials LC 1386. Cinema Seat Allocation The problem is not difficult. But it is tricky to write a clean code. The hint is that all valid patterns can be presented by the…

Monotonic Queue (Pure)

Summary I will introduce some pure Monotonic Queue problems in this post. Details Sword to Offers Problem 59 Max Queue Mantain a special queue so that you can do max_value, push_back, and pop_front in amortized O(1) time. LC 456. 132 Pattern It is not difficult to get an O(n^2) or even an O(nlogn) solution: we…

Segment Tree

Summary In this post, I will introduce several templates for the Segment Tree. Compared to the binary index tree, segment tree is easy to understand, though the codes are longer. I will not introduce 2D Segment Tree in this post. Some OJ problems are listed below. LC 1157: query range majority; update single node; LC…

DP in Intervals (Dynamic)

Summary Some problems in this category has something dynamic. Like several elements merge into one element or eliminate one element with the a cost related to its neighbors. The key point of these problems is think backward: think about how the last element is formed. Details Minimum Cost to Merge Stones I There are N…

Date

Summary In this post, I will introduce some problems related to date.  Details Is Leap Year Days of the Year Days from 1900 Days Between Dates