note.txt

Two Pointers(start, end)
    Usually used when the array is sorted. 
    Finding a target by narrowing down the range from the [start, end].
    
    #Format
        while(start <= end)
            if(something) // Found the answer
                return result;
            else if 
                start++;
            else 
                end--;
    
DFS
    Find constraint satisfaction paths or routes.
        -> sometimes go backward from destination and checking all paths as a successful path.
            ex) 130. 
    DFS(){
        visited[src] = true;
        for(neighbor : neighbors[src]){
            if(!visited[neighbor] /* and other constraints*/){
                /* DO not mark visited here!!*/
                DFS(neighbor); //push unvisited node to call stack!
            }
        }
        // if we want to find all paths
        visited[src] = false
    }
    Finding All Path Time Complexity : O(V+E)*O(V!)[max number of paths] = O(V!E) Print single path (O(V+E)) for all paths. 
    procedure DFS(G, v) is
        label v as discovered
        for all directed edges from v to w that are in G.adjacentEdges(v) do
            if vertex w is not labeled as discovered then
                recursively call DFS(G, w)

DFS & BFS 
    WHERE SHOULD WE CHECK VISITED?
    FOR BFS it does matter because nodes at same level could push the same node twice!
    ex) A, B is in same level, C is neighbor of both A,B. then C is inserted twice.
    
    PATTERN A) make it visited when we add nodes to the queue
    REMEMBER : for starting point, we cannot make it visited cause it is already in the queue
    Thus, we should make it visited before!!
        BFS(){
            visited[src] = true; // set starting node to TRUE 
            while(!q.empty()){
                q.pop();
                for(neighbor : neighbors[src]){
                    if(!visited[neighbor] /* and other constraints*/){
                        visited[neighbor] = true;
                        q.push(neighbor);
                    }
                }
            }
        }
    
    PATTERN B) just push it, and check it when we pop it
        BFS(){
            while(!q.empty()){
                cur = q.front();
                q.pop()
                if(visited[cur] /* or other constraints*/)
                    continue;
                visited[cur] = true;
                
                for(neighbor : neighbors[src]){
                    q.push(neighbor);
                }
            }
        }
    
    In general, pattern B takes more time and memory because it allows redundant push to queue

Sliding Window
    When should we use?? 
    Searching through something consecutive and sequential(ex. substring)

    [0 1 2 3 4 5 6 7 8] (SIZE : N)
    {A B C}             (SIZE : M)
      {A B C}
        {A B C}
    Time complexity : O(MN) => O(N) possible
    When moving a Window, there are duplicate calculation(the indices that are redundant)
    So, just -previous starting point + previous SUM + current end = current window's result .
    Just update the result by subtrating and adding an offset
    EX) Algo1-567
    0 1 2 3 4 5 6
    v v v => func(0) + func(1) + func(2) = prevSum
      v v v => preSum - func(0) + func(3) = prevSum
        v v v => preSum - func(1) + func(4) = prevSum ... on & on
    
    Using this, proceeding the Sliding Window can be done in one loop.

    Using A for loop(when the windowSize is changing) => algo2 Sliding Window
        for(int end = 0; end < N; end++){
            while(condition) => shrink the window until it meets condition
                start++; 
        }
    
    Different Pattern == two pointer (Grind > Sliding Window > 3)
    We have "left" and "right" 
    while(left < N && right < N)
    {
        if(something)
            right++; //enlarge window
        else
            left++; //shrink window
    }

    Just start from Exclusive! [L, R)
    L = 0, R = 0; cur = INITIAL VALUE
    While(L < SIZE && R < SIZE){
        if(something)
            cur += nums[R++];
        else
            cur -= nums[L++];
        ## Key point here is when R == nums.size()
        ## Is there a potential answer cases? (since exclusive!)
        Usual pattern is, for each 'R', count or loop every possible
        answer cases by shrinking window. Then, go to next step(R++, enlarge window).

        The distinction of each step is containing 'R' or not! => helpful when counting (no overocunt!)
        EX)713
        // Shrink Window
        while(condition) 
            cur -= nums[L++];

        //Update Answer 
    }

BackTracking
    https://leetcode.com/problems/combinations/discuss/844096/backtracking-cheatsheet-simple-solution

    BackTracking Pattern
    *********
    def backtrack(candidate):
        if find_solution(candidate):
            output(candidate)
            return
        
        # iterate all possible candidates.
        for next_candidate in list_of_candidates:
            if is_valid(next_candidate):
                # try this partial candidate solution
                place(next_candidate)
                # given the candidate, explore further.
                backtrack(next_candidate)
                # backtrack
                remove(next_candidate)
    *********

    Generate permutations and combinations(algo2)
    -> puts conditions 
    how to make a unique perms and combs?
    1. using a Map
    2. sort and skip the same value 

    Subset = getting combination for all k = 0 ~ n 
    Thus, if we remove "if cur.size() == k" from genComb,
    we can get subset of array!

WORTH NOTING
    http://codeforces.com/blog/entry/66660 
    string a; 
    a = a + "xy" O(N) vs a += "xy" O(1) vs a = move(a) + "xy" O(1)
    first one makes copy of "a", and then append

Cycle Detection (Grind > graph > course schedule)
    Undirected:
        DFS/BFS both possible, If we are visiting the node again
        but that node is not the parent, cycle!
        - in undirected graph, the graph has a cycle if it is not a MST!
        Union Find. -> cannot be used in directed graph!
        EX) 1 -> 2 -> 3, 1 -> 3 is not cyclic if it is directed. but cyclic if
        it is undirected
        If it is connected graph, #edge == #node -1: acyclic else, cyclic
    Directed:
        DFS: utilize the process of finding path. Visit Nodes in call stack
            means they are in the same path. 
            -> DFS is naturally topological sort
        BFS: utilize topological sort (If it has a cycle? cannot do Top Sort!)
            -> using a indegree. Put nodes with 0 indegree,
            pop and decrease the indegree of neighbors. 
            Repeat this process until queue is empty

        ## We can use Tarjan's Algorithm!!
    

Prim's, Kruskal's algo -> only for Undirected graph!

Dijkstra -> Both Undirected + Directd!

Prefix Tree(trie) - look grind > graph > prefixTree
    each node has children array with alphabets, and boolean value(isWord)

Compare Two String, especially comparing pattern or sequence,
    => using a 2D memo, DP
        ex) algo2 > DP > Longest Common subsequence, LongestPalindrome or DP > 44
    TIP) we use empty character at 0 index to use as a buffer.
        So, memo[0][0] = true, but else is false because letter != ' '
        (if some special letter is equal to ' ', then it could be true)


Binary Searching
    1) break condition, start > end
    2) how to divide the region? if not in A, it should be U - A 
    Key is finding sorted part. if some part is sorted,
    sorted[start] < sorted[end] we can know the key element is in that
    range just by compare the start and end of sorted part!

Max sum of subArray!
    Using a sliding window!

Knapsack 
    !!!Include VS not include!!! => think about Knapsack!
    ## if we are picking any elements, then should use DP.
    ## But, if we have to pick continuous elements(substring, subArray) => sliding window!
    0 / 1 problem 
    => set a 2D memo 
    each row : each item, (meaning we are using from 0 ~ to i_th element)
    each col : target amount or restriction.
    We are making this amount OR it should be restricted to this amount

Monotonic sequence EX) 239
    Feels like Semi-sorted list 
    When we don't need full sorted list, but we need to keep current Max
    or current Min, We can use Monotonic Sequence! 
    In this way, we can switch to next MAX or MIN when current MAX or MIN is 
    expired

Tree    
    Undirected Graph that "For all nodes in G,
    A -> B has !only! one path"
    Diameter == Longest Path

    How can I get a Maximum Path from A to B? -> O(N) possible
    ## start traverse from a random point. Find the farthest point X.
    ## start traverse from X and find the farthest point Y.
    ## shortest path is X->Y
    Since there is only one path from A -> B for all nodes in tree,
    If we pick a random point, then the farthest node should be one of the
    end of the longest path!
    EX) let's say 1 - 2 - 3- 4- 5 is the lognest path. And, 3 - 6 - 7.
    Even though we pick 6 or 7 which is the node not included in the longest path,
    It should go through one node in the longest path. Thus, it will reach the end of
    the longest path. We can prove this by contradiction(Suppose the Farthest point from X is
    not the end of the longest path).
    https://stackoverflow.com/questions/20010472/proof-of-correctness-algorithm-for-diameter-of-a-tree-in-graph-theory 
    => application of this concept - Minimum height tree In tree

    Due to this, # of Minimum height tree should be 1 or 2(mid point of the longest path)

    Every node other than mid point should have the length bigger than L/2
    (It goes through one of the node in the longest path and create the height > L/2)

*** Topological Sort of Tree
    traversing from leaf nodes and goes into center.
    We can find the root of Min Height Tree (grind > binTree > 310) at last.
    At the same time, we can get the length of diameter of tree!
    (because we are reducing from the outer nodes, and the diameter is decreased by 2)
    length of diameter = (total number of levels - 1) * 2 + 1 or 0, (if we are counting level from 1)

    Get Diameter == longest path 
    1) Do DFS/BFS twice. Pick random node, do DFS/BFS, find the farthest one(one end).
        Then do DFS/BFS from that node. The farthest node from this search is the other end of path
        => We can get exact path. (A->B-> ...)
    2) Getting a Length of Diameter
        A) Topological Sort 
        B) recursively calculating height and tracking the max per each node.



Graph 
    Undirected 
        Shortest : Dijkstra / Bellman Ford / Floyd Warshall
        + Acyclic = Tree 
            Shortest Path
                - We can use Topologival Sort! (from a node to other nodes)
                - simple shortest path 
                    we can do something simillar to what we did at calculating max diameter.
                    Use DFS, for each node, get min of children, Track 2 minimum children legnth..
                    https://stackoverflow.com/questions/28460252/find-minimum-weight-of-simple-path-in-tree?rq=1 
                    https://stackoverflow.com/questions/4977112/how-to-find-the-shortest-simple-path-in-a-tree-in-a-linear-time 
            Longest Path == Diameter 
                Run DFS/BFS twice 
                Topological Sort

    Directed
        Short : Dijkstra (non-negative weight) (src node to all other nodes) - O(V^2)
                Bellman Ford (negative, positive weight both works!) (src node to all other nodes) - O(VE)
                Floyd Warshall (get shortest path for all pairs) (positive or negative both works) - O(V^3)
        + Acyclic = DAG 
            Shortest Path
                - Topological Sort (from src node to other nodes)
            Longest Path
                - Topological Sort (negate weight and get shortest path) (from src node to other nodes)

    Make MST
        - Kruskal / Prim

    Network Flow

MONOTONIC SEQUENCE - grind > sliding window 239 and grind > stack > 84
 * How to keep the potential max elements?
 * What we need
 *  (1) Max elements in sliding window
 *  (2) Potential max elements which could be the max when current max is popped.
 * We do not need a sorted list. we only need the way to keep potential max.
 *  (A) We do not need previous elements smaller than current elements
 *  (B) if current element is smaller than previous one, it might be the potential max
 * ==> Monotonic Sequence


Dijkstra Sudo code (We do not need VISITED node.)
    while Q is not empty:               // The main loop
        u ← Q.extract_min()            // Remove and return best vertex
        for each neighbor v of u:
            alt = dist[u] + length(u, v) 
            if alt < dist[v]            // if v is visited, dist[v] <= alt, so it should be false
                dist[v] ← alt           // update distance here!
                prev[v] ← u
                Q.decrease_priority(v, alt) // we put the accumulated distance here!!!!
                                            // to pop the shortest distance FROM THE SRC first! 
                                            // if we put just the weight of the edge => Prim's algo

Dijkstra - greedy , Bellman Ford - Dynamic => thus dijkstra cannot handle negative weight
    Even though all edges have negative weight, Dijkstra fails because
    it greedly choose the shortest edge from current, but the negative weight can
    reduce this weight later => which makes greedy fail(substitute 5 to -1 and 2 to -2 from below)
Dijkstra from A will first develop C, and will later fail to find A->B->C
       A
      / \
     /   \
    /     \
   5       2
  /         \
  B--(-10)-->C

V={A,B,C} ; E = {(A,C,2), (A,B,5), (B,C,-10)}

Bellman Ford
https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/
https://leetcode.com/problems/cheapest-flights-within-k-stops/discuss/340911/Understanding-Bellman-Ford 

Shortest Path Faster Algorithm (Improvement of Bellman Ford)
https://leetcode.com/problems/network-delay-time/discuss/810907/spfa-algorithm 
    How? We use a BFS and update the distance
   
Bit Manipulation
XOR characteristic
    X ^ X = 0;
    0 ^ X = X; 
    A ^ B = B ^ A, commutative;
AND 
    X & 0 = 0;
    X & 1 = last bit of X;
Bit shift
    A >> 1, right shift by one (divde by 2^1)

Optimize Tips
    Counting Sort. O(NlogN) -> O(N)
    EX)letters, frequency

Linked list
    Usually think about "LENGTH" 
    Thinking in terms of Length will help a lot.
    Solve the problem in the case <where we already know the length>
    of each list!! 
    Get the solution, and just input the length to that solution.

Post, Pre order 
    If we include Null nodes, we can uniquely identify tree!
    with post and preorder

Find substring
    If the letter is not unique, two pointers does not work!
    EX) onionions & onions
    KMP algo 
    https://www.youtube.com/watch?v=4jY57Ehc14Y&ab_channel=LogicFirst 

Priority Queue + BFS 
    graph > 407, 778
    Using Priority Queue to get minimum location,
    and use BFS to how far we can go from that location.

Subset and genComb, skip redundant  
    just sort and skip the same elem!
    genPerm.. -> use Map!

Integer OutofBound without using long
    USE "STRING" !!

SubSequence with constraint... => KnapSack?!
    https://leetcode.com/discuss/interview-question/402487/Expedia-Coding-Test
    
Counting problems! 
    Utilize Hashmap! 
    Divisible? -> MOD! -> only need to think about numbers under MOD!