---
title: Leetcode Progress
tags: PlanB
---

## 9/3
### Two sum
- hash table with loops
- hash table with one loop

### Sort An Array
- quick sort (iterative solution)

## 9/4

### Sort An Array
- quick sort (iterative solution)
- quick sort (recursive solution)
- partition to fetch the pivot
- quick sort func

### Add Two Numbers
Combine two linkedlists to a new one summed by reversed order.
1 -> 2 -> 3 => 321
2 -> 4 -> 5 => 542
=> 321+542=863 => 3->6->8

- respectively caluculate the reversed value from linkedlist
:::warning
0 -> 4 -> 5
This case will be failed.
The expected result is 54 rather than 540
:::
- keep a current linkedlist and a carry variable
- carry added by value mod 10 (l.val%10)
- finally, add trailing value by carry divided by 10(carry/10)

### Valid Parentheses
- initialze a list as stack that we manipulate by pop/push

### Combination Sum III
- list all the probabilities -> backtracking
- define func first
- param you may pass in:
- cur: current result
- step: current step within fixed range [1,9]
- final result to be returned
- without redundant elements
- from the fixed range [1,9]

### Longest Palindromic Substring
- check palindrome func by sliding each side

## 9/5

### Remove Nth Node From End of List
- firstly, go through the linkedlist and get the size
- two pointer
- edge case: only one node

### Remove Duplicates from Sorted Array
- declare an index out of loop that only indicates an unique number

### Insert Interval
- one loop
- sort by the last element
- three conditions:
- give min(), max()
- add an interval if new_interval.start > interval.start
- new_interval.end < interval.start; then break
- concate results by new_interval plus the rest of intervals

## 9/6

### 01 Matrix
- running BFS in each cell will be time exceeded
- need to gather these cell more than zero
- keep a queue and iterate over surrounding cells
- if not zero, add to queue
- else assign to mat[x][y]

### K Closest Points to Origin
- calculate the Euclidean distance between nodes and the origin
- map[coordination]= Euclidean distance
- sort by value and get the top k coordinations

### Longest Substring Without Repeating Characters
- hash table keeps character and which index
- declare start variable to record the head of resulting substring
- if hash_table[char] < start; then calculate by cur - start +1
- else; start = hash_table[char] (the last index indicating the same character)

### 3Sum
- sort first
- for outer loop [0...n-2]
- if repetitive, move to the next ptr
- 2 pointer [1...n]
- in case of repetitive number
- if matching, move the left ptr to right
- if repetitive, move left

### Majority Element
- 1. sort and return the middle element
- 2. hash table accumulate and return the biggest
- 3. set count that represents the frequency of numbers; turning out to 0 means major need to be updated

## 9/7

### Climbing Stairs
1. recursive way but it ended up time exceeded
2. DP
3. memorization (set tmp and exchange a,b)

### Reverse Linked List
1. iterative
2. recursive

### Longest Palindrome
1. dual number divided first then double them
2. if len(char) % 2 == 1 and result % 2 == 0; turn XXXX to XXOXX

### Implement Queue using Stacks
1. initialze two stacks

### Permutations
1. find all the possible permutations -> back tracking
2. declare necessary arguments
- current nums
- step
- rest of nums
- result

### Non-overlapping Intervals
https://leetcode.com/problems/non-overlapping-intervals/
greedy method
1. sort by the end element
2. var end = the current end value
3. var count = how many span can be removed

overlap [1,3],[2,4],[3,5]
[4,7], [1,100]
non-overlap [1,2],[3,4],[5,6]

### Linked List Cycle
- two ptr

## 9/8

### Flood Fill
- DFS

### Merge Intervals
- sort by the first element
- compare against the last element of output

### Kth Smallest Element in a BST
- inorder
- return the i-th number

### Best Time to Buy and Sell Stock
- dp

## 9/9

### Combination Sum
- look like a backtracking problem however if do so, it ended up time exceeding
- dp: calculate all the numbers from 1 to target
- each target as key
- all the possibles as value
- outer loop: candidate
- inner loop: target number
> since candidate is allow to be repetitive and require to be expanded.

### Minimum Window Substring
1. two ptr
2. target_length: guarantee target matching
3. hash table: record frequency of words, need to take in repetitive candidates
4. be aware of hash table with negative value is possible

### Invert Binary Tree
1. recursive
2. just swap in each level

### Merge Two Sorted Lists
- simply two ptr

### Valid Anagram
> An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

## 9/10

### Binary Search
- recursive
- iterative

### Maximum Subarray
- dp

## 9/11

### Balanced Binary Tree
- Top-down: recursive
- Bottom-up: recursive but returns immediately

### Lowest Common Ancestor of a Binary Search Tree
1. hash table to store the ancestor for each node
2. recursive way

### Linked List Cycle
- two ptr: slow, fast

## 9/12

### First Bad Version
- simple binary search

### Merge k Sorted Lists
- brute force

### Longest Palindromic Substring
- two pointer is better and simple
- dp solution is hard to implement though
- dp[i][j] .. if i to j is palindrome
- two loops
- outer loop is forward
- inner loop is backward
- s[i] = s[j]
- j - i = 1
- X[\*]X
- dp[i+1][j-1] = true
- means the prev result is palindrome

### Binary Tree Level Order Traversal
- BFS
- recursive way fn(root, res, level)

## 9/13

### (repetitive) Longest Palindromic Substring
- do dp manner

### Longest Palindromic Subsequence
- do dp manner
- little differnece is that condition of `end-start==1` is not necessary as no matter what residual charaters i.e., aa, bb, acccb, abcda, we normally add 2 as well.

### (repetitive) 3Sum
- sort then iteration and 2 ptr
- be care of repetitive results
- filter out or skip the same num

### (repetitive) Lowest Common Ancestor of a Binary Search Tree
- recursive way
- once p or q is identified, return the root
- if missing either q or p on one side(left,right), either left or right node would be None
- checking root in prior makes sure if root is q or p will be an answer.

### Minimum Height Trees
- Basically, the idea is to eat up all the leaves at the same time, until one/two leaves are left.
- node number maps to a set which records the dest
- iterative way to update the leave list
- leave node: only one connection

### Add Binary
- add two binary representation with string type
- iterative way
- carry/remain updated every round

### (repetitive) Combination Sum
- use dp since backtrack got time exceeded
- dp: depends on target i, the possible combs exist

## 9/14

### (repetitive) Binary Tree Level Order Traversal
- recursive way fn(root, res, level)
- first define a helper func used to record level result
- second prepare the main logic. declaring res as well as calling func and returns
- organize the body of func
- be careful about adding value need to be followed by the cond of root exists or not
- as example [] or [1] has the diff result though

### (repetitive) Minimum Height Trees
- several approach reviews

### Diameter of Binary Tree
- be careful of the strating root the answer may not be started from given root
- `max(depth(left)+depth(right), fn(left), fn(right))`

### Middle of the Linked List
- only slow fast 2 ptr

### Maximum Depth of Binary Tree
- simply recursive max(left,right)+1

### Contains Duplicate
- simply hash table detection repetition

### Coin Change
- typical dp solution
- min(dp[i], dp[i-c]+1)

### Spiral Matrix
- brute-force

### Word Search
- dfs
- remember to tag back the passed element

### Subsets
- backtrack

### Review of Intervals

Merge Intervals
1. sort by the start element

Insert Interval
> Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals
1. pass by top k intervals
2. pass by the rest intervals
3. insert new interval
- change the context
- not change the context
- just pick up the min and max

returns previous k normal intervals + newIntervals + last n intervals

Non-overlapping Intervals
> return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
1. sort by the end element
- check if the start element is behind the previous end
2. declare two parameters: the end element as far ; count as a result
3. iterate over intervals
4. check if prev_end > interval_start ?
- Yes, it means that the interval need to be removed
- No, it means there is no overlapping
5. return count

## 9/15

### Minimum Path Sum
- dp

### Longest Increasing Subsequence
- dp[i]: LIS till the index i
- dp[i] = max(dp[i], dp[j]+1)
- pick the current dp val or current dp plus the last element(+1)

### Longest Substring Without Repeating Characters
- slding window
- max of non-repetitive substring
- why not use dp?
- dp typically used when the solution comprised of several sub-solutions. however, repetition problem probably does not fully leverage the sub-solution as there may be repetitive if taking on another solution.
- declare start, hashtable to record the indices of characters and the maximum
- val in hashtable:
- update start index ?
- when ht[val] >= start and also move on 1 unit
- when ht[val] < start, then update the maximum val
- update the maximum val
- update ht

### Minimum Size Subarray Sum
- sliding window
- declare min, start and total
- total is necessary due to time limit exceeded

### Longest Common Subsequence
- dp
- tip: add row 0st and column 0st; for computing purpose

### Course Schedule
- form a hash table to store the prerequisite list
- every time, delete leaves and update the hash table
- if input course set is empty, returns True
- otherwise, when leaves set is empty and hash table having k-v pair then returns False

## 9/16

### Binary Search
- recursive
- iterative

### Word Search
- dfs
- filter out if charater with word is missing over input board

### Ransom Note
- simple hash table for word frequency count

### Implement Trie (Prefix Tree)
- create a Trie struct

### Fruit Into Baskets
- sliding window
- hash table to store distinct fruits and count
- if count reaches zero, then remove from the hash table

### Product of Array Except Self
- prefix sum

## 9/20

### Minimum Window Substring
- sliding window
- allow repetition
- declare word counter
- declare matching length

### Min Stack
- create stack struct
- get minimum by O(1)

### Number of Islands
- DFS
- update the visited cell

### Rotting Oranges
- BFS
- need to think more of edge cases

## 9/21

### (repetitive) Combination Sum
- dp
- like coin change

### Time Based Key-Value Store
- care of binary search left&right ptr

### Task Scheduler
- hash table

> ["A","A","A","B","B","B", "C","C","C", "D", "D", "E"]
2

i.e., ABCABCABDCED
calculated as (3-1)*(2+1)+3 = 9

the reason why the result is more than which length is that from the prev measures we assume numbers with maximum frequency would be left so that we do (+3). In fact, these numbers with maximum frequency are used beforehand and no idle there.

### Sort Colors
- sort in place
- 3 of pointers move on

### Binary Tree Right Side View
- BFS
- rightmost each level

## 9/22

### (repetitive) Binary Tree Level Order Traversal
- keep a level-indexed array
- helper func along with level number

### Steps to Make Array Non-decreasing
- dp
- dp[i] means the number of element nums[i] can eat on its right
- brute-force approach will exceed the time
- get rid of elements at the simultaneously
- care of the overlapping cases:
- 1,2,3,4,5 that's ok
- 14,13,2,5,13, where 2ed 13 is overlapping as "14,13,2,5" and "13,2,5"; here 14 need to take 3 rounds otherwise 13 takes 2 rounds. but here is the thing, 14 and 13 get rid of elements at the same time. it means both 13 and 2 would be removed. thus, we have 1 overlapping count. so the dp function can be written as dp[i] = max(dp[i]+1, dp[stack__last_idx]); dp[i]+1 indicates to take 1 round.

### Partition Equal Subset Sum
- dp
- `dp[i] = dp[i] | dp[n-i]`
- similarly, 0/1 knapsack
- why use dp ?

dp: final solution can be measured by sub-solutions.
i.e.,
target = 5
dp would trace target from 0 to 5
over a iteration, when target is 2, we measure by dp[2] = dp[2] | dp[5-2]
if 2 exists in array, dp[2] would be True
when it comes to 5, dp[5] = dp[5] | dp[5-2]
if there is 3 in the future, dp[5] will be True.

arr = [2,2,3,2,2,3]

for i in arr:
for j as target to -1:
dp[j] = dp[j] | dp[j-i]

## 9/23

### (repetitive) Word Search
- dfs either
- tag the cell we'd pass through
- if use grids directly, remember to restore the origin numuber, so that next time we can walk in this cell again
- if we pass an additional argument as grids, it turns out to time limit exceeding.

### Concatenation of Consecutive Binary Numbers
- bit manupulation

:::success
`i & (i - 1) = 0` identify if i is power of 2.
i.e.,
100, 011 -> 0
:::
after removal, if it is 0, then it means it is power of 2

if it is power of 2, we increase the bit length `l`

`res = ((res << l) | i) % (10**9+7)`
where (res << l) means left-offset `l` is the current maximum expands

otherwise, ((res << l) | i) aligns with the rest portion.

### Longest Palindrome

### Longest Palindromic Substring
- sliding-window at each elemet
- 2d dp

### Longest Palindromic Subsequence
- 2d dp
- 1d dp: declare a pre to store the previous result as every time the dp element will be refresh.

### Longest Common Prefix
1. find the minimum length of string set
2. compare against the first element

### Longest Increasing Subsequence
1. 1d dp

## 9/24

### Longest Common Subsequence
1. 2d dp
2. 1d dp (mem space optimized)
- prev to record the previous dp
- every iter overrites the dp and keep trace with prev

### Longest String Chain
1. sort by string length: make sure each iteration that element consists of those previous words.
2. init dp map: (k,v) = (token, longest_chain_size)
3. every iteration, try to find the previous token and keep track with dp func: dp[token]=max(dp[token], dp[prev]+1)

### Longest Repeating Character Replacement
- sliding window
- every iter, find the current maximum frequent word where we know the rest of words supposed to be substituted. (cur_len - maximum_freq)
- since k represents the replace times, it's satisfied with formula as (cur_len - maximum_freq) <= k
- if (cur_len - maximum_freq) > k, left ptr should move on forward until iter reaches the end.
- it gauranee that (length - left ptr) is the longest repetitive length.

### Accounts Merge
- Union Find
- DFS

## 9/25

### Word Break
- dp
dp[i]: considering string from 0 to index i, j <= i, if dp[j-i] is in the word dict and dp[j] is True, then dp[i] can be composed of prev pieces.

### (repetitve) Valid Anagram

### Smallest Subarrays With Maximum Bitwise OR
init an array to store bitwise entries with 1 -> last[32]

iterate from end to head since every time each entry tries to find out the maximum bitwise OR element til the end.

scan from tail to head that help us find the termination firstly.

`nums[i] & (1 << j)` catches the leftmost 1 of nums[i] which indicates the current entry with maximum 1

`max(last)` means the index from i which includes additional 1 by far

## 9/26

### Longest Subarray With Maximum Bitwise AND
the bitwise AND of two different numbers will always be strictly less than the maximum of those two numbers
so the longest subarray with max bitwise AND would be the subarray containing only the max numbers.

### Construct Binary Tree from Preorder and Inorder Traversal
- value in preorder is the top node
- be aware of the terminated condition:
- when left > right, go through the list properly
- recursively calculate the left & right

### (Redo) Course Schedule
- prefix sort

### Find All Anagrams in a String
- sliding window

### Container With Most Water
- sliding window

### Perfect Squares
- dp
- dp[i] = min(dp[i-j^2]+1, dp[i])

### Jump Game II
- greedy

### House Robber
- dp

## 9/27

### Review of Intervals x2

Merge Intervals

sort by the first entry
initialize res consists in intervals[0]
condition:
    - merge: res[-1][1] >= intervals[i][0]
    - append: res[-1][1] < intervals[i][0]

**only need to compare to the second entry**

Insert Interval

sort by the second entry
initialize index which will be utilized in the loop
initialize pre to store the previous original intervals

attempt to obtain the result composed of -
pre + newintervals + the rest of Intervals

condition:
    - append: newInterval[1] < intervals[idx][0]
    - break loop: newInterval[0] > intervals[idx][1]
    - otherwise: update newInterval[min,max]
    
**sort by the second entry makes sure newInterval is isolated from previous intervals**

Non-overlapping Intervals

sort by the first entry
initialze count = 0
condition:
    - find min: intervals[r-1][1] > intervals[r][0]
    intervals[r][1] = min(intervals[r-1][1], intervals[r][1])
    count++
    
key: tune the second entry each interval only as we try to count the removed number as less as possible.

### (Redo) Steps to Make Array Non-decreasing
- dp[i]: ith result need how many times removing action ?
- stack: store numbers less than the current.

dp[i] = max(dp[i] + 1, dp[idx])

where `dp[i] + 1` keeps adding smaller num
`max(dp[i] + 1, dp[idx])` picks up the exact times while processing in parallel.

## 9/28
### linkedlist review (Easy level)

Merge Two Sorted Lists

concept: two pointers
initialize an integrated linklist as a result
do while l1 and l2:
    cur.next = l1 | l2
if l1, then cur.next = ll
if l2, then cur.next = l2

Remove Duplicates from Sorted List

while head.next and head.val == head.next.val: 
    head.next = head.next.next

Linked List Cycle

# walk through total n/2 steps

slow = head
fast = head.next
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

**Intersection of Two Linked Lists
- exchange two lists
- if length is not equal, the second round iteration will access the intersectional node or None simultaneously.

little tricky

while listA != listB:
    listA = listB if listA is None else listA.next
    listB = listA if listB is None else listB.next

Remove Linked List Elements

conditions:
    - the first node gets removed
    - the next nodes get removed

recursive way: 
    1. return fn(head.next, val)
    2. head.next = fn(head.next, val)
2-ptr way:
    init slow, fast
    if fast.val == val:
        slow.next = fast.next
    else:
        slow = slow.next

Palindrome Linked List

 2 ptr: slow/fast
     - odd: get rid of the middle element
     - even
 reverse
 or
 2 ptr: slow/fast with stack approach

Middle of the Linked List

 2 ptr: slow/fast

Convert Binary Number in a Linked List to Integer

 res = res * 2 + head.val

### K Closest Points to Origin

### Remove Nth Node From End of List
1. obtain the actual length of ll
2. convert n into length - n (real index from head to tail)
3. 2 ptr: count == 1 represents the prev node

## 9/30

### (Redo) Longest Palindromic Subsequence

## 10/1

### Flood Fill
- dfs

### Best Time to Buy and Sell Stock
- sliding...
- keep the minimum and iterate over the nums
- calculate profit each step

### Get Maximum in Generated Array
- dp

## 10/2

### 01 Matrix
- topological sort
- start off from cells of 0, and then proceed 1,2,...
- init a queue
- if hit the maximum that should be save back to the queue

- dp
- more straight-forward
- calculate left-top and go backward right-bottom

### Trapping Rain Water
- sliding window
- two pointer

# keep the maximum side
while left < right:
    if height[left] >= height[right]:
        right -= 1 # move the right ptr back 
    else:
        left += 1 

# keep the maximum left/right
# add the max-current as the result
while left < right:
    if height[left] >= height[right]:
        right_max = max(right_max, height[right])
        res += right_max - height[right]

    else:
        left_max = max(left_max, height[left])
        res += left_max - height[left]

### Maximum Profit in Job Scheduling
- sort: O(nlgn)
- binary search: O(nlgn)

- time exceeding: find the closet period which is less than the current start time

### Merge k Sorted Lists
- merge 2 lists
- set up intervals
0 1 2 3 4 5
0 2 4
0 4
0 (result)

## 10/3

### Diameter of Binary Tree
> For every node, length of longest path which pass it = MaxDepth of its left subtree + MaxDepth of its right subtree.

max = (left+right,fn(root.left),fn(root.right))

### Decode Ways
1. 1 dim dp
2. init dp[0] = 1; dp[1] = int(s[0]!='0')

### LRU Cache
1. doubled linkedlist

### Find Median from Data Stream
1. binary search
2. advanced: two heaps: one store the negative num and the other preserve the positive num; keep balance

### Pascal's Triangle II
1. recursive way

### Best Time to Buy and Sell Stock
- only buy/sell once repectively
- set up 2 vars
- max
- min

### Best Time to Buy and Sell Stock II
- reset min if prices[i] > minimum
- dp:
- every time, if prices[i] > prices[i-1], then sum all over(prices[i] - prices[i-1]) for each i

## 10/4

### Partition Equal Subset Sum
- split in 2 subsets
- cond: n % 2 == 0
- cond: target = n // 2
- dp[i]: if i could be assembled ?

dp[i] = dp[i] | dp[i-n]
# dp[i-n]: if n is picked up, dp[i-n] dominates the result basically.

target=3, n=1 # 2,1,0
dp[3] = dp[3] | dp[2] # pick 1, check dp[2] where dp[2]=Flase, so dp[3]=False 
dp[2] = dp[2] | dp[1] # pick 1, check dp[1] where dp[1]=Flase, so dp[2]=False 
dp[1] = dp[1] | dp[0] # pick 1, check dp[0] where dp[1] = True

target=3, n=2 # 1,0
dp[2] = dp[2] | dp[1] # pick 1, check dp[1] where dp[1]=True, so dp[2]=True 
dp[1] = dp[1] | dp[0] # dp[1] = True as usual

:::warning
dp[0] = True
dp[target] represents that it apprears with target number.
:::

### House Robber
- dp

### House Robber II
- circular array
- divided into arr[1:] & arr[:-1] that make sure 1st and the last element would not be picked up at the same time.

### Edit Distance
- hard
- dp
- min(insert, remove, replace)

### Best Time to Buy and Sell Stock III
- hard
- dp

dp[k, i] = max(dp[k, i-1], prices[i] - prices[j] + dp[k-1, j-1]), j=[0..i-1]

k: kth transaction
i: ith day

for each iteration, minimum of the previous transaction should be calculated

## 10/5

### Merge k Sorted Lists
- merge 2 lists for each iteration
- set up interval to make sure the next pointer has not used
- be sensitive to rolling in the interval for every iteration.
- the final result would be at index 0

### Perfect Squares
dp
- the latest number of perfect square numbers that sum to n.

dp[i] = min(dp[i-j**j]) + 1

where +1 means that we'd like to add a perfect square j*j as we've alr preserved the least number dp[i-j*j] then just add it.

BFS
> reach n as soon as possible

[1,12]
q=[1,4,9]
q=[4,9] as pop 1
q=[4,9,2,5,10] as 1+1, 1+4, 1+9
q=[9,2,5,10,8] as 4+1 exists and 4+9 > 12
q=[2,5,10,8] as 9+1 exists and 9+4 > 12
q=[5,10,8,3,6,11] as 2+1, 2+4, 2+9
q=[10,8,3,6,11] as 5+1 exists and 5+4=9, dp[9] != 0 and 5+9 > 12
q=[8,3,6,11]
then pop 8, 8+1 exists, 8+4 hit!

### Find First and Last Position of Element in Sorted Array
- two binary search: find the first and the last separately

### Ugly Number II
- dp
- set 3 ptr and pick up the minumum multiple as well as increase the ptr

## 10/6

### Min Stack
- implemented min stack struct
- linkedlist implementation
- val, min, next
- push/pop/min: O(1)
:::success
O(1): hash table, index
order by value (get minimum): memcache, linkedlist
:::

### Time Based Key-Value Store
- 2d hash map:
- key
- timestamp
- value

### Find Right Interval
- time exceeding: sort, 2-ptr
- should be: sort, binary-search

## 10/7

### Contains Duplicate

### Sudoku Solver
- backtrack

valid func:
> check if number exists or not?
- check against row
- check against column
- check against the 3*3 sub-box

step:
1. find "." cell
2. backtracking: put x from [1,9] and valid()
3. valid()=True, fill in x and valid() again, if True return True;otherwise, put "." back

### Decode String
- stack can preserve the current string and times
- be care of double digits(i.e., 13): k = 10*k + digit

### (Redo) Merge Intervals

### (Redo) Non-overlapping Intervals

### (Redo) Find Right Interval

### (Redo) Insert Interval

### Remove Covered Intervals

### Lemonade Change
- greedy
- coin change problem

## 10/9

### Sort Colors
- sort in place
- order by 0,1,2

### Best Time to Buy and Sell Stock with Cooldown
- state machine
- max profit
- maximum profit appears in 3 of states

no-op state: cool down from sell state or keep in no-op state
sell state: sell stock from buy state
buy state: no-op state followed by buying stock or keep in buy state

gain the maximum profit from max(no-op state, sell state)

buy state means that we hold the stock and never sell it so that it will not be the maximum profit.

## 10/10

### Accounts Merge
1. set a map of email to []indices
> bridge relationship among different emails, i.e.,
> [e-mail] -> [1,2]
> [e-mail] -> [1,3]
>
> where [e-mail] and [e-mail] have relationship.
2. DFS (Union Find)
> dfs(idx, mail_set)
> mail_set collects all the passed emails
> mail2indices[mail] represents its neighbor which is used to find involing candidate set.

## 10/11

### Diameter of Binary Tree
- dfs: based on n as root, to measure level for each side
- remember that every single is possible to be root

max(
    dfs(root.left)+dfs(root.right), 
    diameterOfBinaryTree(root.right), 
    diameterOfBinaryTree(root.left)
)

### (Redo) Construct Binary Tree from Preorder and Inorder Traversal
- preoder records the root first
- inoder records two sides according to root

1. find root first -> pop 1st from preoder list
2. find left substree & right subtree -> search from inoder list
3. recursively 1,2 (cuz preoder pop 1st, next time need just move on to pop 2ed again)

preorder: root, left, right

identify root from preorder list
DFS on left side
DFS on right side

traverse forward

### Construct Binary Tree from Inorder and Postorder Traversal
preorder: left, right, root

identify root from postorder list
DFS on right side
DFS on left side

traverse backward

### Binary Tree Level Order Traversal II
1. top-down traverse
2. BFS
3. reverse list

### Construct Binary Tree from Preorder and Postorder Traversal
- preoder: HLR
- postorder: LRH
- preIndex, postIndex start from 0
- recursive way

pop root up according to pre_index
pre_index++ # check the next preorder index
root.val != postorder[post_index]; then root.left = fn() # left be prior to right
root.val != postorder[post_index]; then root.right = fn() # left be prior to right
post_index++ # check the next post_index

### Serialize and Deserialize Binary Tree
- inorder/preorder/postorder all be fine
- None needs to be recorded, otherwise, we need two lists: inorder & preorder/postorder
:::danger
List of value to a whole Tree
- bfs recover
- iter + next
:::

### (Redo) Unique Paths
- 2d dp

### (Redo) Longest Palindromic Substring
- 2d dp

## 10/12

### Largest Perimeter Triangle
- sort

### (Redo) Reverse Linked List
- recursive version

### (Redo) Minimum Size Subarray Sum

### (Redo) Smallest Subarrays With Maximum Bitwise OR
- find subarray
- Maximum Bitwise OR: the leftmost bit is 1
- number_i OR number_i+1 reduces to

0 <= j < 32
last[j] = nums[i] & (1 << j)

max(last) represents the position of leftmost 1

### Binary Subarrays With Sum
- sliding window

1. set number Counter as {0:1}
- Counter[0]=1 as hit the goal
- Counter[total]=N
- N posibilities while sum of substring reaches total
2. set variable as accumulation and result res
3. iterate over nums:
- accmulate each number

## 10/13

### Palindrome Partitioning
- typical backtracking

### Delete Node in a Linked List

### Sort Integers by The Power Value
- dp

### Gas Station
- greedy
- total diff(gas, cost) >= 0, then we get the ans
- if obtain negative result, proceed start pos to the next index and reset the gas volume as well as journey record.

### (Redo) Longest Palindromic Subsequence
- 2d dp
- typical solution
- 1d dp
- space efficiency
- for each iteration, keeps the previous round dp result

### (Redo) Longest Palindromic Substring
- 2d dp

## 10/14

### (Redo) Majority Element

### Majority Element II
- advanced: linear time and space complexity: O(1) - Boyer–Moore majority vote algorithm

### Delete the Middle Node of a Linked List
- 2 ptr
- odd/even

### Unique Substrings in Wraparound String
- record the maximum matching substring
- dictionary to store a-z and each possibility

## 10/16

### String Compression II
- dp
- need cache otherwise time exceeding

Given string s, deleting quota k, to find the shortest compressed string

s=aaabb, k=2 => a3b2 -> a3

min(keep, delete)
- keep: don't remove the current num
- delete: remove the current num, k-1

decimal offset
- a to a2
- a9 to a10
- a99 to a100

record the previous character
- emphasis on keep
- a to a2, checked out by the previous
- a to ab, we can keep ab

length increasing
- first charater
- "" -> "a"
- "a" -> "ab"
- decimal offset

terminated state
- reach the last character
- k < 0: reutrn inf since it has no quota

### (Redo) Contain Duplicate
- set

### (Redo) Longest Substring Without Repeating Characters
- sliding window

### (Redo) Clone Graph
- dfs
- deep copy

### (Redo) Maximum Subarray
- simple dp

### (Redo) 3Sum

## 10/16

### (Redo) Number of Islands
- dfs

### (Redo) Course Schedule
- topological sort

### (Redo) Coin Change
- dp

### Minimum Difficulty of a Job Schedule
- dp
- need cache othereise time exceeding
- k bins
- min(sum(maximum of each bin))

## 10/17

### Check if the Sentence Is Pangram

### Construct String from Binary Tree

### Longest Consecutive Sequence
- hash set
- check beside values even if they do not exist in an array (+-1)
- O(n) finished

### Word Break II
backtracking
memorization: avoid time exceeding

### (Redo) Word Break

dp[i]: if s was composed of items of wordDict until index i

### Review of Construct Binary Tree

Construct Binary Tree from Preorder and Inorder Traversal

Construct Binary Tree from Inorder and Postorder Traversal

Construct Binary Tree from Preorder and Postorder Traversal
- different logic
- recursive way
- iterative way (stack): better to trace again

Construct Binary Search Tree from Preorder Traversal
- different logic
- recursive way (need inf bound for termination)

## 10/18

### Spiral Matrix II

### (Redo) LRU Cache
- doubled linkedList

### (Redo) Kth Smallest Element in a BST
- preorder

### (Redo) Power of Two

n & (n-1)

10
01

100
011

10000
01111

### (Redo) Merge k Sorted Lists

### Kth Largest Element in an Array
- quick select

### Last Stone Weight
- heapify

## 10/19

### Rotting Oranges
- bfs

### Top K Frequent Words
- priority queue/heap queue
- heapq

x = []
heapq.heapify(x) # linear time, in place

heap[k] <= heap[2*k+1]
heap[k] <= heap[2*k+2]

### Increasing Triplet Subsequence
- Greedy

## 10/20

### (Redo) Partition Equal Subset Sum

// i from n to target
dp[i] = dp[i] or dp[i-n]

### Design Twitter
- priority queue

### Car Pooling
- Same as 253. Meeting Rooms II.
- Track the change of capacity in time order
- [capacity, from, to]

Save all time points and the change on current capacity
- one trip would be [from, capacity] and [to, -capacity]
    
Sort all the changes on the key of time points.
Track the current capacity and return false if negative
- sequntially check each timestamp if capacity would be less than 0

Time O(NlogN) --> sort
Space O(N) --> copy with sorted array

## 10/21

### (Redo) Subsets

### (Redo) Contains Duplicate II

### (Redo) Minimum Window Substring

### (Redo) Implement Queue using Stacks

### Range Sum Query 2D - Immutable
- prefix sum

### Sliding Window Maximum
- priority queue

preserve a heap
preserve a result
for i := range nums
    // while-loop to check i-k >= heap.first.index (the minimum within last window)
    push (-score, index) to heap
    if len(heap) >= k:
        // start to add into result

## 10/23

### Set Mismatch

- find out duplicate from a sequence of numbers
- find the missing value from a sequence of numbers

declare n length of given array
declare a sum of given array
declare b sum of set of given array
calculate s the accumulated sum over [1, n]
obtain the duplicate via a-b
obtain the missing value via s-b

### Subarray Sum Equals K
prefix sum
1. generate every cumulate sum at first
2. sum of subarry computed from i to j
4. find a subarry: the difference bwtween two subarrys is equal to k; i,sum([...])=k, j

### (Redo) Merge k Sorted Lists

## 10/24

### Maximum Length of a Concatenated String with Unique Characters
- backtracking

### Pow(x, n)
- recursion

### (Redo) Word Search

### (Redo) Fruit Into Baskets
- sliding window

### Count Complete Tree Nodes

### K-th Smallest Prime Fraction
- brute-force O(n**2)
- pq

### Cheapest Flights Within K Stops
- Dijkstra (TLE)
- pq
- Bellmen-Ford
- deque

### Next Permutation
- little tricky
- find the next combination in-place
- 123, 132, 213, 231, 312, 321

from right to left, find the acending number first met
i.e., 1<3>654
swap the number just greater than the target number
i.e., 1<3>654 -> 1<4>65<3>
reverse the following numbers
i.e., 14456

### Longest Substring with At Least K Repeating Characters
- recursion

### Surrounded Regions
- surrounding edges do not be turned
- give surrounding edge a sign
- finally, iterate over regions and turn them back to O and X for each island.

### Longest Consecutive Sequence
- hashset
- find the first ascending number

### Convert Sorted List to Binary Search Tree
- recursion

## 10/26
### (Redo) Longest Substring Without Repeating Characters

## 10/27

### Continuous Subarray Sum

Let pref[i] denote the sum of 
the first i elements of the array nums,
i.e. pref[i]=nums[0]+nums[1]+⋯+nums[i−1]

(pref[r+1]−pref[l])%k = 0
is equivalent to
pref[l]%k=pref[r+1]%k

pref[0]=0 allows us to consider 
subarrays starting at the beginning of
the entire array.

## 10/28

### Sort Array
- use quick sort

### (Redo) Trapping Rain Water
- Monotonic Stack
- monotonic increment
- monotinic decrement
- O(n): every element would be popped and pushed once
- Steps:
- keep 2 variables: left maximum & right maximum
- scan over the array from two sides (2 ptr)
- if arr[left] > arr[right], then we explore the water from the rightmost (since the maximum height must be equal or less than arr[left])
- otherwise, exploring the leftmost

### (Redo) Find All Anagrams in a String
- hash table + sliding window
- preserve pattern p length
- preserve left & right ptrs
- preserve ht Counter(p)
- Steps:
- iterate over array, for each i
- if ht[i] > 0, then ht[i]-1
- if reach p length, then add the start index
- otherwise, move left ptr forward and restore the ht[i] from 0 to N

other numbers in the hash table is added by left moving.

## 10/29
### (Redo) Middle of the Linked List

### Smallest Subsequence of Distinct Characters
- Monotonic Stack
- preserve the last index of array
- if the last idex is more than the current step, we keep it in the stack
- compare the last element from stack against the current value.

### Reverse Nodes in k-Group
- hard
- liknedlist reverse

## 10/30

### (Redo) Delete the Middle Node of a Linked List
- fast, slow ptr
- 3ed ptr as prev slow

prev_slow.next = slow.next

### House Robber III
- dp
- recursive way: substructure
- bottom up: sunstructure + subproblem
- greedy
- keep an array
- pick root up
- don't pick root up

### Shortest Path in a Grid with Obstacles Elimination
- seem to be medium but it's attribute to hard
- simple bfs
- queue = [x,y,k,step]
- seen denotes walked paths

## 10/31
### (Reodo) Minimum Path Sum
- dp

### Toeplitz Matrix
- matriA matrix is Toeplitz if every diagonal from top-left to bottom-right has the same elements.

### Evaluate Division
- build up a graph
- Union Find
- DFS
- remember to turn on/off visited flag
- node as (next, weight)
- weight: a->b = a/b = 3
- weight: b->a = b/a = 1/3

# 11/2

### Where Will the Ball Fall
- DFS
- check 2x2 block

### Minimum Genetic Mutation
- BFS
- word A and word B exactly have 1 difference.
- topological sort
- simple version of word ladder (hard)

# 11/3

## Longest Palindrome by Concatenating Two Letter Words
- hash table
- a-z hash table
- 2 literals is known
- possible combs is up to 26*26
- substring is even: directly add identical pairs
- substring is odd: add identical pairs-1
- Finally, add 1 if substring is odd

# 11/5

### Reverse Vowels of a String

### Serialize and Deserialize BST

### Largest Number
- greedy
- change comparable function
- leading number is important

## 11/6

### Orderly Queue

### Wildcard Matching
- hard
- dp: variant of LCS
- finite machine (awesome solution)
- '*': state -> state
- otherwise: state -> state+1

## 11/7

### Maximum 69 Number

### 1792. Maximum Average Pass Ratio
- priority queue

### 1774. Closest Dessert Cost
- BFS
- take care of negative outputs
- backteacking
- for each base_count
- preserve total, index of toppings

### 1775. Equal Sum Arrays With Minimum Number of Operations
- greedy
- Count the increases and decreases
- preserve a Counter to keep differnece of
- big sum: need distract
- 6-x
- small sum: need increment
- x-1
## 11/8

### 1544. Make The String Great

### 979. Distribute Coins in Binary Tree
- binary tree
- put coins until tree balanced

### 315. Count of Smaller Numbers After Self
- brute-force: TLE
- merge sort

## 11/9

### Online Stock Span
- Monotonic Stack

### 154. Find Minimum in Rotated Sorted Array II
- binary search on rotated array
- edge case
- [3,3,1,3], mid=3, equal right, suppose find the right side
- [1,3,3,3], mid=3, equal right, suppose find the left side
- solution: move right ptr backward

## 11/10

### 1047. Remove All Adjacent Duplicates In String

### 374. Guess Number Higher or Lower

### 464. Can I Win
- backtracking
- lru_cache
- tuple({the rest of choices})
- desired left amount

## 11/11

### 26. Remove Duplicates from Sorted Array

### 85. Maximal Rectangle
- hard
- dp
- left: records the left bound of rect
- right: records the right bound of rect
- height: records the height from the top

## 11/12

### 295. Find Median from Data Stream
- addNum: insert by binary search and keep the array sorted, meanwhile, preserving the median additionally.

### 316. Remove Duplicate Letters
- stack: preserve an unique stack and keep in lexicographical order.
- greedy
- Greedy choice property
- Optimal substructure

## 11/13

### 151. Reverse Words in a String
- follow-up: space complexity: O(1)

### 49. Group Anagrams
- counting sort (since all the letters would be lower case)
- hash table[tuple]

### 289. Game of Life
- keep in previous elements of grid

## 11/14

### 947. Most Stones Removed with Same Row or Column
- dfs/bfs
- remove the largest number of stones
- remove stone once it connects to neighbor stones.

## 11/15

### 1023. Camelcase Matching
- ptr to pattern
- ptr to query

### 1024. Video Stitching
sort
- like jump game-
- keep the maximum end

dp
- dp[time] indicates minimum number of clips until specific time

for each time t
    for each clip c
        if c.start <= t <= c.end;then
            update dp[t] = min(dp[t], dp[c.start]+1)

## 11/17

### 223. Rectangle Area
- interval measurement

### 836. Rectangle Overlap
- easy version of the above

### 1823. Find the Winner of the Circular Game
- Josephus Problem
- linkedlist removal
- recursive (space complexity=O(n))

> moving on to the next kth person (i.e. f(n) = f(n-1)+k)
> have to rotate:
> (i.e. f(n) = (f(n-1)+k)%n)

- iterative (space complexity=O(1))

## 11/23

### 36. Valid Sudoku

https://leetcode.com/problems/valid-sudoku/description/

- consider 3 of conditions:
1. cells along with this row
2. cells along with this column
3. cells grouped in this 3*3 box
- create a hashtable/or simply a set collecting 0-9. Numbers are only allowed to be appeared once.

Follow-up:
sudoku solver
https://leetcode.com/problems/sudoku-solver/description
- backtracking
- bfs

### (Redo) 3. Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

- sliding window & hash table
- keep in mind the start/left pointer
- initially set to 0
- update pointer by max(pointer, prev_idx+1) as long as hash table collision
- where +1 means to move forward to the next character. i.e., (abca) -> (bca)

## 11/26

### (Redo) 1235. Maximum Profit in Job Scheduling

l