intervals = sorted(intervals)
        res = [intervals[0]]
        rightmost = intervals[0][1]
        for i in intervals[1:]:
            if i[0]<=rightmost<= i[1] or rightmost >= i[1]:
                popInt = res.pop()
                res.append([min(popInt[0], i[0]), max(popInt[1], i[1])])
                rightmost = max(popInt[1], i[1])
            else: 
                res.append(i)
                rightmost = i[1]
                
        return res

res = []
path = [1,2,3]
res.append(list(path))
print(res) => [[1,2,3]]
path.pop()
print(res) => [[1,2,3]]

### 1209. Remove All Adjacent Duplicates in String II (Medium, FB常考)
* 主要思路： stack存[letter, frequency]
* 目前解法： time O(N), space: O(N)


================================================
## Queue
================================================
* FIFO
Terminology: 
* enqueue: put items in the queue. 
* dequeue: remove items from the queue.

Basic Operations of Queue
* enqueue
* dequeue
* isEmpty: check if queue is empty
* isFull: check if queue if full
* Peek: get value of the front of the queue without removing it

Working of Queue
* Queue operations work as follows:
    * two pointers FRONT and REAR
    * FRONT track the first element of the queue
    * REAR track the last element of the queue
    * initially, set FRONT and REAR = -1

1. Enqueue Operation
    * check if the queue is full
    * for the first element, set the value of FRONT to 0
    * increase the REAR index by 1
    * add the new element in the position pointed to by REAR

2. Dequeue Operation
    * check if the queue is empty
    * return the value pointed by FRONT
    * increase the FRONT index by 1
    * for the last element, reset the values of FRONT and REAR to -1

Applications of Queue
* CPU scheduling, Disk Scheduling
* When data is transferred asynchronously between two processes.The queue is used for synchronization. For example: IO Buffers, pipes, file IO, etc
* Handling of interrupts in real-time systems.
* Call Center phone systems use Queues to hold people calling them in order.

Complexity Analysis
* Enqueue and dequeue operations in a queue using an array is O(1)

## Circular Queue
* the circular increment is performed by modulo division with the queue size.
Circular Queue Operations
* The circular queue work as follows:
    * two pointers FRONT and REAR
    * FRONT track the first element of the queue
    * REAR track the last elements of the queue
    * initially, set value of FRONT and REAR to -1
1. Enqueue Operation (会动的只有REAR)
*  check if the queue is full, if yes, return False
* elif:  for the first element, set value of FRONT to 0
* else: circularly increase the REAR index by 1 (i.e. if the rear reaches the end, next it would be at the start of the queue), add the new element in the position pointed to by REAR

2. Dequeue Operation （会动的只有FRONT）
* check if the queue is empty, if yes, return False
* elif at last item (FRONT == REAR), return queue[FRONT] and reset FRONT, REAR to -1
* else: return the value pointed by FRONT, circularly increase the FRONT index by 1

3. Check if Queue is Full
* Case 1: FRONT = 0 && REAR == SIZE - 1
* Case 2: FRONT = REAR + 1

## Priority Queue
* In a queue, the first-in-first-out rule is implemented whereas, in a priority queue, the values are removed on the basis of priority. The element with the highest priority is removed first.
* we can use linked-list, binary search, heap to implement priority queue. 

-----------------------------------------------
### 622. Design Circular Queue (Medium, Circular Queue)
* use circular definition above
* 相似题： 
    * 641. Design Circular Deque (Medium): 完全和622一样的想法

### 767. Reorganize String (Medium, Priority Queue)
* 解题思路： alternating inserting the most common letter to res. 
* 相似题： 
    * 621. Task Scheduler (Medium)

================================================
## Binary-Search
================================================
* Binary Search is a searching algorithm for finding an element's position in a sorted array.
*  Binary search can be implemented **only on a sorted list of items**. If the elements are not sorted already, we need to sort them first.
* Time Complexities： b
    * best case complexity: O(1)
    * Average case complexity: O(log n): proof: The question is, how many times can you divide N by 2 until you have 1? This is essentially saying, do a binary search (half the elements) until you found it. In a formula this would be this: $1 = \frac{N}{2^x} \rightarrow x=\log(N)$
    *  Worst case complexity: O(log n)
* Space Complexity: O(1)
* template

-----------------------------------------------

### 278. First Bad Version (Easy)
* set two pointers, start and end, check if mid is True, then move pointers accordingly. 
* 相似题： 
    * 374. Guess Number Higher or Lower （Easy)
    * 35. Search Insert Position (Easy)
    * 34. Find First and Last Position of Element in Sorted Array (Medium, 常考)

### 34. Find First and Last Position of Element in Sorted Array (Medium, 常考)
* binary search to find left bound, then run the binary search to find right bound, so total is 2 binary search = 2*O(logn)
* time: O(logn), space O(1)

### 658. Find K Closest Elements (Medium)
* binary search to find x. Starting from x's index, expand window by comparing if which of the left/right item is closer to x, and include it to the window, run until sliding window size reach k. 
* 细节： sliding window: left,right = bsearch_output-1, bsearch_output(why? because bsearch_output>=x)

================================================
## Binary-Search-Trees
================================================
* 问题：Given an array of numbers, interval $k$, given another number $m$问
    1. 是否能将$m$ insert into the array $R$ with all numbers separated by at least distance $k$
    2. can u do in $O(logn)$
* 几种可能解法:
    1. sorted array:
        * do binary search and find the place to insert: $O(log n)$
        * compare against $R[i-1]$ and $R[i]$
        * insert: $O(n)$, because it is an array, requires shifting elements
    2. heap
        * insert: $O(logn)$
        * find the place to insert: $O(n)$
    3. Dictionary or python set: 
        * insert: $O(1)$
        * find the place to insert: $\Omega(n)$ (lower bound, at least this much)
* So 我们需要binary search trees
    * 定义：it is a **data structure**. `node.left.val < node.value < node.right.val`
    * 二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为 $O(\log n)$
    * time complexity: All operations (search, insert, deletion) are O(h) where $h=log n$ is height of the BST.
    * space complexity: $O(n)$
-----------------------------------------------

#### 501. Find Mode in Binary Search Tree (Easy)
* 相似题： 
    * 98. Validate Binary Search Tree (Medium)
        * recursion+定义一个函数叫valid去做functioning的一些工作
        * `valid(root, min, max)`: 因为树的左边必须都小于顶端root， 右边必须大于顶端root。
        * 在同一个class下define function记得加self `def valid(self, root, min, max): `


### 1038. Binary Search Tree to Greater Sum Tree (Medium, 常考)
* recursion solution (or DFS), first right node, then modify node.val, then save self.prev(to save up-to-date sum), then do left node. 
* time: O(N), space: O(1): in-place modify
* 相似题： 
    * 538. Convert BST to Greater Tree: same question


================================================
## Trees
================================================

## Binary Tree
*  It's a **tree data structure** in which each node has **at most two children**.
* Depth First Traversals:

   1
  / \
2    3       / \   4   5 ``` * Inorder (Left, Root, Right) : 4 2 5 1 3 * Preorder (Root, Left, Right) : 1 2 4 5 3 * Postorder (Left, Right, Root) : 4 5 2 3 1 * Breadth First or Level Order Traversal : 1 2 3 4 5 -----------------------------------------------

* time: O(V+E)
    * outer loop: visit all vertices: O(V)
    * inner loop: DFS-visit is called only once for one versit. And visit all outgoing edges from the vertex: O(E)

* Application I: Job Scheduling
    * Given Directed Acylic Graph (DAG), where vertices represent tasks & edges represent dependencies, order tasks without violating dependencies
    * Topological Sort: run DFS, output the reverse of finishing times of vertices
        * During DFS, after visited a vertex, you put into a list, so your output shall be the reverse of this list
        * Proof why this works? 
        * proof statement: For any edge (u, v) — u ordered before v, i.e., v finished before u, reverse the visited list can do the topological sort
        * case 1: if $u$ is visited before $v$
            * proof: u is visited before v. since we have the edge $u->v$, before u finishes, we will visit v. That implies v finishes before u.
        * case 2: if $v$ is visited before $u$. 
            * proof: if it happens, means that there exists an edge of $v->u$. Plusing our premise $u-> v$ implies we have a cycle in the graph. Contradiction. So case 2 cannot happen. 

------------------------------------------------

### 690. Employee Importance (Easy, 相似题)
* recursion + hashtable
* 相似题： 
    * 339. Nested List Weight Sum (Medium): recursion
    * 364. Nested List Weight Sum II (Medium): I write a function to do DFS to find max depth, then use #339 to calculate weighted sum

### 695. Max Area of Island (Medium， 相似题)
* time: O(R*C), space O(R*C): R: no. rows, C: no. cols
* 相似题： 
    * 200. Number of Islands (Easy)
        * 主要思路： DFS, 将每一个grid看成一个node, 每个node有四个branch(left, right, up, down), 我们要做的就是DFS去找到所有的为1的grid将其value 从1改为*， *指的是这一片小岛，使得下次for loop到的时候不会增加count

================================================
## Toplogical-Sort
================================================
* 使用条件： 只针对Directed acyclic(acyclic means not form of a cycle) graph (DAG)，有向无环图。(i.e., 这个图的边必须是有方向的；图内无环。)
* DAG <=> Toplogical Sort
    * 如果这个图不是 DAG，那么它是没有拓扑序的；
    * 如果是 DAG，那么它至少有一个拓扑序；
    * 反之，如果它存在一个拓扑序，那么这个图必定是 DGA.
* toplogical sort is not unique. 
    * e.g.， 要修C1, C2再修C3, C4, 这边就有两个toplogical sort, 一个是先修C1再C2， 一个是先修C2再C1
* Definition: 
    * 入度：顶点的入度是指「指向该顶点的边」的数量；
    * 出度：顶点的出度是指该顶点指向其他点的边的数量。
    * We can view a topological sort of a graph as an ordering of its vertices along a horizontal line so that **all directed edges go from left to right**
* BFS Implementation Algorithm (推荐): 
    * Map: `<key = Vertex, value = 入度>`
    * 我们把入度为 0 的那些顶点放入 queue 中，然后通过每次执行 queue 中的顶点，就可以让依赖这个被执行的顶点的那些点的 入度-1，如果有顶点的入度变成了 0，就可以放入 queue 了，直到 queue 为空。
* DFS Implementation Algorithm: 
* time complexity O(V+E)
* Application: 
    * 课程排序
    * 判断是不是DAG： 另一个是如果题目没有给这个图是 DAG 的条件的话，那么有可能是不存在可行解的，那怎么判断呢？很简单的一个方法就是比较一下最后结果中的顶点的个数和图中所有顶点的个数是否相等，或者加个计数器，如果不相等，说明就不存在有效解。所以这个算法也可以用来判断一个图是不是有向无环图。
    * 比如 pom 依赖引入 jar 包时，大家有没有想过它是怎么导进来一些你并没有直接引入的 jar 包的？比如你并没有引入 aop 的 jar 包，但它自动出现了，这就是因为你导入的一些包是依赖于 aop 这个 jar 包的，那么 maven 就自动帮你导入了。
------------------------------------------------

### 207. Course Schedule (Medium, 常考)
* step1: graph processing: 
    * construct in_edges`<vertex: no. ingoing edges>`, and out_edges`<vertex: [list of outgoing edges]>`
* step 2: BFS impletation of toplogical sorting
* time $O(|V|+|E|)$
* 相似题： 
    * 210. Course Schedule II (Medium, 常考)

### 329. Longest Increasing Path in a Matrix (Hard, 常考， textIQ考了)
* step 1: graph processing: construct in-edges and out_edges
* step 2: put initial in_edges=0 vertices into queue
* step 3: run BFS: use longest to record current level, return longest as results. 
* time: O(M*N+ 4MN (no. edges))= O(mn) space: O(M*N)

================================================
## Graph-based DSA: BFS
================================================
* Goal: reach all nodes reachable from a given vertex $s\in V$
* Start from one node $s$, look at all possible node you can reach, build level i > 0 from level i − 1 by trying all outgoing edges, but **ignoring vertices from previous levels**
* $O(V+E)$ time, kinda optimal as you need to at least go over all vertices and edges. 
* Algorithm: time O(V+E)

* LC template

* Another way to look at the graph is Tree. As this graph can also be represented as a tree. 
* BFS的经典题： find the shortest path from vertex $v$ to $s$. 
    * take v, read its parent[v], read its parent[parent[v]], etc., until s (or None), then read backwards is the shortest path from s to v.
    * for every vertex v, fewest edges to get from s to v is either level[v] if v assigned level or inf (no path)
* 主要解题思路： 
    1. 用deque记录visited过的nodes， while deque, reach to next node from current node. Update level. 
------------------------------------------------

### 994. Rotting Oranges (Medium， modify in-place)
* first create a deque to store rotten oranges positions. Use (-1, -1) to mark it's the end of a level. While queue, determine if need to add another level marker, and update rotten
* Time: O(N): N is the size of grid, enumerate it once to find all rotten oranges at state 0 (O(N)), then enumerate it once to update rotten oranges O(N), in total is O(N)+O(N) = O(N), space O(N): deque
* 相似题： 
    * 286. Walls and Gates (Medium)
        * ThoughtExchange面试考了， 这题和rotting oranges一样的解法
    * 130. Surrounded Regions (Medium)
        * 主要思路： mark connected to border cells to "E", "E" means finally we want to escape flipping on these cells
        * time: O(N), space: O(N): N no. of cells in the board
    * 200. Number of Islands (Easy)
        * 主要思路： DFS, 将每一个grid看成一个node, 每个node有四个branch(left, right, up, down), 我们要做的就是DFS去找到所有的为1的grid将其value 从1改为*， *指的是这一片小岛，使得下次for loop到的时候不会增加count
    * 1197. Minimum Knight Moves (Medium)
        * 典型BFS
    * 542. 01 Matrix (Medium)

### 127. Word Ladder (Hard)
* 这道题的难点就是怎么找出dist(w1, w2). 这里用的方法是先过一遍wordList, 将wordList里每个word的pattern找出来， 存入dictionary。 key is pattern, value of a list of words that satisfy this pattern. E.g., pattern of a word "hit" are "*it", "h*t", "hi*". 
* 细节： create a dictionary of list values `from collections import defaultdict, defaultdict(list)`
* time: total is $O(M^2N)$. 
    * calculate dictionary: $O(M*M*N)$. M is length of each word in wordList, N is len of wordList. we needs to create $M*N$ variants, each variant is created from substring operation, which takes $O(M)$.
    * BFS: $O(M^2N)$: worst case is to go over all N words in wordList, and each word has M variants, and each variant is created from **substring operation**, which **takes $O(M)$ time**. 
* space : $O(M^2N)$ (from $O(M*M*N)+O(MN)+O(MN)$)
    * pattern dict $O(M*M*N)$: each word has M variants, and each variant has length M, in total we have N words
    * Visited queue need $O(MN)$: N words, each word has length M
    * queue for BFS $O(MN)$: worst case need to store all (N-1) words
* 相似题： 
    * 126. Word Ladder II （Hard): 记住要设置visited_at_this_level, and set break once find the shortest path to prevent exceed time limit

### 1091. Shortest Path in Binary Matrix (Medium)
* 也是需要replace cell's value to its level in BFS tree. similar to Q329.
* time O(MN), space O(MN), where M, N is no.rows, cols in the grid. 
================================================
## Math 
================================================
### 645. Set Mismatch (Easy)
* **list不能相减， set可以**

### 621. Task Scheduler (Medium)
* 类似于种树问题， 相同的task间至少要隔n个位置
* 找出freq最多的task， 那么结果是 max(len(tasks), (maxfreq-1)*(n+1)+nmax)， where maxfreq是最多freq的task的freq， nmax:有几种最多freq的task。 e.g., n=2, A, _, _, A, _, _, A, 那么需要 2个 A, _, _ 组（长度为(maxfreq-1)*(n+1))加上最后的A。 
* 细节： `ord('B')-ord('A')=1`, `<arr>.count(<element>)`: returns the number of times the specified element appears in the list.
* time: O(n): 因为要建这个freq array， space: O(1), 这个freq array 长度固定为26， 因为26个字母。

### 204. Count Primes (Easy)
* 主要思路： outer loop from 2 to $\sqrt{n}$ (because say $n = p\times q$, where $p \leq q$, then worst case is $p=q=\sqrt{n}$), inner loop, save multiples into a dict `multiples`. 
* time complexity $O(\sqrt{n}l\log\log n)$, as $\sum_{primes\ i\ before\ n} \frac{n}{i} = O(loglog n)$ space : $O(n)$. 

### 628. Maximum Product of Three Numbers (Easy)
* sort array first, 最大的是either last three items multiplication or nums[0]*nums[1]*nums[-1]

### 1822. Sign of the Product of an Array (Easy)

### 836. Rectangle Overlap (Easy)

### 592. Fraction Addition and Subtraction (Medium)
* `ints = map(int, re.findall('[+-]?\d+', expression))` get expression里的分数 (it is an iterable, move iterable to next item by `b = next(ints)`, read items in iterable by `for a in ints`)，存做$\frac{a}{b}$, 将目前的sum叫做$\frac{A}{B}$. $\frac{A}{B}+\frac{a}{b}=\frac{Ab+Ba}{Bb}$, 算出分母分子的gcd by `math.gcd()`, updating 分母分子by `//gcd`
* re: 
    * `\d`: match any digit
    * `(?...)`: The first character after the '?' determines what the meaning and further syntax of the construct is. 
    * `[]`: indicate a set of characters
    * `+`: Causes the resulting RE to match 1 or more repetitions of the preceding RE. ab+ will match ‘a’ followed by any non-zero number of ‘b’s; it will not match just ‘a’.
* `map(int, <str expr>)`: map string expression to integer. 

================================================
## Array
================================================
### 41. First Missing Positive (Hard, 常考)
* 思路和之前的一题一样， index sorting， nums[num] *= -1, 这样positive的index都会变负数。 
* 类似题： 
    * 448. Find All Numbers Disappeared in an Array (Easy)
        * 主要思路： 
            * 方法1是用set做, complexity is O(N). set() is essentially iterating over the list and adding each of those elements to a hash table.
            * 方法2: in-place modify. 将数字对应在1-n的index变成-数字。 e.g.，[2,2], 2 corresponds to index 1 in 1-n, so mark 2 to -2. then iterate over the array again to find which index is non-negative, those are results. 
                * time: O(N)
                * space: O(1): in-place

### 1200. Minimum Absolute Difference (Easy)
* 主要思路： minimum diff一定是在相邻的两个数之间， 所以先sort array
* time: 
    * sort: O(nlogn)
    * go over array : O(n)
* space: O(N): worst case is that all numbers are equally spaced, thus store all pairs in, thus 2N numbers. 



#### 1480. Running Sum of 1d Array (Easy, Amazon常考)
* 主要思路：过一遍, `nums[i] += nums[i-1]`
* time: O(N), space O(1)

### 163. Missing Ranges
* time: O(N), space O(1) 
    * The output list has a worst case size of O(N). This case occurs when we have a missing range between each of the consecutive elements in the input array (for example, if the input array contains all even numbers between lower and upper). We aren't using any other additional space, beyond fixed-sized constants that don't grow with the size of the input.
    * However, **output space that is simply used to return the output (and not to do any processing) is not counted for the purpose of space complexity analysis**. For this reason, the overall space complexity is O(1).

================================================
## Hash-Table
================================================
### 266. Palindrome Permutation (Easy, 常考， 相似题)
* 判断a string 可否通过permutation得到一个palindrome => all chars appear even number of times, OR all char appear even number of times and except one appear once. 
* time: O(N), space: O(1): because # of chars are bounded by 26.
* 相似题： 
    * 409. Longest Palindrome (Easy): 判断最长能组成palindrome的substr
        * 这题两个情况： 对于出现次数为奇数的char, 
            * 情况1：第一次出现奇数， so `res+=freq`
            * 情况2: 第二次出现, so `res+=freq-1`, 这样的好处，如果freq=1, 则不改变，如果freq>1, 则加入其偶数次freq。
    * Lexicographically all Shortest Palindromic Substrings from a given string (Easy)
        * shortest palindrome substring is just a single character. 
        * 注意: ord('a') == 97, create an array to keep track of alphabetic characters `abcd = [0]*26`
        * time O(N), space O(1)


### 957. Prison Cells After N Days (Medium)
* 主要思路： 用hashmap记录循环
   
### 706. Design HashMap
* remove key from a dictionary `hashmap.remove('key', None)`

### 953. Verifying an Alien Dictionary
* 主要思路： create a hashmap for order, then two loops on words, one loop to loop over words, compare word with next word by looping over current word's index. 

### 136. Single Number (Easy)
* `from collections import Counter, Counter(<a list nums>)= <hashmap>`
* 相似题： 
    * 389. Find the Difference (Easy)
        * time O(N), space O(1)： 因为这边最多就26个字母，所以不是O（N)而是O（1）

### 1772. Sort Features by Popularity (Medium)
* `sorted(l, key=, reverse=False)`: by default, sort in ascending order
* sort by multiple keys `key=(key1, key2, ...)`
* 巧妙用 `set` to reduce redundent appearance, 因为feature appears in the same response multiple times only counted as once.

### 1570. Dot Product of Two Sparse Vectors (Medium, FB常考)
* 注意： 这里bruce-force的做法是直接算，但这样一来time O(n) for both constructing sparse vec and calculating dot product, O(1) for constructing the sparse vector as we simply save a reference to the input array and O(1) for calculating the dot product.
* hashmap做法： 将nonzero entries存入hashmap： time O(n) for constructing sparse vec, O(L) for calculating dot, where L is no.non-zeros in vec. Space O(L): for constructing, O(1) for calculating

================================================
## Set
================================================
* Python built-in set

#### 349. Intersection of Two Arrays (Easy)



================================================
## Linked List
================================================
很好的整理资料： https://dongxiaoran.com/algo/basic/iterativelist/

### 206 Reverse Linked List (Easy, 经典题，together with 234)
* 主要思路： create a res node NULL, let head be the current node in the list. while head, let `res.next, head.next, head  = head,res.next, head.next`

| Round | res.next=head | head.next=res.next | head=head.next |
| ------|:-------------:| ------------------:|---------------:|
| 1     | res:None->1->2->3| res: None->1->None| head: 2->3|
| 2     | res:None->2->3| res: None->2->1->None| head: 3|

* 细节： 
    * create a dummy node NULL `ListNode(float(-inf))`
    * multiple values assign to multiple variables: `cur.next, pre, cur = pre, cur, cur.next` 这一行代码实现了，三个变量的赋值，而且有个特点，变量之间是有重叠的，问题也就出现在这里了，再进一步解释，当执行赋值中的第二个赋值（pre = cur）时，其实第一个赋值并没有生效，还是保持这行语句之前的状态，同样的执行赋值语句（cur = cur.next）时，同一行的两个赋值也并未生效，在这个代码背景中，就出现了节点游离的状态。不是先第一个，再第二个，再第三个，后一个的赋值覆盖前一个。

### 92. Reverse Linked List II (Medium, 206变形题， 类似题：143)
* 与206不同的是要造一个result的替身dummy去跑, 永远让dummy去更新

### 148. Sort list （Medium, 234变形题, 类似题：143,876,21）
* 主要思路: divide and merge
    * divide: 用快慢pointer，将linkedlist 由中间分开（和题234一样）
        * 一开始slow, fast, prev都指向head, slow and fast跑，到停的时候， 示意`prev.next=None`, 此时head会随之改变
    * recursive call sortedList(head)
    * merge two sorted list, 将两部分按大小merge起来, create a dummy, while h1 and h2: merge
* LinkedList: create 一个替身tail, dummy=tail=ListNode(-1), 然后tail用来跑current node， tail.next连到的node也会体现在dummy里, dummy维持整个linkedlist
* 相似题： 
    * 876. Middle of the Linked List
    * 21. Merge Two Sorted Lists
    * 143. Reorder List: 注意 
    1. 这边merge的时候要及时delink, 否则merge会成环 (因为我们先用`after = dummy.next`去存储， 再merge的时候用`dummy.next = after`, 所以成环) 
    2. 在reverse（slow)的时候也会改变global variable slow.  

================================================
## Two-pointers
================================================

According to mechanism and usage, I have roughly classified them into five categories:
* Old and new state: old, new = new, cur_result
* Slow and fast runner: slow-> fast->->
    * ![Slow and Faster Runner Template](./assets/images/slow_fast_runner.png)
* Left and right boundary: |left-> ... <-right|
* Pointer-1 and pointer-2 from two sequences: p1-> p2->
* Start and end of sliding window: |start-> ... end->|
-----------------------------------------------

## Left-Right Boundary
### 1. Two Sum, 167. Two Sum II - Input array is sorted, 1099. Two Sum Less Than K （Easy, 经典题）
* 主要思路： two-pointer
* 细节： sort list's idx by list's values. `sorted(range(len(l)), key=lambda k: l[k])`, `lambda arguments : expression`
* 类似题： 
    * 345. Reverse Vowels of a String （Easy)
        * time: O(n)
        * space: O(n)

### 15. 3Sum (Medium, 经典题)
* 主要思路： two-pointer
    1. 先sort array
    2. lock one pointer i, and do 2 sum with the other two pointers j, k. if i+j+k对应的和< target, move j to right. (因为锁定i, 如果目前和小于target， 则将j 右移， 因为array是ascending的，往右移数越大，使其更接近target，如果碰到duplicates， i.e., 目前j和j-1数一样 e.g., `while j<k and nums[j]==nums[j-1]` e.g., `while i>0 and nums[i]==nums[i-1]: continue`， 则skip因为我们在j-1时已经检查过了和) 如果i+j+k > target, move k to left

### 1711. Count Good Meals (Medium)
* 这题我自己做的可能做的不是很好，我用的是hashmap+two-pointer的做法

### 125. Valid Palindrome (Easy, 常考)
* python `<str>.isalnum()` check if all the characters in the text are alphanumeric.
* check is s[left] == s[right]
* time: O(N), space O(1)

### 680. Valid Palindrome II (Easy, 常考)
* outer two-pointer until hit `s[left] != s[right]`, then run inner two-pointer on (left+1, right) and (left, right+1) to check if inner is palindrome.
* time O(N), space O(1)

## Fast-Slow Runner (用于找中位数/判断是否有环)
### 234. Palindrome Linked List （Easy, 经典题, similar #9(str)）
* 主要思路: 3步 
    * 第一步：findMid: 这边用到的是fast and slow pointers， fast每次走两步，slow每次一步， 先设一个dummy node， 从dummy node 开始走，until fast is none  or fast.next is none. 这样奇数个的linked-list， slow就能走到mid, 偶数个的linkedlist, slow能走到mid的左边(1->2->3->4 走到2)
    * 第二步 reverse mid 后面的那部分 利用#206
    * 第三步， compare head first half with reversed second half
* 细节：palindrome definition (对称性)
* 9. Palindrome Number: 注意可以用string[::-1] to reverse a string

### 287. Find the Duplicate Number (Medium, 相似题： 142)
因为题意说有且只有一个duplicate, 则一定有环two-pointer 将找duplicate 的问题化为环问题, 
1. 找到相遇点(乌龟每次走一步， 兔子走两步， 直到兔子赶上乌龟， 假设a = 不是环的长度, b+c为环的长度slow and faster pointer 在b点相遇因为slow pointer走了=a+b,fast pointer=a+b+c+b=a+2b+c => since 2S=F, 2(a+b) = a+2b+c=>a=c  ) 
2. 找环的开头, 再设两个指针，这次两个指针每次都走1步, 一个指针初始在开头，一个初始在b， 他两最后相遇的地方就是环的起点（因为两个分别走了a步和c步，且a=c)
* 相似题： 142. Linked List Cycle II

## Queue (FRONT, REAR也是一种two-pointer, 也是一种sliding window)
### 346. Moving Average from Data Stream
* circular queue
* time O(1), space O(N): construct the queue

## Sliding-Window

pick an easier one first.

Constrained Subsequence Sum
Number of Substrings Containing All Three Characters
Count Number of Nice Subarrays
Replace the Substring for Balanced String
Max Consecutive Ones III
Binary Subarrays With Sum
Subarrays with K Different Integers
Fruit Into Baskets
Shortest Subarray with Sum at Least K
Minimum Size Subarray Sum

More Good Stack Problems

Here are some stack problems that impressed me.

Constrained Subsequence Sum
Minimum Cost Tree From Leaf Values
Sum of Subarray Minimums
Online Stock Span
Score of Parentheses
Next Greater Element II
Next Greater Element I
Largest Rectangle in Histogram
Trapping Rain Water



### 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (Medium, Google)
* use two queues, one called `maxq` to store items in monotonically decreasing order, the other called `minq`, store items in monotonically increasing order. 
* 我们的sliding window的右端点每次会往右一格，(i.e., add j-th position item to maxq and minq).  
    * 同时跟新maxq使得maxq只保留[i,j]之间比j-th position 大的数， 更新minq使得其只保留[i,j]之间比j-th position 小的数
    * 将j-th position 加入maxq, minq
    * 我们会看if [i,j]里的max num-minnum <=k 来决定是否需要移动左端点. 
    * 如果要移， 判断 (proof is below) 是否i-th position的数是[i,j]里最大的数，if yes, remove it from maxq. 判断i-th position 的数是[i,j]里最小的数，if yes, remove it from minq. i += 1
* Time: O(N), space: O(N)
* 很好的解答： https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/discuss/609771/JavaC%2B%2BPython-Deques-O(N)

### 209. Minimum Size Subarray Sum (Medium)
* 解法1: sort then two sum. time: O(nlogn)
* 解法2: sliding window. 类似#1048，一个指针j一直往右， move指针i指着最小的window使得sum of window >= target. time: O(N) space: O(1)

================================================
## Heap
================================================
* tree-based data  structure， 用来出k closest最好, 是一种priority queue的implementation
* a heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property: 
    * in a max heap, for any given node C, if P is a parent node of C, then the value of P is >= to the value of C. 
    * In a min heap, the value of P is <= to the value of C.
* Heap in Python: 

* heapq 在python中的实现原理(假设我们在看minheap)
    1. 第一个问题：如何由一个无序序列建立成一个heap？从无序序列的第 n/2 个元素 （即此无序序列对应的完全二叉树的最后一个非终端结点 ）起 ，至第一个元素止，依次进行下沉（下沉指的是将其和其left and right node 比，选left,right中小的与其进行对调）
    2. 第二个问题： 如何在输出heap.pop()之后，调整剩余元素，使之成为一个新的heap？ 采用的方法叫“筛选”，当输出堆顶元素之后，就将堆中最后一个元素代替之；然后将根结点值与左、右子树的根结点值进行比较 ，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。
    3. 第三个问题： 新添加元素和，如何调整堆？这个的方法正好与 下沉 相反，首先将新元素放置列表的最后，然后新元素与其父节点比较，若比父节点小，与父节点交换；重复过程直到比父节点大或到根节点。这个过程使得元素从底部不断上升，从下至上恢复堆的顺序，称为 上浮 。
* time complexity (Binary n-item (min) heap )

| Type | Average |	Worst case | 
| ------|:-------------:| :-------------:| 
| Space | O(n) | O(n) |
| Search| O(n) | O(n) 还是要遍历 |
| Insert| O(1) | O(logn) like binary search, 因为要一直比较左右上浮|
| Find-min| O(1) min at the top|O(1) 因为min就在root node|
| Delete-min| O(1)|O(logn)输出以后要重新调整成为新的heap, 这个过程like binary search, 因为要一直比较左右下沉|

为什么Search is O(n)?