Leetcode Notes
Monotonic Stack
1> find the first larger/smaller one starting from the current index.
LC 901, 907
739. Daily Temperatures
Stack
1> revolve around the relation between the sequential items.
LC 316
227. Basic Calculator II(+, -, *, /)
2> find the “(” and “)” problem. (a) It can use a stack to find all the invalid parenthesis. But it can just use count variable to deal with the simple problem, such as check valid, find the first/second outmost “(“.
LC 536. Construct Binary Tree from String
Monotonic （double-ended Queue）deque
1> move the invalid from the left and add a new one from the right. Get the min/max of the window. Keep the left as the min/max, adjust the deque when adding a new item from the right. Because of the monotonic deque. the left always max/min, even remove the invalid one. The next one is still the max/min in the window. It’s similar to a monotonic stack. Just it can remove the invalid from the left.
sliding window to find the maximum/minimum.
LC 239 Sliding Window Maximum
2> sliding window to get the average.
LC 346. Moving Average from Data Stream
Binary Search in the sorted array to replace the insertion location
1> find how many items < current item before.
DP
1> DP Arr: the problem can start from the subproblem. Think from the simplest case.
(1). Find relation between dp[i] and dp[k], where k < i.
LC 91
(2). dp[i] can be represented by the other known info. it can be before i or be after i.
LC 689
(3). dp[i][j]: For the 2d dp problem.
(a.)>The outmost loop should start from the length of the range i and j. Then i loop, the j = length -1 + i
a. ij can be driven from i -1, j-1. i, j start from the 0 to end
b. ij can be driven from i +1, j-1. Such problems usually involve subsequence or substring. Finish the initialization. j start from small to end and j start from i to 0.
312. Burst Balloons
516 Longest Palindromic Subsequence
(b.) There are two arguments. You have to narrow them to smaller ones.
1143. Longest Common Subsequence
2> DFS: tree traverse, find largest or smallest balabal(dfs + memo). Figure out the return which can be used for the next iteration.
LC 333
Knapsack Problem
It’s usually solved by DP.
Merge Intervals
1> Get the sorted intervals and merge and update for next merge.
LC 616
Find words of dict in string
1> Get the lengths of words in the dict. Scan the string and get the length of the word to check.
LC 616
Two pointers
1> Check the palindromic. (a) left and right pointers at the two ends of arr, facing to the middle. (b). Start from the middle, facing to the two ends of the arr. LC647
Heap
1> find the kth largest/smallest in the stream. Notice the minheap/maxheap to use. Keep k largest/smallest items in the heap.
LC 703. Kth Largest Element in a Stream
Maximum subarray
1> Greedy: track the max-to-curIndex, then update the max value in the process.
LC 152.Maximum Product Subarray
Quick Select
1> find the kth largest number in the unsorted array. O(n)
LC 215 Kth Largest Element in an Array
Templet:
Quick Sort vs Merge Sort vs Insertion Sort
1>Quick Sort:
sort array based on the partition, but it does not abandon one part of the array when goes to the subpart of the array.
Time complexity: average: O(nlogn) , worst:O(n2).
Space complexity: O(1).
While quick select will abandon one part.
Similar to quick sort, merge sort is another way to sort. But it will sort each pair in the array and merge them into the bigger part, and … interaction. It starts with the smallest problem to a large problem. While quick sort will start from the large problem to the small problem.
2> Merge Sort:
Time complexity: O(nlogn)
Space complexity: O(n)
Divide and Conquer, Heap
1> find the median of the two sorted array. The goal of using DC is to abandon part of the range.
LC 4. Median of Two Sorted Arrays
Tree Traversal
BFS, DFS can traverse the tree based on different requirements.
(1) BFS: the tree can be traversed level by level. You have to visit the tree with the help of the level_cnt. Then you don’t need to have a visitedSet. This is different from the BFS of traversing the graph. To traverse the general graph, you have to use a visitedSet to record which node is visited and you will not add it to the queue again. Or you can modify something in the graph to mark the visitedNode.
(2) DFS: The following discusses the iteration(stack) method of DFSto traverse the tree.
1>InOrder: left, root, right.
2>PreOrder: root, left, right
3>PostOrder:left, right, root; two solutions:(1)get most left and then check if the currentNode == preNode.left, if it is, get the preNode.right. (2) = reverse special PreOrder(root, right, left)
Binary Search
1> Given the sorted array, find the target position. (first meet or last meet)
2>The other most common way to use it: The answer will exist in (1) a sorted array and (2) there is a range. You can try different answers to check if this is the correct one.
1898. Maximum Number of Removable Characters
875. Koko Eating Bananas
3> Get the longest subsequence. Given an unsorted array, find the length of the longest subsequence.
Solution:
(1) arrA: store the sorted array when scanning the unsorted array from left to right.
(2) add the current num to the sorted arrA to make sure arrA is always sorted.
if not arrA, append directly.
binary search to get the insertion position, if the position is in the arrA, replace the original one, else append to the end of the arrA.
The length of arrA will be the increasing subsequnce.
300. Longest Increasing Subsequence
354. Russian Doll Envelopes
Random problem: Reservoir sampling
A reservoir sampling algorithm can be used for randomly choosing a sample from a stream of n items, where n is unknown. 1/count
Random pick up items satisfying their weight
398. Random Pick Index
528. Random Pick with Weight: binary search. [0, 1, 1, 2, 2, 2, 2, 3, 3, 3] => [1, 2, 4, 3] => [1, 3, 7, 10] binary search to select one random(10)
Sliding Window
1> longest/minimum substring that satisfies some conditions.
76. Minimum Window Substring
1004. Max Consecutive Ones III
395. Longest Substring with At Least K Repeating Characters(The problem has to find another condition to shrink the window. It is a special sliding window question.)
Key steps for the sliding window: (0) define one endpoint (1) expand the window (2) shrink the window.
Important Step: to update the result(min / longest substring) based on the expand(left is fixed, expand to right)/shrink(right is fixed, shrink from left) window. eg: 1> minimum: after expanding the window until it just meets the condition. The substring will be a minimum candidate. 2> longest: after shrinking the window until it just meets the condition. The substring will be the longest candidate.
Union Find O(logn)
1> Get the connected Component. It fits the dynamically calculating the connected component.
200. Number of Islands
305. Number of Islands II
827. Making A Large Island
2> Get the root of the component
721. Accounts Merge
PrefixSum
calculate the sum of the subarray:
array = [i0, i1, i2, i3, i4, i5]
PrefixSum = [0, i0, i0+i1, i0+i1+i2, sum4, sum5, sum6], each item is the sum of the first i items of the array.
Therefore: PrefixSum[j] — PrefixSum[i] = sum(array[i:j])
BFS
1> General graph:
2>Tree:
Calculate the shortest distance from source to target.
-General way to implement bfs is “queue”. Level by level =>distance is increased by each level.
-Special way to use bfs: “heap”. like Dijkstra’s algorithm(get the shortest path of the weighted graph starting from the source point.)
eg: 787. Cheapest Flights Within K Stops
Design Circular queue/deque
array = [0] * k, where k is the capacity
head = 0
count = 0
Notice: tail = (head + count-1) % capapcity
Trie
Dictionary: add word, search word
Trie: tree
node: boolean to check if the path to the current node is a word
edge: the chs
You can have other properties of the TrieNode based on the requirement of the problem.
Segment Tree
If the target is mutable, then query something based on it.
Eg: query the sum for a given range. If the num arr is immutable, we can use the prefix sum directly. While the num arr is mutable, we need to update part of the arr before the query. The segment Tree method is a good choice for such a scenario.
The segment tree actually is the (binary) indexed tree. The node if the tree is split into two parts, left and right. The node can be split into two, four, …. based on the special problems.
0> create a node of the segment tree. eg: for the query range sum of the array problem: (start, end, sumVal, leftnode, rightnode)
1> build segment tree: start from root, recursively split the node to left and right children based on the range of the node.; O(n), O(n)
2> update node in the tree: recursively update the nodes for the node; O(logn), O(1)
3> query node in the tree: query the target nodes.; O(logn), O(1)
Clone Graph
1> create new nodes based on the old nodes. 2> connect these nodes based on the connections of the old nodes.
Traverse the graph by dfs/bfs to create the new nodes and connect them.
dfs way: hashmap + set:
bfs way: hashmap + queue(normal way: queue + visitedSet): bfs to create new nodes. for each node, append the neighbors based on the old nodes.
Topological Sorting
TS is used for schedule problems. There are some prerequisites. For a directed graph, It is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.
1> generate indegree for each node.
2> start from the nodes with indegree 0, traverse the graph based on edges. Use a queue to traverse the graph, reduce the in-degree of visited nodes, when its indegree becomes 0, append it to queue. All the nodes that exist in the queue will be valid.
Detect a Cycle in a directed graph
- To detect if the graph has a cycle, (1) reverse the directed graph, all the nodes in the topological sorting are nodes that are not in the cycle. The left nodes will be in the cycle.
- To detect if the linked list has a cycle, use slow and fast pointers, if they can meet somewhere, the linked list has a cycle.
- For the directed graph:
1> smallest cycle:
Detect a Cycle in an undirected graph
Union find
(1) Cycle in a 2D grid =>check if some cell is visited again in the “going forward traversal”.
eg: 1559. Detect Cycles in 2D Grid
Shortest path from source to target in the weighted graph
Dijkstra: O((E + N)logN), O(N + E) => heap + bfs
Dijkstra: find the shortest path from s to t in the weighted graph.
BFS: find the farthest node in the unweighted graph. queue + HashSet.
Binary Tree
1>Check complete binary tree:
(1) node(i index)=>leftChild:2i and rightChild:2i + 1
(2) the index of last node(top to bottom, left to right) == #nodes in the tree
Longest subsequence and subarray for two arguments
(1) 1143. Longest Common Subsequence
DP: dp[i][j]: longest common subsequence for A[:i + 1] and B[:j + 1]
if A[i] == A[j]: dp[i][j] = 1 + dp[i — 1][j — 1]
else = max(dp[i — 1][j], dp[i][j — 1])
For the loop, from left to right of the two arrays
(2) 718. Maximum Length of Repeated Subarray
DP: dp[i][j]: maximum common prefix of A[i:] and B[j]
if A[i] == A[j]: dp[i][j] = 1 + dp[i + 1][j + 1]
For the loop, from right to left of the two arrays
