Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision 		Previous revision
algorithm_problems [2020/08/30 17:04]
paul [Wildcard Matching] 		algorithm_problems [2020/10/19 19:58] (current)
Line 8: Line 8:
 fucked. If you go too slow, you're fucked. So just go steady, watch the signs fucked. If you go too slow, you're fucked. So just go steady, watch the signs
 and down blow past them! and down blow past them!
 +
 +Rules:
 +  - Do not jump to quick solutions
 +  - Think about information that you have access to
 +  - Write psuedo code that works. If pseudo code doesn't work, code won't work
 +  - Think simple.
 +  - Validate psuedocode with a simple case
 +
 +===== Top K Frequent Words =====
 +[[https://leetcode.com/problems/top-k-frequent-words/|Leedcode 692]].
 +
 +**Given a non-empty list of words, return the k most frequent elements.
 +
 +Your answer should be sorted by frequency from highest to lowest. If two words
 +have the same frequency, then the word with the lower alphabetical order comes
 +first.**
 +
 +This problem is broken in two parts:
 +  - Track/store the words and their frequency
 +  - Order the words and their frequency 
 +
 +For storing the words and their frequency there are two ways to do it:
 +  - hashmap of string and int, increment count every time you see the int
 +  - Using a trie
 +
 +For ordering you can do the following:
 +  - Using an ordered set and return only the elements needed. 
 +    - This is bad because you are sorting all the words when you only need some of them.
 +  - Maintain a priority queue of all the words with a custom ordering and then pop off only the needed elements. 
 +    - This is not great because you are storing a priority queue with every possible word.
 +  - Build a MIN HEAP. 
 +    - If the min heap is bigger than the size we are looking for, when inserting an element check it against the current min. If it is bigger, insert it and pop off the min.
 +
 +Implementation of the logic is straight forward. The tricky part is setting the
 +custom ordereding in C++. Use the following for ordering a prioirty queue with
 +the frequency and then lexicographically as a fallback.
 +
 +<code cpp [enable_line_numbers="true"]>
 +typedef pair<string, int> p_d;
 +
 +class Compare{
 +public:
 +    bool operator() (const p_d& a, const p_d& b){
 +        if(a.second == b.second){
 +            return a.first > b.first;                
 +        }else {
 +            return a.second < b.second;
 +        }
 +    }
 +};
 +
 +priority_queue<p_d, vector<p_d>, Compare> heap;
 +</code>
 +
 +To create a custom compare ordered container and not fall into C++ errors,
 +creating a compare class works.
 +
 +===== Longest Increasing Path =====
 +
 +[[https://leetcode.com/problems/longest-increasing-path-in-a-matrix/|Leetcode 329]].
 +
 +**Given an integer matrix, find the length of the longest increasing path.**
 +
 +Solved this with a dfs approach. Spent a bit of time with seen, and didn't even
 +need it in the end! The numbers are increasing so you don't need to check for
 +that.
 +
 +<code pseudo [enable_line_numbers="true"]>
 +array of positions getNeighbors(pos, the matrix)
 +    return top if inbounds and bigger
 +    
 +int explore and return the longest path (Pos, seen set of positions)
 +    have we seen it?
 +        yes: return 0
 +    add this position to seen
 +    getNeighbors of this position (in bounds and increasing positions)
 +    
 +    int path = 0;
 +    iterate over neighbors
 +       path = max(1 + explore(neighbor), path)
 +      
 +    remove this pos from seen
 +    return path
 +
 +keep running max
 +start from every element in the array
 +explore it, get longest path, compare to runnign max
 +return the max
 +</code>
 +
 +<code cpp [enable_line_numbers="true"]>
 +class Solution {
 +public:
 +
 +    vector<vector<int>> memo;
 +    int rows;
 +    int cols;
 +    
 +    bool inBounds(vector<int> &p){
 +        if(p[0] < 0 || p[0] >= rows || p[1] < 0 || p[1] >= cols){
 +            return false;
 +        }
 +        return true;
 +    }
 +    
 +    vector<vector<int>> getNeighbors(vector<vector<int>>& matrix, vector<int> &p){
 +        int val = matrix[p[0]][p[1]];
 +        vector<int> l = p, r = p, t = p, b = p;
 +        
 +        l[1]--; 
 +        r[1]++; 
 +        t[0]--; 
 +        b[0]++;
 +        
 +        vector<vector<int>> out;
 +        if(inBounds(l) && matrix[l[0]][l[1]] > val)      { out.push_back(l); }
 +        if(inBounds(r) && matrix[r[0]][r[1]] > val)      { out.push_back(r); }
 +        if(inBounds(t) && matrix[t[0]][t[1]] > val)      { out.push_back(t); }
 +        if(inBounds(b) && matrix[b[0]][b[1]] > val)      { out.push_back(b); }
 +
 +        return out;        
 +    }
 +    
 +    int explore(vector<vector<int>>& matrix, vector<int> &p){
 +
 +        if(memo[p[0]][p[1]] > 0){ return memo[p[0]][p[1]]; }
 +        int path = 1;
 +        vector<vector<int>> nays = getNeighbors(matrix, p);
 +        for(auto& n : nays){
 +            path = max(path, 1 + explore(matrix,n));
 +        }
 +        memo[p[0]][p[1]] = path;
 +        return path;
 +    }
 +    
 +    int longestIncreasingPath(vector<vector<int>>& matrix) {
 +        if(matrix.size() == 0){ 
 +            return 0; 
 +        }
 +        
 +        rows = matrix.size();
 +        cols = matrix[0].size();
 +                
 +        memo = vector<vector<int>>(rows, vector<int>(cols, 0));
 +        
 +        int pathMax = 0;
 +        for(int r = 0; r < rows; r++){
 +            for(int c = 0; c < cols; c++){
 +                vector<int> p = {r,c};
 +                pathMax = max(pathMax, explore(matrix, p ) );
 +            }
 +        }
 +        return pathMax;
 +    }
 +};
 +</code>
  
 ===== Binary Search ===== ===== Binary Search =====
Line 20: Line 176:
 is what gets you ''O( Log N )'' search of data. is what gets you ''O( Log N )'' search of data.
  
-<code> +Algorithm: 
-1. Left pointer = 0 and right pointer = to last element + 
-2. While left is less then or equal to right +<code pseudo [enable_line_numbers="true"]> 
-3.     Find middle +Left pointer = 0 and right pointer = to last element 
-4.     Check if our target is in the middle, return it if we found it +While left is less then or equal to right 
-5.     If our target is less than the middle element +    Find middle 
-6.       explore left, mid; +    Check if our target is in the middle, return it if we found it 
-7.     If our target is greater than the middle +    If our target is less than the middle element 
-8.       explore mid+1 and right; +      explore left, mid; 
-9. return -1 if not found.+    If our target is greater than the middle 
 +      explore mid+1 and right; 
 +return -1 if not found.
 </code> </code>
  
-<code>+Code: 
 + 
 +<code cpp [enable_line_numbers="true"]>
 int search(vector<int>& nums, int target) { int search(vector<int>& nums, int target) {
   int left = 0;   int left = 0;
Line 61: Line 221:
  
 Algorithm: Algorithm:
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1. Create a pointer called last_good that starts at zero +Create a pointer called last_good that starts at zero 
-2. Iterate i from 0 to end +Iterate i from 0 to end 
-3.   if Nums[i] is not 0 +  if Nums[i] is not 0 
-4.     swap it with last good, and increment last good+    swap it with last good, and increment last good
 </code> </code>
  
Line 88: Line 248:
 Algorithm: Algorithm:
  
-{{:pasted:20200827-002710.png?600}}+{{:pasted:20200901-000003.png?600}}
  
 Code: Code:
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 bool isMatch(string s, string p) { bool isMatch(string s, string p) {
   int p_len = p.length(), s_len = s.length();   int p_len = p.length(), s_len = s.length();
Line 143: Line 303:
 **Given an input string (s) and a pattern (p), implement wildcard pattern matching **Given an input string (s) and a pattern (p), implement wildcard pattern matching
 with support for '?' and '*'.** with support for '?' and '*'.**
-<code>+<code pseudo [enable_line_numbers="true"]>
 '?' Matches any single character. '?' Matches any single character.
 '*' Matches any sequence of characters (including the empty sequence). '*' Matches any sequence of characters (including the empty sequence).
Line 156: Line 316:
 {{:pasted:20200830-170359.png?500}} {{:pasted:20200830-170359.png?500}}
  
-<code cpp>+Code: 
 + 
 +<code cpp [enable_line_numbers="true"]>
 bool helperMatch(string &s, int p_s, string &p, int p_p) { bool helperMatch(string &s, int p_s, string &p, int p_p) {
  
Line 230: Line 392:
 Algorithm: Algorithm:
  
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1.  Create res, and max_h, set to 0 +Create res, and max_h, set to 0 
-2.  Create a vector of left max heights +Create a vector of left max heights 
-3.  Iterate h over heights from 0 to end +Iterate h over heights from 0 to end 
-4.    max_h = max of h and max_h +  max_h = max of h and max_h 
-5.    left max push in max_h - h, this is the max this height can support +  left max push in max_h - h, this is the max this height can support 
-6.  Reset max_h to 0 +Reset max_h to 0 
-7.  Iterate h over heights from end to 0 +Iterate h over heights from end to 0 
-8.    max_h = max of h and max_h +  max_h = max of h and max_h 
-9.    res += min(left max at i, max_h - h) +  res += min(left max at i, max_h - h) 
-10. return res+return res
 </code> </code>
  
 Code: Code:
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 int trap(vector<int>& height) { int trap(vector<int>& height) {
     int res = 0, max_h = 0;     int res = 0, max_h = 0;
Line 276: Line 438:
 Algorithm: Algorithm:
  
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1.  Create a left pointer L = 0, right pointer R to size - 1 +Create a left pointer L = 0, right pointer R to size - 1 
-2.  Create left max LM and right max LM and a res of 0 +Create left max LM and right max LM and a res of 0 
-3.  While L < R +While L < R 
-4.    IF H[L] is smaller than H[R] +  IF H[L] is smaller than H[R] 
-5.        Set LM to MAX(LM, H[L]) +      Set LM to MAX(LM, H[L]) 
-6.        RES += LM - H[L] +      RES += LM - H[L] 
-7.        Increment L +      Increment L 
-8.    Else +  Else 
-9.        Set RM to MAX(RM, H[R]) +      Set RM to MAX(RM, H[R]) 
-10.       RES += RM - H[R] +      RES += RM - H[R] 
-11.       Decrement R +      Decrement R 
-12. Return Res+Return Res
 </code> </code>
  
 Code: Code:
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 int trap(vector<int>& h) { int trap(vector<int>& h) {
     // left pointer, right pointer, left max, right max, result     // left pointer, right pointer, left max, right max, result
Line 317: Line 479:
 ===== Edit Distance (DP) ===== ===== Edit Distance (DP) =====
  
-[[https://leetcode.com/problems/edit-distance/submissions/|Leetcode 72 (Hard)]].+[[https://leetcode.com/problems/edit-distance/|Leetcode 72 (Hard)]].
  
 **Given two words ''word1'' and ''word2'', find the minimum number of operations **Given two words ''word1'' and ''word2'', find the minimum number of operations
Line 340: Line 502:
 Code: Code:
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 int minDistance(string word1, string word2) { int minDistance(string word1, string word2) {
  
Line 395: Line 557:
 Algorithm: Algorithm:
  
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1.  Set bigger equal to string 1 length, and smaller equal to string 2 length +Set bigger equal to string 1 length, and smaller equal to string 2 length 
-2.  If bigger < smaller +If bigger < smaller 
-3.    return call functions with flipped strings +  return call functions with flipped strings 
-4.   + 
-5.  if bigger == smaller we need to do a replace +if bigger == smaller we need to do a replace 
-6.    iterate i over bigger +  iterate i over bigger 
-7.      if s1[i] != s2[i] +    if s1[i] != s2[i] 
-8.        return s1.substring(i+1) == s2.substring(i+1) +      return s1.substring(i+1) == s2.substring(i+1) 
-9.    if we get here that means strings were equal to return false +  if we get here that means strings were equal to return false 
-10. if bigger - smaller = 1 +if bigger - smaller = 1 
-11.   iterate i over smaller +  iterate i over smaller 
-12.     if s1[i] != s2[i] +    if s1[i] != s2[i] 
-13.       return s1.substring(i+1) == s2.substring(i) +      return s1.substring(i+1) == s2.substring(i) 
-14.   return true if we get here +  return true if we get here 
-15. return false if we get here, because it means strings are more than 1 away from each other+return false if we get here, because it means strings are more than 1 away from each other
 </code> </code>
  
 Code: Code:
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 bool isOneEditDistance(string s, string t) { bool isOneEditDistance(string s, string t) {
  
Line 484: Line 646:
 Here is the algorithm: Here is the algorithm:
  
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1.  FUNCTION: maxSub(string S1 and S2, pointers M and N, memo matrix) +FUNCTION: maxSub(string S1 and S2, pointers M and N, memo matrix) 
-2.    if M or N are 0, return 0 +  if M or N are 0, return 0 
-3.    if memo[M][N] is valid, return it +  if memo[M][N] is valid, return it 
-4.     +   
-5.    int x = 1 if S1[M-1] is equal to S2[N-1] +  int x = 1 if S1[M-1] is equal to S2[N-1] 
-6.    int SAME = maxSub(S1, S2, M-1, N-1, memo) + x +  int SAME = maxSub(S1, S2, M-1, N-1, memo) + x 
-7.    int DEL_S1 = maxSub(S1, S2, M-1, N, memo) +  int DEL_S1 = maxSub(S1, S2, M-1, N, memo) 
-8.    int DEL_S2 = maxSub(S1, S2, M, N-1, memo) +  int DEL_S2 = maxSub(S1, S2, M, N-1, memo) 
-9.   + 
-10.   return the max of the 3 +  return the max of the 3 
-11.  + 
-12. FUNCTION isValid(S1, S2) +FUNCTION isValid(S1, S2) 
-13.   M = S1 length, N = S2 length +  M = S1 length, N = S2 length 
-14.   Make a memo vector that is M+1 and N+1, init all to -1 +  Make a memo vector that is M+1 and N+1, init all to -1 
-15.   return ( M + N - 2* maxSub(S1, S2, M, N, memo)+  return ( M + N - 2* maxSub(S1, S2, M, N, memo)
 </code> </code>
  
 Code: Code:
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 // make our own fancy 3 way max function // make our own fancy 3 way max function
 int max(int x, int y , int z) int max(int x, int y , int z)
Line 562: Line 724:
 Code: Code:
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 int findLength(vector<int>& A, vector<int>& B) { int findLength(vector<int>& A, vector<int>& B) {
   int m = A.size(), n = B.size();   int m = A.size(), n = B.size();
Line 599: Line 761:
 Algorithm ''O(N log n)'': Algorithm ''O(N log n)'':
  
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1. Sort input array +Sort input array 
-2. Iterate i start at index 1 over array +Iterate i start at index 1 over array 
-3.     if(num[i] == num[i - 1] then it is a duplicate +    if(num[i] == num[i - 1] then it is a duplicate 
-4.     else if(num[i] == num[i]-2 it is a missing element +    else if(num[i] == num[i]-2 it is a missing element 
-5.  + 
-6. return duplicate and missing+return duplicate and missing
 </code> </code>
  
 Algorithm ''O(N)'': Algorithm ''O(N)'':
  
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1.  create min set to INT_MAX and max set to INT_MIN +create min set to INT_MAX and max set to INT_MIN 
-2.  create unordered set +create unordered set 
-3.  iterate n over input +iterate n over input 
-4.      if n in set +    if n in set 
-5.          dupe = n +        dupe = n 
-6.      insert n in set +    insert n in set 
-7.      min = min ( min and n) +    min = min ( min and n) 
-8.      max = max ( max and n) +    max = max ( max and n)
-9.   +
-10. iterate i from min to max +
-11.    if i is not found in our set, we have our missing! +
-</code>+
  
-===== Linked List Cycle II ===== +iterate i from min to max 
- +   if i is not found in our set, we have our missing!
-[[https://leetcode.com/problems/linked-list-cycle-ii/|Leetcode 142]]. +
- +
-**Given a linked list, return the node where the cycle begins. If there is no +
-cycle, return ''null''. +
- +
-To represent a cycle in the given linked list, we use an integer pos which +
-represents the position (0-indexed) in the linked list where tail connects to. +
-If pos is -1, then there is no cycle in the linked list.** +
- +
-Super super cool Floyd's algorithm for loop detection. The following algorithm +
-does all the proper checks in case of null lists and also lists that are not +
-cycles. +
- +
-Algorithm: +
- +
-<code> +
-1.  Make pointer q and q both equal to head +
-2.   +
-3.  while q and p, and p->next +
-4.    p advance twice +
-5.    q advance once +
-6.    if p == q, break +
-7.   +
-8.  When we get here we either have a loop or an NULL end. +
-9.  if( !p OR !p->next) // the OR order is important, so we don't have runtime errors  +
-10.   We have the end, so no loop! return NULL +
-11.  +
-12. We have loop, so we have to find where it starts +
-13. q = head +
-14. while p != q +
-15.   p advance once +
-16.   q advance once +
-17.  +
-18. return q // or q, it doesn't matter :) +
-</code> +
- +
-Code: +
- +
-<code cpp> +
-ListNode *detectCycle(ListNode *head) { +
- +
-  ListNode *q = head, *p = head; +
- +
-  while(q && p && p->next != NULL) +
-  { +
-    p = p->next; p = p->next; +
-    q = q->next; +
-    if(q == p) +
-      break; +
-  } +
- +
-  if(!p || p->next == NULL) +
-    return NULL; +
- +
-  q = head; +
-  while(p != q) +
-  { +
-    p = p->next; +
-    q = q->next; +
-  } +
-  return q;    +
-}+
 </code> </code>
  
Line 707: Line 803:
 we detect where the cycle started which is the duplicate. we detect where the cycle started which is the duplicate.
  
-<code> +Algorithm: 
-1.  p = nums[0] and q = to num [0] + 
-2.  DETECT CYCLE +<code pseudo [enable_line_numbers="true"]> 
-3.  while true +p = nums[0] and q = to num [0] 
-4.      move p twice +DETECT CYCLE 
-5.      move q once +while true 
-6.      if p == q, break ( we have a cycle ) +    move p twice 
-7.   +    move q once 
-8.  FIGURE OUT WHERE CYCLE IS BASED ON FLOYD'S ALGO +    if p == q, break ( we have a cycle ) 
-9.  q = nums[0] + 
-10. while(p != q) +FIGURE OUT WHERE CYCLE IS BASED ON FLOYD'S ALGO 
-11.   move p once +q = nums[0] 
-12.   move q once +while(p != q) 
-13.  +  move p once 
-14. return q :)+  move q once 
 + 
 +return q :)
 </code> </code>
  
-<code cpp>+Code: 
 + 
 +<code cpp [enable_line_numbers="true"]>
 int findDuplicate(vector<int>& nums) { int findDuplicate(vector<int>& nums) {
  
Line 746: Line 846:
   return p;   return p;
 } }
 +</code>
 +
 +===== Median Stream =====
 +
 +[[https://www.hackerrank.com/challenges/find-the-running-median/problem|Hackerrank]].
 +
 +**You're given a list of n integers ''arr[0..(n-1)]''. You must compute a list
 +''output[0..(n-1)]'' such that, for each index ''i'' (between 0 and ''n-1'',
 +inclusive), ''output[i]'' is equal to the median of the elements ''arr[0..i]''
 +(rounded down to the nearest integer).**
 +
 +I first solved this with a set, but this took ''n/2'' time to find the middle elements. I then solved it with two heaps with.
 +
 +{{:pasted:20200831-204419.png?500}}
 +
 +Code:
 +
 +<code cpp [enable_line_numbers="true"]>
 +vector <int> findMedian(vector <int> arr) {
 +  vector<int> out;
 +  priority_queue<int> max_heap;
 +  // just have to remember a default priority_queue in c++ is a max_heap
 +  priority_queue<int, vector<int>, greater<int>> min_heap;
 +
 +  for(auto& num : arr){
 +    // If both heaps empty
 +    if(max_heap.size() == 0 && min_heap.size() == 0){
 +      max_heap.push(num);
 +    }
 +    // we assume that max heap will not be empty
 +    else{
 +      if(num > max_heap.top()){
 +        min_heap.push(num);
 +      }else{
 +        max_heap.push(num);
 +      }
 +    }
 +
 +    // Balance the heaps CAREFUL WITH SIZE TYPES
 +    if((int)max_heap.size() - (int)min_heap.size() > 1){
 +      min_heap.push(max_heap.top());
 +      max_heap.pop();
 +    }
 +    else if((int)min_heap.size() - (int)max_heap.size()  > 1){
 +      max_heap.push(min_heap.top());
 +      min_heap.pop();
 +    }
 +
 +    // Calculate median
 +    if(max_heap.size() == min_heap.size()){
 +      out.push_back( (max_heap.top() + min_heap.top() ) / 2 );
 +    }else if(max_heap.size() > min_heap.size()){
 +      out.push_back(max_heap.top());
 +    }else{
 +      out.push_back(min_heap.top());
 +    }
 +  }
 +  return out;
 +}
 +</code>
 +
 +===== Iterator for List of Sorted Lists =====
 +Interview problem.
 +
 +**Create an iterator for a list of sorted lists that implements a constructor
 +''SortedIterator()'', ''next()'', and ''hasNext()'' functions.**
 +
 +Great problem. I first dove into this problem by suggesting sorting out input
 +lists. This would not work on large sets. Do not liberally try sorting data
 +first. Explore the problem and see what can be done. In the end this problem can
 +be solved with a min heap, by keeping track of the smallest leading element of
 +the array, along with its indices. 
 +
 +I initially solved this problem with a multimap to take care of the i, j
 +indices. A multimap has worse time complexity than a heap becasue it has
 +''O(log(n))'' insertion times, and you need to do an insertion with every
 +''next()'' operation.
 +
 +Algorithm:
 +
 +<code pseudo [enable_line_numbers="true"]>
 +class HeapElement
 +HeapElemetn constructor
 +value
 +  i, j
 +// convert to min heap
 +overload the < operator
 +  a.i > b.i
 +
 +priority_queue<HeapElement> minHeap
 +   
 +FUNC constructure( lists )
 +  for i to lists size
 +  if list[i] not empty
 +    insert HeapElement(list[i][0], i, 0) into min heap
 +
 +FUNC next()
 +  if hasNext() is false
 +     return -1
 +     
 +   get a copy of top element of heap, call it prevTop
 +   pop off the top element
 +   int out = prevTop.val
 +   prevTop.j++ 
 +   if prevTop.j is bounds of its list
 +     set prevTop.val to value at prevTop i j
 +     insert heapElement into min_heap;
 +   return out;
 + 
 +FUNC hasNext()
 +   return size of heap > 0
 +</code>
 +
 +Code:
 +
 +<code cpp [enable_line_numbers="true"]>
 +// this will contain the data in our heap
 +class HeapElement {
 +  public:
 +    int val, i, j;
 +    HeapElement(int _val, int _i, int _j) : val(_val), i(_i), j(_j){}
 +};
 +
 +// Overload the less than operator
 +bool operator<(const HeapElement &a, const HeapElement &b){
 +  return a.val > b.val;
 +}
 +
 +class SortedIterator {
 +private:
 +  // we need a reference to our input list
 +  const vector<vector<int>> &lists;
 +  priority_queue<HeapElement> minHeap;
 +public:
 +  // Constructor
 +  SortedIterator(const vector<vector<int>> &_lists) : lists(_lists){
 +    for(int i = 0; i < (int)lists.size(); i++){
 +      if(lists[i].size() > 0){
 +        minHeap.push(HeapElement(lists[i][0], i, 0));
 +      }
 +    }
 +  }
 +
 +  // our iterator next function
 +  int next(){
 +    if(hasNext() == false){
 +      return -1;
 +    }
 +    HeapElement prevTop = minHeap.top(); 
 +    minHeap.pop();
 +    int out = prevTop.val;
 +
 +    if(++prevTop.j < (int)lists[prevTop.i].size()){
 +      prevTop.val = lists[prevTop.i][prevTop.j];
 +      minHeap.push(prevTop);
 +    }
 +    return out;
 +  } 
 +
 +  // check if we have a next value 
 +  bool hasNext(){
 +    return minHeap.size() > 0;
 +  }
 +};
 </code> </code>
  
Line 764: Line 1028:
 Algorithm: Algorithm:
  
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1. create memo array +create memo array 
-2. set memo[0][:] to 1 +set memo[0][:] to 1 
-3. set memo[:][0] to 1 +set memo[:][0] to 1 
-4.  + 
-5. for i 1 to m +for i 1 to m 
-6.     for j 1 to m +    for j 1 to m 
-7.         memo[i][j] = memo[i-1][j] + memo[i][j-1] +        memo[i][j] = memo[i-1][j] + memo[i][j-1] 
-8.  + 
-9. return memo[size - 1][memo[0]size-1]+return memo[size - 1][memo[0]size-1]
 </code> </code>
  
 Code: Code:
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 int uniquePaths(int m, int n) { int uniquePaths(int m, int n) {
     // vector of all 1's     // vector of all 1's
Line 880: Line 1144:
 Here is a much more concise solution I found online: Here is a much more concise solution I found online:
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 int calculate(string s) { int calculate(string s) {
   stack<int> myStack;   stack<int> myStack;
Line 911: Line 1175:
   }   }
   return res;   return res;
 +}
 +</code>
 +
 +===== Reverse Linked List II =====
 +
 +[[https://leetcode.com/problems/reverse-linked-list-ii/|Leetcode 92]].
 +
 +**Reverse a linked list from position m to n. Do it in one-pass.**
 +
 +I struggled to get the cases down with this one. You have to think simply! You
 +maintain 3 pointers, prev and cur, and next, which you get from cur. With this
 +amazingly simple algorithim you don't even need a temp object. 
 +
 +What you do is move prev and cur till cur is on the first node ''m'' to be
 +reversed.
 +
 +{{:pasted:20200831-040408.png?500}}
 +
 +<code cpp [enable_line_numbers="true"]>
 +ListNode* reverseBetween(ListNode* head, int m, int n) {
 +  ListNode dh;
 +  dh.next = head;
 +  ListNode *pre = &dh, *cur = head;
 +
 +  n = n - m;
 +
 +  // move pre and cur down till we hit m
 +  while(m > 1){
 +    pre = pre->next;
 +    cur = cur->next;
 +    m--;
 +  }
 +
 +  // handle our swaps
 +  while(n > 0){
 +    ListNode* next = cur->next;
 +    cur->next = next->next;
 +    next->next = pre->next;
 +    pre->next = next;
 +    n--;
 +  }
 +  return dh.next;
 +}
 +</code>
 +
 +===== Linked List Cycle II =====
 +
 +[[https://leetcode.com/problems/linked-list-cycle-ii/|Leetcode 142]].
 +
 +**Given a linked list, return the node where the cycle begins. If there is no
 +cycle, return ''null''.
 +
 +To represent a cycle in the given linked list, we use an integer pos which
 +represents the position (0-indexed) in the linked list where tail connects to.
 +If pos is -1, then there is no cycle in the linked list.**
 +
 +Super super cool Floyd's algorithm for loop detection. The following algorithm
 +does all the proper checks in case of null lists and also lists that are not
 +cycles.
 +
 +Algorithm:
 +
 +<code pseudo [enable_line_numbers="true"]>
 +Make pointer q and q both equal to head
 +
 +while q and p, and p->next
 +  p advance twice
 +  q advance once
 +  if p == q, break
 +
 +When we get here we either have a loop or an NULL end.
 +if( !p OR !p->next) // the OR order is important, so we don't have runtime errors 
 +  We have the end, so no loop! return NULL
 +
 +We have loop, so we have to find where it starts
 +q = head
 +while p != q
 +  p advance once
 +  q advance once
 +
 +return q // or q, it doesn't matter :)
 +</code>
 +
 +Code:
 +
 +<code cpp [enable_line_numbers="true"]>
 +ListNode *detectCycle(ListNode *head) {
 +
 +  ListNode *q = head, *p = head;
 +
 +  while(q && p && p->next != NULL)
 +  {
 +    p = p->next; p = p->next;
 +    q = q->next;
 +    if(q == p)
 +      break;
 +  }
 +
 +  if(!p || p->next == NULL)
 +    return NULL;
 +
 +  q = head;
 +  while(p != q)
 +  {
 +    p = p->next;
 +    q = q->next;
 +  }
 +  return q;   
 +}
 +</code>
 +
 +===== Insert In a Sorted Circular Linked List ======
 +
 +[[https://leetcode.com/problems/insert-into-a-sorted-circular-linked-list/|Leetcode 708]]
 +
 +**Given a node from a Circular Linked List which is sorted in ascending order,
 +write a function to insert a value insertVal into the list such that it remains
 +a sorted circular list.**
 +
 +This problem becomes hard because of the cases you have to check for, for
 +proper insertion of the value.
 +
 +You have to check these cases:
 +
 +  - **case 1**: Simple, value fits between a ''prev'' and ''curr'' pointer.
 +  - **case 2**: We have a pivot, ''prev'' > ''curr''. That means we fit if we are greater than ''prev'', OR we are less than ''curr''.
 +  - **case 3**: We reach back to the start of the list. Just pop us in man.
 +
 +Took me a while to nail down these cases. It is VERY easy to get lost in nested
 +if statements.
 +
 +<code cpp [enable_line_numbers="true"]>
 +class Solution {
 +  public:
 +
 +    void insertAfter(Node* node, int i)
 +    {
 +      Node* temp = new Node(i);
 +      temp->next = node->next;
 +      node->next = temp;
 +    }
 +
 +    Node* insert(Node* head, int insert_val) {
 +
 +      // Lets take care of the NULL case
 +      if(head == NULL)
 +      {
 +        Node* temp = new Node(insert_val);
 +        temp->next = temp;
 +        return temp;
 +      }
 +
 +      // two pointers
 +      Node *p = head, *n = head->next;
 +
 +      while(n != head)
 +      {
 +        if(p->val <= insert_val && insert_val <= n->val)
 +        {
 +          insertAfter(p, insert_val);
 +          return head;
 +        }
 +        else if(p->val > n->val)
 +        {
 +          if(p->val <= insert_val || insert_val <= n->val)
 +          {
 +            insertAfter(p, insert_val);
 +            return head;
 +          }
 +        }
 +        p = n;
 +        n = n->next;
 +      }
 +
 +      insertAfter(p, insert_val);
 +
 +      return head;
 +    }
 +};
 +</code>
 +
 +===== Print Binary Tree =====
 +
 +[[https://leetcode.com/problems/print-binary-tree/|Leetcode 655]].
 +
 +**Print out a binary tree in the form of a 2d string array with spacing between
 +each element.**
 +
 +The devil of this problem is to have the proper spacing between elements as you
 +can down the levels. This problem requires the following information:
 +
 +  - Get the heigh of the tree.
 +  - Figure out the width of the output based on the height
 +  - Do a DFS exploration of the tree and find correct indices for elements
 +
 +I had to peek at the answer for this one, but practiced how to BFS iteratively
 +with a queue and a nested while loop.
 +
 +The algorithm for putting values in the correct places is also very smart, with
 +a left and right pointer and then just placing items in the middle of them.
 +
 +===== Convert Sorted List to Binary Search Tree ====
 +
 +[[https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/|Leetcode 109]].
 +
 +**Given the ''head'' of a singly linked list where elements are sorted in ascending
 +order, convert it to a height balanced BST.**
 +
 +The first step to realize is that you need to find the middle. Then you must
 +realize that the middle is going to be a root node. Then you must realize that
 +you need to split list in a left half and a right half. The left half of the
 +list can be used to rescurse into, the head of which will be the left child, and
 +same with the right list. You can do it!
 +
 +{{:pasted:20200831-165853.png?500}}
 +
 +Algorithm:
 +
 +<code pseudo [enable_line_numbers="true"]>
 +FUNCTION split(head)
 +   if head is null return head
 +   slow pointer and faster pointer equal to head
 +   prev pointer
 +   while fast and fast next is not null 
 +       prev = slow
 +       fast = fast next
 +       slow = slow next
 +    prev next = null
 +    return slow
 +    
 +FUNCTION treenode sortedListToBST(head)
 +    if head is null return NULL
 +    listnode mid = split(head)
 +    TreeNode root = new treenode mid val
 +    if mid != head
 +        left = sortedListToBST(head);
 +    right = sortedList(mid->next)
 +    return root 
 +</code>
 +
 +<code cpp [enable_line_numbers="true"]>
 +ListNode* split(ListNode *head){
 +  if(head == NULL){
 +    return NULL;
 +  }
 +  ListNode *slow = head, *fast = head, *prev = head;
 +  while(fast != NULL && fast->next != NULL){
 +    prev = slow;
 +    slow = slow->next;
 +    fast = fast->next->next;
 +  }
 +  
 +  prev->next = NULL;
 +  
 +  return slow;
 +}
 +
 +TreeNode* sortedListToBST(ListNode* head) {
 +  if(head == NULL){
 +    return NULL;
 +  }
 +  ListNode *mid = split(head);
 +  TreeNode *root = new TreeNode(mid->val);
 +
 +  // left list is going to be started with head
 +  // right list is started with mid->next
 +
 +  // if we have a real left list
 +  if(mid != head){
 +    root->left = sortedListToBST(head);
 +  }
 +  root->right = sortedListToBST(mid->next);
 +
 +  return root;
 +}
 +</code>
 +
 +===== Binary Tree Zigzag Level Order Traversal ====
 +
 +[[https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/|Leetcode 103]]
 +
 +**Given a binary tree, return the zigzag level order traversal of its nodes'
 +values. (ie, from left to right, then right to left for the next level and
 +alternate between).**
 +
 +Just have to realize to do a BFS with a queue and output the data reversed every
 +other level. When doing BFS with a stack, you have to deliniate the current
 +level and the next level. Doing it with a null node is a nice way.
 +
 +Algorithm:
 +<code pseudo [enable_line_numbers="true"]>
 +init a queue of nodes
 +put in the root in the queue
 +put in null node
 +
 +output array (2d)
 +
 +empty level array 
 +
 +while queue inst' empty
 +    set cur to queue front
 +    pop it off
 +    if(cur is not null)
 +        put in our level array
 +        if children aren't null, push into queue
 +    else we reached the end of the level
 +        if rev is true
 +            reverse level array
 +        push in our level array
 +        clear the level array
 +        toggle rev
 +        if q isn't empty
 +            push in a null
 +</code>
 +
 +===== Binary Tree Maximum Path Sum ===== 
 +
 +[[https://leetcode.com/problems/binary-tree-maximum-path-sum/|Leetcode 124]].
 +
 +**Given a non-empty binary tree, find the maximum path sum. There can be negative
 +numbers.**
 +
 +I was asked this in an interview. The core concept is that at every node, the
 +maximum will either be the following:
 +
 +  * left path plus node 
 +  * right path plus node 
 +  * both paths rooted through the node.
 +
 +This problem can be simplified really well into short code by making use of
 +''max()'' calls on return data. Also we need to keep track of a global max, and
 +also return the max path, either left or right.
 +
 +<code pseudo [enable_line_numbers="true"]>
 +explore function (node, global max) -> max path from this node
 +  if this node is null, return 0
 +
 +  left max  = max(recursive call on left child, 0)
 +  right max = max(recursive call on right child, 0)
 +
 +  max both  = node val + max (left, right max)
 +
 +  global max = max(global max, both)
 +
 +  return node val + max(left, right)
 +</code>
 +
 +<code cpp [enable_line_numbers="true"]>
 +int explore(TreeNode* node, int& max_sum)
 +{
 +  if(node == NULL){
 +    return 0;
 +  }
 +
 +  int max_left = max(explore(node->left, max_sum), 0);
 +  int max_right = max(explore(node->right, max_sum), 0);
 +
 +  int max_both = node->val + max_left + max_right;
 +
 +  max_sum = max(max_both, max_sum);
 +
 +  return node->val + max(max_left, max_right);
 +}
 +
 +int maxPathSum(TreeNode* root) {
 +  int max = INT_MIN;
 +  explore(root, max);
 +  return max;
 } }
 </code> </code>
Line 939: Line 1571:
  
 Algorithm: Algorithm:
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1.   FUNCTION: CALC DISTANCE BETWEEN CHARACTER A AND CHARACTER B -> return a char +FUNCTION: CALC DISTANCE BETWEEN CHARACTER A AND CHARACTER B -> return a char 
-2.     Int d = A - B +  Int d = A - B 
-3.     if D is negative, then D += 'z' - 'a' + 1 +  if D is negative, then D += 'z' - 'a' + 1 
-4.     Reutrn D :) +  Reutrn D :) 
-5.   FUNCTION GROUP SHIFTED -> RETURN vector of vector of strings +FUNCTION GROUP SHIFTED -> RETURN vector of vector of strings 
-6.     create an OUTPUT vector of vector of strings +  create an OUTPUT vector of vector of strings 
-7.     Create a map of string, int : key is the "relationship between letters" and +  Create a map of string, int : key is the "relationship between letters" and 
-8.     value is the OUTPUT index for this group of strings that has the same key +  value is the OUTPUT index for this group of strings that has the same key 
-9.     Iterate s over input strings +  Iterate s over input strings 
-10.      Create a temp key (string) +    Create a temp key (string) 
-11.      Iterate i over s, starting at position 1. +    Iterate i over s, starting at position 1. 
-12.        temp key += DISTANCE(s[i-1], s[i]) +      temp key += DISTANCE(s[i-1], s[i]) 
-13.      IF key is found in map: +    IF key is found in map: 
-14.        add s to the right spot in OUTPUT +      add s to the right spot in OUTPUT 
-15.      else +    else 
-16.        add s to a NEW spot in output and add this index to the MAP +      add s to a NEW spot in output and add this index to the MAP 
-17.    RETURN OUTPUT+  RETURN OUTPUT
 </code> </code>
  
 Code: Code:
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 // how much we have to add to a to get to b // how much we have to add to a to get to b
 char dist(char a, char b) char dist(char a, char b)
Line 998: Line 1630:
 </code> </code>
  
 +===== Best Meeting Point =====
 +[[https://leetcode.com/problems/best-meeting-point/|Leetcode 296]].
 +
 +TODO
 +
 +<code cpp [enable_line_numbers="true"]>
 +    int minTotalDistance(vector<vector<int>>& grid) {
 +        if(grid.size() == 0){
 +            return 0;
 +        }
 +        
 +        // find all peeps
 +        vector<Point> peeps;
 +        for(int i = 0; i < grid.size(); i++){
 +            for(int j = 0; j < grid[0].size(); j++){
 +                if(grid[i][j] == 1){
 +                    peeps.push_back(Point(i,j));
 +                }
 +            }
 +        }
 +        
 +        int minDist = INT_MAX;
 +        for(int i = 0; i < grid.size(); i++){
 +            for(int j = 0; j < grid[0].size(); j++){
 +                // iterate through all our peeps
 +                int totalDist = 0;
 +                for(auto& peep : peeps){
 +                    totalDist += Point::dist(peep, Point(i,j));
 +                }
 +                minDist = min(totalDist, minDist);
 +            }
 +        }
 +        return minDist;
 +    }
 +    </code>
 ===== Passing Yearbooks ===== ===== Passing Yearbooks =====
 +
 +[[https://leetcode.com/discuss/interview-question/614096/facebook-interview-preparation-question-passing-yearbooks|Facebook recruiting question]].
  
 We are giving an array that represents the path a yearbook will take to get signed. The index of each element represents the student. We optimize by keeping track of what students are part of a circuit of signatures. Those student's path do not then need to be calculated. We are giving an array that represents the path a yearbook will take to get signed. The index of each element represents the student. We optimize by keeping track of what students are part of a circuit of signatures. Those student's path do not then need to be calculated.
          
 +Algorithm:
 +<code pseudo [enable_line_numbers="true"]>
 +FUNCTION Explore(Yearbook PATH, vertex V, set SEEN)
 +  if V in SEEN
 +    return
 +  insert V in SEEN
 +  explore(PATH[V-1])
 +
 +FUNC signature(Yearbook PATH)
 +  out vector initalized to PATH size + 1 of -1's
 +  iterate i from 1 to PATH size inclusive
 +    if out[i] != -1
 +      explore(i)
 +      iterate E over elements in SEEN
 +        out[E] = SEEN size
 +  out.erase(out.begin)
 +  return out
 +</code>
 +
 +<code cpp [enable_line_numbers="true"]>
 +void explore(vector<int> &arr, unordered_set<int> &seen, int v)
 +{
 +  if(seen.count(v) > 0){
 +    return;
 +  }
 +  seen.insert(v);
 +  explore(arr, seen, arr[v-1]);
 +  return;
 +}
 +
 +vector <int> findSignatureCounts(vector <int> arr) {
 +  int n = arr.size();
 +  vector<int> out(n, -1);
 +  for(int i = 1; i <= n; i++){
 +    // an unexplored yearbook
 +    if(out[i-1] == -1){
 +      unordered_set<int> seen;
 +      explore(arr, seen, i);
 +      for(auto& e : seen){
 +        out[e-1] = seen.size();
 +      }
 +    }
 +  }
 +  return out;
 +}
 +</code>
          
 ===== Course Schedule ===== ===== Course Schedule =====
Line 1029: Line 1744:
  
 Algorithm: Algorithm:
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1.  OPTIMIZATION: Build unordered set of explored vertices called GOOD +OPTIMIZATION: Build unordered set of explored vertices called GOOD 
-2.  Build adjacency list Adj (unoredered map of vector<int>) +Build adjacency list Adj (unoredered map of vector<int>) 
-3.    Iterate over edges, adj[left vertex].push_back(right vertex) +  Iterate over edges, adj[left vertex].push_back(right vertex) 
-4.   + 
-5.  Iterate v over Adj list +Iterate v over Adj list 
-6.    OPT: If v is in good, CONTINUE, no need to check +  OPT: If v is in good, CONTINUE, no need to check 
-7.    create seen set of ints +  create seen set of ints 
-8.    If cycleDFS of v vertex returns TRUE, we have a cycle +  If cycleDFS of v vertex returns TRUE, we have a cycle 
-9.      return false +    return false 
-10.  + 
-11. // Return true if there is a cycle, false otherwise +// Return true if there is a cycle, false otherwise 
-12. FUNCTION cycleDFS( take in Adj, seen, and vertex v) +FUNCTION cycleDFS( take in Adj, seen, and vertex v) 
-13.   OPT: If v is in good, return false, no need to check +  OPT: If v is in good, return false, no need to check 
-14.   check if v in seen +  check if v in seen 
-15.     If true, return true, there is a cycle +    If true, return true, there is a cycle 
-16.   iterate over n Neighbors of vertex v +  iterate over n Neighbors of vertex v 
-17.     OPT: If n is in good, continue +    OPT: If n is in good, continue 
-18.     If cycleDFS of n is true +    If cycleDFS of n is true 
-19.       return true +      return true 
-20.   // if we are here there are no cycles +  // if we are here there are no cycles 
-21.   Remove v from seen, so we can backtrack without false positives +  Remove v from seen, so we can backtrack without false positives 
-22.   return false+  return false
 </code> </code>
  
 {{:pasted:20200820-041830.png?400}} {{:pasted:20200820-041830.png?400}}
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 class Solution { class Solution {
 public: public:
Line 1129: Line 1844:
 {{:pasted:20200820-193246.png?500}} {{:pasted:20200820-193246.png?500}}
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 class Solution { class Solution {
 public: public:
Line 1216: Line 1931:
 Algrithm: Algrithm:
  
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1. make a multiset of numbers +make a multiset of numbers 
-2. sort by end date +sort by end date 
-3. start a last_end int to 0 +start a last_end int to 0 
-4. iterate i from 0 to end of courses +iterate i from 0 to end of courses 
-5.   if we can take the class : if last_end + courses[i][0] <= courses[i][1] +  if we can take the class : if last_end + courses[i][0] <= courses[i][1] 
-6.     take it: last_end += courses[i][0], set insert courses[i][0] +    take it: last_end += courses[i][0], set insert courses[i][0] 
-7.   if we CAN't take the class +  if we CAN't take the class 
-8.     is the largest element in the taken set longer or EQUAL to this course we can't take? +    is the largest element in the taken set longer or EQUAL to this course we can't take? 
-9.       delete the largest elemetn in the set, and insert this new one.  +      delete the largest elemetn in the set, and insert this new one.  
-10.       last_end doesnt' stay the same! It gets shifted back by our time saved +       last_end doesnt' stay the same! It gets shifted back by our time saved 
-11. return size of set+ return size of set
 </code> </code>
  
 Code: Code:
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 int scheduleCourse(vector<vector<int>>& courses) { int scheduleCourse(vector<vector<int>>& courses) {
   // set of durations of classes that we have taken   // set of durations of classes that we have taken
Line 1283: Line 1998:
 Algorithm: Algorithm:
  
-<code>+<code pseudo [enable_line_numbers="true"]>
 FUNCTION findMinArrows( 2d array of baloon bounds) FUNCTION findMinArrows( 2d array of baloon bounds)
   sort INPUT array by end locations   sort INPUT array by end locations
Line 1297: Line 2012:
 Code: Code:
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 int findMinArrowShots(vector<vector<int>>& points) { int findMinArrowShots(vector<vector<int>>& points) {
   // Sort by end first   // Sort by end first
Line 1334: Line 2049:
 Algorithm: Algorithm:
  
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1. sort by end times +sort by end times 
-2. set last end to a negative number +set last end to a negative number 
-3. iterate i over meetings +iterate i over meetings 
-4.   if start time of i is greater or equal to last end,  +  if start time of i is greater or equal to last end,  
-5.      ans++, last meeting = this one +     ans++, last meeting = this one 
-6.      print out the meeting +     print out the meeting 
-7. return ans+return ans
 </code> </code>
  
 Code: Code:
  
-<code>+<code cpp [enable_line_numbers="true"]>
 int greedyMeeting(vector<vector<int>> &m) int greedyMeeting(vector<vector<int>> &m)
 { {
Line 1384: Line 2099:
 creating a compare function like so: creating a compare function like so:
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 bool compare(const vector<int>& a, const vector<int>&b) bool compare(const vector<int>& a, const vector<int>&b)
 { {
Line 1413: Line 2128:
  
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 bool compare(const vector<int> &a, const vector<int> &b) bool compare(const vector<int> &a, const vector<int> &b)
 { {
Line 1456: Line 2171:
  
 </code> </code>
 +
 +===== Frog Jump =====
 +[[https://leetcode.com/problems/frog-jump/|Leetcode]].
 +
 +Frog jump problem. Fucking confuused. Wtf??? I think i solved it but have no
 +idea how it works out.vTheres a test case that I don't understand. I figured
 +out what I did wrong, i misread the probem!!! k is the previous jump. My
 +memo approach was spot on tho. NEED TO WRITE NOTES ON THIS. 
 +
 +Had to memo it to make it.
  
 ===== Jump Game ===== ===== Jump Game =====
Line 1472: Line 2197:
 reach a maximum reach that we can. reach a maximum reach that we can.
  
-<code>+<code pseudo [enable_line_numbers="true"]>
 FUNC: isPossible(array INPUT) FUNC: isPossible(array INPUT)
   MAX_REACH = 0, i = 0;   MAX_REACH = 0, i = 0;
Line 1516: Line 2241:
 Implement your own power function. The following is the naive algorithm and takes too much time: Implement your own power function. The following is the naive algorithm and takes too much time:
  
-<code c>+<code cpp [enable_line_numbers="true"]>
  
 class Solution { class Solution {
Line 1542: Line 2267:
 {{::screen_shot_2020-07-08_at_11.55.31_am.png?400|}} {{::screen_shot_2020-07-08_at_11.55.31_am.png?400|}}
  
-<code c>+<code cpp [enable_line_numbers="true"]>
 class Solution { class Solution {
 public: public:
Line 1580: Line 2305:
 with the valid.  Valid then becomes my new array size. with the valid.  Valid then becomes my new array size.
          
-===== Search in a Rotated Array II.  =====+===== Search in a Rotated Array I and II.  =====
  
-Really interesting one cause theres dupes and rotations. Idea is to split the +[[https://leetcode.com/problems/search-in-rotated-sorted-array|Leetcode 33]]. 
-array and based on its bounds, you have 3 possible situations: +[[https://leetcode.com/problems/search-in-rotated-sorted-array|Leetcode 34]]. 
-  * You have a normal sorted list cause left bound smaller than right bound. Do a normal bin search + 
-  * Left bound is == to right bound, do a linear search +**Suppose an array sorted in ascending order is rotated at some pivot unknown to 
-  * You have a pivot somewhere. You check to see if the left array is sorted right. If it is, check to see if your target is in it. If it is, search in it.  +you beforehand. You are given a target value to search. If found in the array 
-  * If it isn't in it, it's gotta be on the other side!  Remove duplicates from a sorted list+return true, otherwise return false. 
 + 
 +Version I has no duplicates, and version II has duplicates.** 
 + 
 +We deal with this problem but splitting the search space in half, with a left 
 +and right half. One of these halves will have a sorted array, which we can use 
 +to check if the number we are looking for is in it or not. 
 + 
 +Cases: 
 +  - the number is in the middle 
 +  - the left is greater than the middle.  
 +    - Pivot is in the left half, right half is sorted 
 +  - middle is greater than the right. Pivot is in the right 
 +    - Pivot is in the right half, left half is sorted 
 + 
 +To deal with duplicates we elagantly add a 4th case as an ''else'' that 
 +decrements the right pointer by one. For this to work we also have to add a 
 +check in the first case to see if the right pointer is the number we are looking 
 +for. 
 + 
 +Code: 
 + 
 +<code cpp [enable_line_numbers="true"]> 
 +int search(vector<int>& nums, int target) { 
 +  int left = 0, right = nums.size() - 1; 
 +  // For this type of binary search we need to handle the case where left is the same as right 
 +  while(left <= right){ 
 +    int mid = left + (right - left) / 2; 
 + 
 +    // Check if element is in the middle of the right one 
 +    // We add the right check for the duplicate 
 +    if(nums[mid] == target || nums[right] == target){ 
 +      return true; 
 +    } 
 +    // pivot is in left. right is sorted 
 +    else if(nums[left] > nums[mid]){ 
 +      // check if we are in the right 
 +      if(nums[mid] < target && target <= nums[right] ){ 
 +        left = mid + 1; 
 +      }else{ 
 +        right = mid - 1; 
 +      } 
 +    } 
 +    // pivot is in right. left is sorted 
 +    else if(nums[mid] > nums[right]){ 
 +      if(nums[left] <= target && target < nums[mid]){ 
 +        right = mid - 1; 
 +      } 
 +      else{ 
 +        left = mid + 1; 
 +      } 
 +      // nums[left] is equal or smaller than nums[mid] 
 +      // nums[mid] is equal or smaller than nums[right] 
 +    // This check is for dealing with duplicates. 
 +    }else { 
 +      right--; 
 +    } 
 +  } 
 +  return false; 
 +} 
 +</code> 
 + 
 +===== Find Minimum in Rotated Sorted Array II ===== 
 + 
 +[[https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/|Leetcode 154]]. 
 + 
 +**An array sorted in ascending order is rotated at some pivot unknown to you 
 +beforehand. Find the minimum element. The array may contain duplicates. 
 + 
 +eg.** 
 +''[4,5,6,7,0,1,2])'' 
 + 
 +This problem groups together a bunch of problems: binary search, finding a 
 +pivot, and dealing with duplicates. The issue with this problem is running into 
 +problems dealing with edge cases, such as an array with all duplicates. 
 + 
 +The solution is to break it down into its concise cases while maintaining 
 +correctness of the algorithm by not skipping over any elements in the search. 
 + 
 +The solution structure is to maintain a low and high pointer and iterating in a 
 +while loop with the condition that low is smaller than high. At the start of 
 +every iteration we calculate the middle index. 
 + 
 +The concise cases are as follows: 
 +  - the middle number is higher than the high pointer. Look in the right half 
 +  - the middle number is lower than the low pointer. Look in the left half 
 +  - if none of above cases, move the high pointer one lower 
 + 
 +Then return the low pointer 
 + 
 +<code> 
 +l   m   h 
 +9 0 1 2 3 
 + 
 +    l h 
 +2 2 2 1 2 
 +</code> 
 + 
 + 
 +<code cpp [enable_line_numbers="true"]> 
 +int findMin(vector<int>& nums) { 
 +  int low = 0, high = nums.size() - 1; 
 +  while(low < high){ 
 +    int mid = low + (high - low) / 2; 
 +    if(nums[mid] > nums[high]){ 
 +      low = mid + 1; 
 +    } 
 +    else if(nums[mid] < nums[low]){ 
 +      high = mid; 
 +    } 
 +    else{ 
 +      high -= 1; 
 +    } 
 +  } 
 +  return nums[low]; 
 +} 
 +</code>
  
 ===== Partition List ===== ===== Partition List =====
 +
 +[[https://leetcode.com/problems/partition-list/|Leetcode 86]].
 +
 +**Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
 +
 +You should preserve the original relative order of the nodes in each of the two
 +partitions.**
  
 Make sure elements greater. Had a hard time with this one Make sure elements greater. Had a hard time with this one
Line 1595: Line 2443:
 the list if they met a certain condition. Problem was that I entered an infinite the list if they met a certain condition. Problem was that I entered an infinite
 loop because I would get to the nodes I pushed back and keep pushing them back. loop because I would get to the nodes I pushed back and keep pushing them back.
-I came up with a better one pass solution after I redid it.+ 
 +I then solved it by looking for groups of nodes that are bigger than ''x''. I 
 +Then moved them with a node after them that was less than ''x''. 
 + 
 +Algorithm: 
 + 
 +{{:pasted:20200831-230233.png?500}} 
 + 
 +<code cpp [enable_line_numbers="true"]> 
 +ListNode* partition(ListNode* head, int x) { 
 +  ListNode dh(0, head); 
 +  ListNode *prev = &dh, *cur = head; 
 + 
 +  while(cur != NULL){ 
 +    if(prev->next->val < x){ 
 +      prev = prev->next; 
 +    } 
 +    if(cur->val >= x){ 
 +      while(cur->next != NULL && cur->next->val >= x){ 
 +        cur = cur->next; 
 +      } 
 + 
 +      if(cur->next == NULL){ 
 +        return dh.next; 
 +      } 
 + 
 +      ListNode* next = cur->next; 
 +      cur->next = next->next; 
 +      next->next = prev->next; 
 +      prev->next = next; 
 +    }else{ 
 +      cur = cur->next; 
 +    } 
 +  } 
 +  return dh.next; 
 +} 
 +</code> 
 + 
 +There is a MUCH EASIER way to do this! Build two lists, one less than and one 
 +greater than, and then connect them in the end!!!!!!! 
 +[[https://www.youtube.com/watch?v=IJOQSmoDLa0|Watch this video]]. 
 + 
 + 
 +===== House Robber ===== 
 +[[https://leetcode.com/problems/house-robber/|Leetcode 198]]. 
 + 
 +What a great problem! I first tried a greedy approach by picking the largest 
 +element first, setting it and its neighbors to 0, and then picking the next 
 +largest element, and repeat ''n/2'' times. This fails for ''[2,3,2]]'' as it 
 +generates 3 instead of 4. 
 + 
 +Dynamic programming with bottom up processing. If we are asked to solve a 
 +problem for the n'th thing, we solve for the i'th thing n times. 
 + 
 +Code Recursive: 
 + 
 +<code cpp [enable_line_numbers="true"]> 
 +int explore(vector<int>& nums, int i){ 
 +  // base case 
 +  if(i >= nums.size()){ 
 +    return 0; 
 +  } 
 + 
 +  int yes = 0, no = 0; 
 + 
 +  // choose 
 +  yes = nums[i] + explore(nums, i+2); 
 + 
 +  // unchoose 
 +  no = explore(nums, i+1); 
 + 
 +  return max(yes, no); 
 +} 
 + 
 +int rob(vector<int>& nums) { 
 +  return explore(nums, 0); 
 +} 
 +</code> 
 + 
 +Code DP: 
 + 
 +<code cpp [enable_line_numbers="true"]> 
 +int rob(vector<int>& nums) { 
 +  // solve for the first 3 cases 
 +  if(nums.size() == 0) { return 0;                        } 
 +  if(nums.size() == 1) { return nums[0];                  } 
 +  if(nums.size() == 2) { return max(nums[0], nums[1]);    } 
 + 
 +  // create the dp matrix 
 +  vector<int> dp(nums.size(), 0); 
 + 
 +  // build the dp matrix and seed it with the first two cases 
 +  dp[0] = nums[0]; 
 +  dp[1] = max(nums[0], nums[1]); 
 + 
 +  // iterate over the rest 
 +  for(int i = 2; i < nums.size(); i++){ 
 +    dp[i] = max(dp[i-2] + nums[i], dp[i-1]); 
 +  } 
 + 
 +  return dp.back(); 
 +} 
 +</code> 
 + 
 +Code Simple DP (Kadane): 
 +<code cpp [enable_line_numbers="true"]> 
 +int rob(vector<int>& nums) { 
 +  int prev = 0, cur = 0; 
 +  for(auto& num : nums){ 
 +    // temp keeps the max of one house ago 
 +    int temp = cur; 
 +    cur = max(prev + num, cur); 
 +    prev = temp; 
 +  } 
 +  return cur; 
 +} 
 +</code> 
  
 ===== Maximum Subarray ===== ===== Maximum Subarray =====
Line 1605: Line 2570:
 {{:pasted:20200711-155528.png?500}} {{:pasted:20200711-155528.png?500}}
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 int maxSubArray(vector<int>& nums) { int maxSubArray(vector<int>& nums) {
-    int cur_max = nums[0], max_out = nums[0]; +  int cur_max = nums[0], max_out = nums[0]; 
-     + 
-    for(int i = 1; i < nums.size(); i++) +  for(int i = 1; i < nums.size(); i++) 
-    { +  { 
-        cur_max = max(nums[i], cur_max + nums[i]); +    cur_max = max(nums[i], cur_max + nums[i]); 
-        max_out = max(cur_max, max_out); +    max_out = max(cur_max, max_out); 
-    } +  } 
-    return max_out;+  return max_out;
 } }
 </code> </code>
Line 1640: Line 2605:
 **Find-Max-Crossing-Subarray Algorithm** **Find-Max-Crossing-Subarray Algorithm**
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 int maxCross(vector<int>&nums, int& l, int &mid, int& r) int maxCross(vector<int>&nums, int& l, int &mid, int& r)
 { {
Line 1698: Line 2663:
 {{:pasted:20200811-212403.png?500}} {{:pasted:20200811-212403.png?500}}
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 int maxProfit(vector<int>& prices) { int maxProfit(vector<int>& prices) {
          
Line 1729: Line 2694:
 Amazingly you get to test every possible subarray in one pass. Really awesome! Amazingly you get to test every possible subarray in one pass. Really awesome!
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 int maxProduct(vector<int>& nums)  int maxProduct(vector<int>& nums) 
 { {
Line 1757: Line 2722:
 {{:pasted:20200809-155218.png?500}} {{:pasted:20200809-155218.png?500}}
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 vector<int> productExceptSelf(vector<int>& nums) { vector<int> productExceptSelf(vector<int>& nums) {
  
Line 1780: Line 2745:
   return out;   return out;
 } }
 +</code>
 +
 +===== Minimum Size Subarray Sum =====
 +
 +[[https://leetcode.com/problems/minimum-size-subarray-sum/|Leetcode 209]].
 +
 +**Given an array of n positive integers and a positive integer s, find the
 +minimal length of a contiguous subarray of which the sum ≥ s. If there isn't
 +one, return 0 instead.**
 +
 +I solved this problem using a two pointer approach. The two pointers bound a
 +subarray whose sum is updated as the pointers move. The trick is how to advanced
 +the pointers. The right pointer moves up if the sum doesn't meet the condition.
 +The left pointer moved up if the sum meets the condition. 
 +
 +I also worried about the case where the left pointer advanced over the right
 +pointer but that is actually fine. The left pointer can only advanced over the
 +right pointer once, at which case the sum will be 0 and invalidate the case.
 +
 +Algorithm:
 +
 +<code pseudo [enable_line_numbers="true"]>
 +Function: min subarray : take in nums array and number s
 +  left = 0, min_length = 0, sum = 0
 +
 +  iterate right from 0 to nums size
 +    sum += nums[i]
 +    while sum is greater than s
 +      min_length = min( min_length, i - left + 1 )
 +      remove nums[last] from sum
 +      move up left pointer
 +  return min_length
 </code> </code>
  
Line 1791: Line 2788:
 Find the longest substring without repeating characters. Cute use of an unordered_set to keep track of seen characters while implement two pointers for a sliding window. The sliding window is your valid substring. You have a left and right pointer. Advance the right pointer and if the character is not in the set, great, ans = max(right - left, ans). If the character is found in the set, remove the character at the left pointer, advancing the left and try again. Point is you keep advancing the left pointer till you're good to advance the right. Worst case, the left pointer will go all the way to the right and you start with an empty set. Cool! Find the longest substring without repeating characters. Cute use of an unordered_set to keep track of seen characters while implement two pointers for a sliding window. The sliding window is your valid substring. You have a left and right pointer. Advance the right pointer and if the character is not in the set, great, ans = max(right - left, ans). If the character is found in the set, remove the character at the left pointer, advancing the left and try again. Point is you keep advancing the left pointer till you're good to advance the right. Worst case, the left pointer will go all the way to the right and you start with an empty set. Cool!
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 int lengthOfLongestSubstring(string s) { int lengthOfLongestSubstring(string s) {
   unordered_set<char> seen;   unordered_set<char> seen;
Line 1811: Line 2808:
   return ans;   return ans;
 } }
 +</code>
 +
 +===== Minimum Window Substring =====
 +[[https://leetcode.com/problems/minimum-window-substring/|Leetcode 76]].
 +
 +**Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity ''O(n)''.**
 +
 +You can solve this problem not in ''O(n)'' easily with two maps and compare the count of each letter in the dictionary and window map as you do a sliding window. The tricky part is using a "factor" variable that is equal to the unique number of letters and their counts. 
 +
 +You keep a running ''factor'' of the window and run logic on additions and removals of characters. If the character that you added gives you a count equal to the key count of that character you can increase your factor. If when you remove a character it equals one less they key count, you decrement the factor. This gives you an ''O(1)'' check for window validity.
 +
 +**Algorithm:**
 +<code pseudo [enable_line_numbers="true"]>
 +build a map called dic of letters and count of the t string
 +
 +min_size = 0
 +start = 0;
 +
 +factor is the number of unique characters of atleast a count
 +factor = size of dict
 +
 +pointer left = 0, right = -1
 +while right is less than length - 1
 +    
 +    advanced the right and add it
 +    
 +    while window valid // while factors are equal
 +        check if min_size is 0 or greater than right - left + 1
 +            start = left
 +            update min_size
 +        advance the left
 +        
 + if min_size == 0, return ""
 +return s.sub(start, min_size)
 +        
 +        
 +add a character:
 +    if char isn't in dic return
 +    window[char]++
 +    if window[char] == dic[char]
 +        factor++
 +    
 +remove a char:
 +    if char isn't in dic return
 +    window[char]--
 +    if window[char] == dic[char] - 1
 +        factor--
 +</code>
 +
 +**Code**
 +
 +<code cpp [enable_line_numbers="true"]>
 +class Solution {
 +public:
 +    unordered_map<char, int> dict, window;
 +    int factor;
 +    
 +    void addChar(char c){
 +        if(dict.count(c) == 0){
 +            return;
 +        }
 +        window[c]++;
 +        if(dict[c] == window[c]){
 +            factor++;
 +        }
 +    }
 +    
 +    void removeChar(char c){
 +        if(window.count(c) == 0){
 +            return;
 +        }
 +        window[c]--;
 +        if(dict[c] - 1 == window[c]){
 +            factor--;
 +        }
 +    }
 +    
 +    string minWindow(string s, string t) {
 +        if(t.length() == 0 || s.length() == 0){
 +            return "";
 +        }
 +
 +        for(auto& c : t){
 +            dict[c]++;
 +        }
 +
 +        factor = 0;
 +        int start = 0, min_size = 0;
 +        int left = 0, right = -1;
 +
 +        while(right < (int)s.length() - 1){
 +            //advance right
 +            right++;
 +            addChar(s[right]);
 +
 +            while(factor == dict.size()){
 +                int win_size = right - left + 1;
 +                if(win_size < min_size || min_size == 0){
 +                    start = left;
 +                    min_size = win_size;
 +                }
 +                removeChar(s[left]);
 +                left++;
 +            }
 +        }
 +        return (min_size == 0) ? "" : s.substr(start, min_size);
 +    }
 +};
 </code> </code>
  
Line 1827: Line 2932:
 maps. maps.
  
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1. Create key of characters and counts +Create key of characters and counts 
-2. Create a window key of empty characters and counts, and output list +Create a window key of empty characters and counts, and output list 
-3. Iterate i from 0 to end of input string s +Iterate i from 0 to end of input string s 
-4.   add character at i to window key +  add character at i to window key 
-5.   if i - p.length() is >= to zero, remove character from window key +  if i - p.length() is >= to zero, remove character from window key 
-6.   compare window and key, if match add i - p length + 1 to output +  compare window and key, if match add i - p length + 1 to output 
-7. Return output+Return output
 </code> </code>
  
 Vector based code; Vector based code;
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 vector<int> findAnagrams(string s, string p) { vector<int> findAnagrams(string s, string p) {
   vector<vector<int>> key = vector(26,vector<int>(1,0));   vector<vector<int>> key = vector(26,vector<int>(1,0));
Line 1863: Line 2968:
 Map based code: Map based code:
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 vector<int> findAnagrams(string s, string p) { vector<int> findAnagrams(string s, string p) {
  
Line 1887: Line 2992:
   }   }
   return out;           return out;        
 +}
 +</code>
 +
 +
 +===== Longest Palindromic Substring =====
 +
 +[[https://leetcode.com/problems/longest-palindromic-substring|Leetcode 5]].
 +
 +**Given a string ''s'', return the longest palindromic substring in ''s''.**
 +
 +This is an ''O(n²)'' solution. There is no easy way to solve this problem in
 +''O(n)'' time. The ''O(n)'' solution is [[https://en.wikipedia.org/wiki/Longest_palindromic_substring#Manacher's_algorithm|here]].
 +
 +{{:pasted:20200715-000341.png?500}}
 +
 +You solve this by doing the following:
 +
 +  - Iterate through each character in the string
 +  - For every character try middle out from that character
 +  - For every character assume prev character is the same and middle out it
 +
 +I fell in a bit of a pitfall with this problem when coding the middle out
 +palindrome checker. I kept getting tripped up on what the set the condition of
 +the while loop. I kept getting off by one and had a hard time coming down with a
 +case that didn't give me off by one. Should I check for the current case and
 +then increment the pointers and invalidate them? What about the initial case?
 +
 +If yes, then simply subtract one from the output! The assumption that I needed
 +to grasp is that is we check to see if the current case is valid, and we
 +increment, we will always have a result that is one bigger. Which is fine, just
 +need to correct for it.
 +
 +**Algorithm:**
 +
 +<code psuedo [enable_line_numbers="true"]>
 +int isPali(string, left and right)
 +    while char at left and char at right are the same and left and right are in bounds
 +        move left left and right right
 +    return out with left pointer + 1, and count with r - l + 1
 +
 +struct POD start len
 +for every letter
 +    single = isPali(index index)
 +    double = isPali(index - 1, index)
 +    pick the bigger one and max against global
 +        
 +return substring
 +</code>
 +
 +**Code:**
 +
 +<code cpp [enable_line_numbers="true"]>
 +struct Out{
 +  int index;
 +  int len;
 +  Out(int i = 0, int l = 0){
 +    index = i;
 +    len = l;
 +  }
 +};
 +
 +Out pal(string& s, int l , int r){
 +  // while inbounds and same char
 +  while(l >= 0 && r < s.length() && s[l] == s[r]){
 +    l--;
 +    r++;
 +  }
 +  // Shift back the start pointer because it's gonna be off by one
 +  // r will be off by one to the right, so subtract r from l and then dec 1
 +  return Out(l + 1, r - l - 1);
 +}
 +
 +string longestPalindrome(string s) {
 +  // first is index, second is len
 +  Out max;
 +
 +  // first pass single char mid out
 +  for(int i = 0; i < s.length(); i++){
 +
 +    // Single character check
 +    Out cur1 = pal(s, i, i);
 +    // Double character check
 +    Out cur2 = pal(s, i-1, i);
 +    // Pick the biggest one
 +    Out cur = (cur1.len > cur2.len) ? cur1 : cur2;
 +    max = (max.len > cur.len) ? max : cur;
 +  }
 +  return s.substr(max.index, max.len);
 } }
 </code> </code>
Line 1905: Line 3098:
 Algorithm: Algorithm:
  
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1.  FUNCTION isPalindrome ( string s, left pointer, right pointer) +FUNCTION isPalindrome ( string s, left pointer, right pointer) 
-2.    while left pointer is less than right pointer +  while left pointer is less than right pointer 
-3.      if character under left pointer is not the same as right pointer character +    if character under left pointer is not the same as right pointer character 
-4.        return false +      return false 
-5.    return true +  return true 
-6.   + 
-7.  FUNCTION explore(string S, int START,  +FUNCTION explore(string S, int START,  
-8.                    array of string CUR, array of array of strings OUT) +                  array of string CUR, array of array of strings OUT) 
-9.    if START is equal to string length +  if START is equal to string length 
-10.     push in CUR to OUT, and return +    push in CUR to OUT, and return 
-11.   Iterate from I = START to S.length() +  Iterate from I = START to S.length() 
-12.     if the string from START to I is NOT a palindrome, continue +    if the string from START to I is NOT a palindrome, continue 
-13.     create a substring that goes from START to I and push it into CUR +    create a substring that goes from START to I and push it into CUR 
-14.     explore S, i + 1, CUR, OUT +    explore S, i + 1, CUR, OUT 
-15.     pop the last element of CUR +    pop the last element of CUR 
-16.  + 
-17. Call explore with START of 0+Call explore with START of 0
 </code> </code>
  
 Code: Code:
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 // return true if string is palindrome, false otherwise // return true if string is palindrome, false otherwise
 bool isPalin(string& in, int start, int end) bool isPalin(string& in, int start, int end)
Line 1968: Line 3161:
 } }
 </code> </code>
- 
-===== Longest Palindromic String ===== 
- 
-Tricky son-of-a-gun. Easiest way is to brute force, and check if every possible substring is a palindrome. 
- 
-Next best thing is ''O(n²)'' solution by doing a two pass. First pass you check every character and go middle out, next pass find any double characters and then middle out them. 
- 
-{{:pasted:20200715-000341.png?500}} 
  
 ===== Palindrome Pairs ===== ===== Palindrome Pairs =====
Line 1997: Line 3182:
  
 Append Example: Append Example:
-<code>+<code pseudo [enable_line_numbers="true"]>
 // Matching the following: // Matching the following:
 word1 = petonot  word1 = petonot 
Line 2022: Line 3207:
  
 The hashtable gives the 0(1) lookup speed, and avoids the linear search. The hashtable gives the 0(1) lookup speed, and avoids the linear search.
 +
 +===== Isomorphic Strings ===== 
 +[[https://leetcode.com/problems/isomorphic-strings/|Leedcode]].
 +
 +**Given two strings s and t, determine if they are isomorphic.
 +Two strings are isomorphic if the characters in s can be replaced to get t.
 +All occurrences of a character must be replaced with another character while
 +preserving the order of characters. No two characters may map to the same
 +character but a character may map to itself.**
 +
 +This wasn't THAT easy! I created a map from one string to another but then
 +realized that doesn't work for all cases, because two different characters can't
 +map to the same character. I then created two maps from both directions but the
 +code is pretty hard to read. 
 +
 +A much more elegant solution is to simple run the algorithm twice from both
 +sides.
 +
 +<code pseudo [enable_line_numbers="true"]>
 +if char lenghts aren't the same, return false
 +
 +keep a dictionary array of characters
 +for i 0 to s size
 +    tchar = t[pointer], schar = s[pointer]
 +    if dictionary[tchar] is equal to some flag character, set it equal to schar
 +    if dictionary[tchar] doesn't equal schar, return false
 +return true
 +</code>
 +
 +<code cpp [enable_line_numbers="true"]>
 +bool isIsomorphic(string s, string t) {
 +  vector<char> smap(256, '*');
 +  vector<char> tmap(256, '*');
 +
 +  if(s.length() != t.length()){
 +    return false;
 +  }
 +
 +  for(int i = 0; i < s.length(); i++){
 +    char tchar = t[i], schar = s[i];
 +    if(tmap[tchar] != schar && smap[schar] != tchar){
 +      if(tmap[tchar] == '*' && smap[schar] == '*' ){
 +        tmap[tchar] = schar;
 +        smap[schar] = tchar;
 +      } else{
 +        return false;
 +      }
 +    }
 +  }
 +  return true;
 +}
 +
 +// NEW WAY:
 +bool isIsomorphic(string s, string t) {
 +  return isIso(s,t) && isIso(t,s);
 +}
 +
 +bool isIso(string s, string t) {
 +  vector<char> map(256, '*');
 +
 +  if(s.length() != t.length()){
 +    return false;
 +  }
 +
 +  for(int i = 0; i < s.length(); i++){
 +    char tchar = t[i], schar = s[i];
 +    if(map[tchar] == '*'){
 +      map[tchar] = schar;
 +    }
 +    if(map[tchar] != schar){
 +      return false;
 +    }
 +  }
 +  return true;
 +}
 +</code>
  
 ===== Generate Parenthesis ===== ===== Generate Parenthesis =====
Line 2031: Line 3292:
 [[https://leetcode.com/problems/task-scheduler/solution/|Leetcode 621]] [[https://leetcode.com/problems/task-scheduler/solution/|Leetcode 621]]
  
-I tried solving this problem by implementing a task scheduler that prioritized +**Given a characters array tasks, return the least number of units of times that 
-tasks that had no cooldown and also the largest task count.+the CPU will take to finish all the given tasks. **
  
-The information that I actually did come across, but didn't use it well enough, +This problem needs to be broken down into some basic parts:
-is that the answer, which is the least time units it takes to do all tasks is +
-bounded by the most frequent task.+
  
-So for a task list of 3 A's, 2 B's , 1 C the answer becomes:+  - The result is the count of tasks plus whatever idle time we have 
 +  - The frequency of the tasks we need 
 +  - The problem is bounded by the task with the maximum frequency 
 +  - Edge case of having multiple tasks with a max frequency
  
-<code> +There are some bits in the algorithm that look tricky, like the min's and max's 
-A B C COOLDOWN A B COOLDOWN A+but if you go back to the basic keys for solving this problem, it will make 
 +sense! 
 + 
 +<code pseudo [enable_line_numbers="true"]> 
 +Function: least Interval ( tasks, n cooldown) 
 +  Create a vector of frequencies 
 +  Sort the frequencies from high to low 
 + 
 +  idle_time = maximum ( frequency - 1 ) * n 
 + 
 +  iterate i from 1 to end 
 +    Subtract from idle_time the min frequency of the task OR the max freq - 1 
 + 
 +  return tasks size + max(idle time or 0 incase it's negative
 </code> </code>
  
-Which becomes:+<code cpp [enable_line_numbers="true"]> 
 +int leastInterval(vector<char>& tasks, int n) { 
 +  vector<int> freq(26, 0); 
 +  for(auto& task : tasks){ 
 +    freq[task - 'A']++; 
 +  }
  
-<code> +  sort(freq.begin(), freq.end(), greater<int>()); 
-(count of most frequent task - 1) * max(COOLDOWN, count_of_tasks - 1) + count of + 
-most frequent task+  int idle_time = (freq[0] - 1) * n; 
 + 
 +  for(size_t i = 1; i < freq.size(); i++){ 
 +    idle_time -= min(freq[0] - 1, freq[i]); 
 +  } 
 + 
 +  return tasks.size() + max(idle_time, 0); 
 +}
 </code> </code>
  
Line 2066: Line 3353:
 Code: Code:
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 void explore(Node* node, Node* pr) void explore(Node* node, Node* pr)
 { {
Line 2123: Line 3410:
 Code: Code:
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 TreeNode* flatten_child(TreeNode* node) TreeNode* flatten_child(TreeNode* node)
 { {
Line 2148: Line 3435:
     return right_tail;     return right_tail;
 } }
 +</code>
 +
 +===== Convert Binary Search Tree to Sorted Doubly Linked List =====
 +[[https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/|Leetcode 426]].
 +
 +**Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.**
 +
 +You have to realize that you need to flatten child nodes and then return both
 +head and tail up to the caller. The caller than rearranges themselves in the
 +right way.
 +
 +Algorithm:
 +
 +<code pseudo [enable_line_numbers="true"]>
 +FUNC flatten(node) return: Head and Tail of flattened list
 +    if node is null
 +        return null head and null tail
 +    
 +    (Left Head,  Left Tail)  flatten(Left child)
 +    (Right Head, Right Tail) flatten(Right child)
 +    
 +    If Left Tail not null, Connect Left  Tail with node
 +    If Reft Head not null, Connect Right Head with node
 +    
 +    HeadTail out;
 +    
 +    //Set the proper Head
 +    out.head = (Left Head != NULL) ? Left Head : node;
 +    
 +    //Set the proper Tail
 +    out.tail = (Right Tail != NULL) ? Right Tail : node;
 +    
 +FUNC caller(node) return: node
 +    if node is null return
 +    HeadTail = flatten(node)
 +    Head left = tail
 +    tail right = head
 +    return head
 +    return out
 +</code>
 +
 +Code:
 +
 +<code cpp [enable_line_numbers="true"]>
 +// Our return object containing a head and tail
 +class HeadTail{
 +  public:
 +    Node* head;
 +    Node* tail;
 +
 +    HeadTail(){}
 +
 +    HeadTail(Node* _head, Node* _tail) : head(_head), tail(_tail) {}
 +};
 +
 +class Solution {
 +  public:
 +    HeadTail flatten(Node* node){
 +      if(node == NULL){
 +        return HeadTail(NULL, NULL);
 +      }
 +
 +      HeadTail leftHT  = flatten(node->left);
 +      HeadTail rightHT = flatten(node->right);
 +
 +      if(leftHT.tail != NULL){
 +        leftHT.tail->right = node;
 +        node->left = leftHT.tail;
 +      }
 +      if(rightHT.head != NULL){
 +        rightHT.head->left = node;
 +        node->right = rightHT.head;
 +      }
 +
 +      HeadTail out;
 +      out.head = (leftHT.head != NULL)  ? leftHT.head  : node;
 +      out.tail = (rightHT.tail != NULL) ? rightHT.tail : node;
 +      return out;
 +    }
 +
 +    Node* treeToDoublyList(Node* root) {
 +      if(root == NULL){
 +        return NULL;
 +      }
 +      HeadTail out = flatten(root);
 +      out.head->left = out.tail;
 +      out.tail->right = out.head;
 +      return out.head;
 +    }
 +};
 </code> </code>
  
Line 2172: Line 3549:
 parent node again.  parent node again. 
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 class BSTIterator { class BSTIterator {
 public: public:
Line 2224: Line 3601:
 Algorithm: Algorithm:
  
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1.   FUNC: BUILD MIN ( Take in a node ) +FUNC: BUILD MIN ( Take in a node ) 
-2.     if node NULL return +  if node NULL return 
-3.     Add node to stack +  Add node to stack 
-4.     if node has left child-> BUILDMIN(LEFT CHILD) +  if node has left child-> BUILDMIN(LEFT CHILD) 
-5.    + 
-6.   FUNC: NEXT() +FUNC: NEXT() 
-7.     Node OUT = stack top +  Node OUT = stack top 
-8.     pop stack top +  pop stack top 
-9.     BUILD MIN( OUT->right child) +  BUILD MIN( OUT->right child) 
-10.    return OUT's val +  return OUT's val 
-11.   + 
-12.  FUNC: HAS NEXT() +FUNC: HAS NEXT() 
-13.    return true if size of stack greater then 0, false otherwise+  return true if size of stack greater then 0, false otherwise
 </code> </code>
  
 Code: Code:
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 class BSTIterator { class BSTIterator {
 public:     public:    
Line 2284: Line 3661:
 Algorithm: Algorithm:
  
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1.  create a queue +create a queue 
-2.  push first node into the the queue +push first node into the the queue 
-3.  while queue isn't empty +while queue isn't empty 
-4.      level size = queue size +    level size = queue size 
-5.      take the back of the queue and add it output +    take the back of the queue and add it output 
-6.      for( i to level size) +    for( i to level size) 
-7.          cur = pop front of queue +        cur = pop front of queue 
-8.          if cur has children, put them in the back of the queue+        if cur has children, put them in the back of the queue
 </code> </code>
  
 Code: Code:
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 vector<int> rightSideView(TreeNode* root) { vector<int> rightSideView(TreeNode* root) {
     // output result     // output result
Line 2351: Line 3728:
  
 Algorithm: Algorithm:
-<code>+<code pseudo [enable_line_numbers="true"]>
 Explore function that takes in node, level, ref to output array Explore function that takes in node, level, ref to output array
   if node is null return   if node is null return
Line 2364: Line 3741:
  
 Code: Code:
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 void explore(TreeNode* node, int level, vector<int> &out) void explore(TreeNode* node, int level, vector<int> &out)
 { {
Line 2401: Line 3778:
 Algorithm: Algorithm:
  
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1.  Create two traces lists one for p and for q +Create two traces lists one for p and for q 
-2.  explore p and build a left trace list +explore p and build a left trace list 
-3.  explore q and build a right trace list +explore q and build a right trace list 
-4.  while the two front elements of the traces equal each other +while the two front elements of the traces equal each other 
-5.    set out to the front of one element +  set out to the front of one element 
-6.    pop the first element of both traces off +  pop the first element of both traces off 
-7.   + 
-8.  // FUNCTION +// FUNCTION 
-9.  Explore starting from a node with a target and reference of the trace list +Explore starting from a node with a target and reference of the trace list 
-10.   If node is null, return false +  If node is null, return false 
-11.   Push out node on the trace list +  Push out node on the trace list 
-12.   if node == target, that means we found it!  +  if node == target, that means we found it!  
-13.       return true +      return true 
-14.   Explore the left, and the right child. If either returns true +  Explore the left, and the right child. If either returns true 
-15.       return true +      return true 
-16.   We haven't found the target from this root, pop our element off the trace list +  We haven't found the target from this root, pop our element off the trace list 
-17.   return false+  return false
 </code> </code>
  
 Code: Code:
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 bool explore(TreeNode* node, TreeNode* target, list<TreeNode*>& trace) bool explore(TreeNode* node, TreeNode* target, list<TreeNode*>& trace)
 { {
Line 2475: Line 3852:
  
 Algorithm: Algorithm:
-<code>+<code pseudo [enable_line_numbers="true"]>
 Explore with a node, a string and a reference to output array Explore with a node, a string and a reference to output array
     If the node is null, JUST RETURN. (we can be in a node with only one child!)     If the node is null, JUST RETURN. (we can be in a node with only one child!)
Line 2487: Line 3864:
  
 Code: Code:
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 void explore(TreeNode* node, string path, vector<string> &out) void explore(TreeNode* node, string path, vector<string> &out)
 { {
Line 2525: Line 3902:
 Algorithm: Algorithm:
  
-<code>+<code pseudo [enable_line_numbers="true"]>
 Explore node with out ref Explore node with out ref
   if node is null, return 0   if node is null, return 0
Line 2538: Line 3915:
 Code: Code:
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 int explore(TreeNode* node, int& out) int explore(TreeNode* node, int& out)
 { {
Line 2571: Line 3948:
 {{:pasted:20200812-162639.png?500}} {{:pasted:20200812-162639.png?500}}
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 int helper(TreeNode* node, int target, vector<int> sums) int helper(TreeNode* node, int target, vector<int> sums)
 { {
Line 2612: Line 3989:
 Also funny, found some [[https://www.reddit.com/r/leetcode/comments/fnxb0z/prefix_sum_with_hashmaphow_to_best_understand_this/|poor guy on the internt who also thinks this is magic]]. Also funny, found some [[https://www.reddit.com/r/leetcode/comments/fnxb0z/prefix_sum_with_hashmaphow_to_best_understand_this/|poor guy on the internt who also thinks this is magic]].
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 class Solution { class Solution {
 public: public:
Line 2694: Line 4071:
  
 Return all three cases && together. Return all three cases && together.
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 class Solution{ class Solution{
 public: public:
Line 2726: Line 4103:
 symmetric pairs. symmetric pairs.
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 class Solution { class Solution {
 public: public:
Line 2751: Line 4128:
         }         }
         return true;         return true;
-    } 
-}; 
-</code> 
- 
-===== Insert In a Sorted Circular Linked List ====== 
- 
-[[https://leetcode.com/problems/insert-into-a-sorted-circular-linked-list/||Leetcode 708]] 
- 
-**Given a node from a Circular Linked List which is sorted in ascending order, 
-write a function to insert a value insertVal into the list such that it remains 
-a sorted circular list.** 
- 
-This problem becomes hard because of the cases you have to check for, for 
-proper insertion of the value. 
- 
-You have to check these cases: 
- 
-  - **case 1**: Simple, value fits between a ''prev'' and ''curr'' pointer. 
-  - **case 2**: We have a pivot, ''prev'' > ''curr''. That means we fit if we are greater than ''prev'', OR we are less than ''curr''. 
-  - **case 3**: We reach back to the start of the list. Just pop us in man. 
- 
-Took me a while to nail down these cases. It is VERY easy to get lost in nested 
-if statements. 
- 
-<code cpp> 
-class Solution { 
-  public: 
- 
-    void insertAfter(Node* node, int i) 
-    { 
-      Node* temp = new Node(i); 
-      temp->next = node->next; 
-      node->next = temp; 
-    } 
- 
-    Node* insert(Node* head, int insert_val) { 
- 
-      // Lets take care of the NULL case 
-      if(head == NULL) 
-      { 
-        Node* temp = new Node(insert_val); 
-        temp->next = temp; 
-        return temp; 
-      } 
- 
-      // two pointers 
-      Node *p = head, *n = head->next; 
- 
-      while(n != head) 
-      { 
-        if(p->val <= insert_val && insert_val <= n->val) 
-        { 
-          insertAfter(p, insert_val); 
-          return head; 
-        } 
-        else if(p->val > n->val) 
-        { 
-          if(p->val <= insert_val || insert_val <= n->val) 
-          { 
-            insertAfter(p, insert_val); 
-            return head; 
-          } 
-        } 
-        p = n; 
-        n = n->next; 
-      } 
- 
-      insertAfter(p, insert_val); 
- 
-      return head; 
     }     }
 }; };
Line 2833: Line 4140:
 Example 1: Example 1:
  
-<code>+<code pseudo [enable_line_numbers="true"]>
 Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
 Output: [[1,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]]
Line 2841: Line 4148:
 Algorithm: Algorithm:
  
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1. If input is less than 2 elements return +If input is less than 2 elements return 
-2. Sort by starting interval +Sort by starting interval 
-3. Put first interval in out array +Put first interval in out array 
-4. Iterate i from 1 to input end +Iterate i from 1 to input end 
-5.   min end = min(end of last interval in out, end of input[i] +  min end = min(end of last interval in out, end of input[i] 
-6.   if start of last interval in out is LESS OR EQUAL to min end +  if start of last interval in out is LESS OR EQUAL to min end 
-7.     Overlap, set end of last interval to the max end of the two +    Overlap, set end of last interval to the max end of the two 
-8.   Else +  Else 
-9.     No overlap, push in input[i] to out +    No overlap, push in input[i] to out 
-10. Return out+ Return out
 </code> </code>
  
 Code: Code:
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 vector<vector<int>> merge(vector<vector<int>>& in) { vector<vector<int>> merge(vector<vector<int>>& in) {
   // Take care of edge case   // Take care of edge case
Line 2919: Line 4226:
  
 Algorithm: Algorithm:
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1.    If node is NULL return NULL +If node is NULL return NULL 
-2.    Add node and copy to map +Add node and copy to map 
-3.    Explore Node with Map +Explore Node with Map 
-4.      iterate over neighbors A +  iterate over neighbors A 
-5.        if not in Map +    if not in Map 
-6.          add copy of A to map. +      add copy of A to map. 
-7.          Explore A with Map +      Explore A with Map 
-8.        Push back copy of A to copy of Node neighbors+    Push back copy of A to copy of Node neighbors
 </code> </code>
  
 Code: Code:
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 void explore(Node* node, unordered_map<Node*, Node*> &copy_map) void explore(Node* node, unordered_map<Node*, Node*> &copy_map)
 { {
Line 2964: Line 4271:
  
 Algorithm: Algorithm:
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1.  If node is NULL return NULL +If node is NULL return NULL 
-2.  Insert node, and a copy of that node (with just the value for now) in a map +Insert node, and a copy of that node (with just the value for now) in a map 
-3.  Push node in a queue +Push node in a queue 
-4.  While queue is not empty +While queue is not empty 
-5.     deque the front of the queue and call it N +   deque the front of the queue and call it N 
-6.     iterate over the neighbors of N, call each one A. +   iterate over the neighbors of N, call each one A. 
-7.       if A is not in the map +     if A is not in the map 
-8.           Insert A, and a copy into the map +         Insert A, and a copy into the map 
-9.       add the copy of A to the neighbor list of the copy of N. +     add the copy of A to the neighbor list of the copy of N. 
-10. Return the copy of node.+Return the copy of node.
 </code> </code>
  
 Code: Code:
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 Node* cloneGraph(Node* node) { Node* cloneGraph(Node* node) {
   if(node == NULL) return NULL;   if(node == NULL) return NULL;
Line 3028: Line 4335:
  
 Algorithm: Algorithm:
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1. Iterate over every element of the graph +Iterate over every element of the graph 
-2.   If the element is unseen land +  If the element is unseen land 
-3.       Increment result counter +      Increment result counter 
-4.       Explore unseen land +      Explore unseen land 
-5.           Mark land as seen +          Mark land as seen 
-6.           Explore all unseen connected land+          Explore all unseen connected land
 </code> </code>
  
  
 Code: Code:
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 vector< vector<int> > landN(vector<vector<char>>& grid, int& i, int& j) vector< vector<int> > landN(vector<vector<char>>& grid, int& i, int& j)
 { {
Line 3108: Line 4415:
  
 Algorithm: Algorithm:
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1.  Create color map, key will be vertex index and value will be color or unseen +Create color map, key will be vertex index and value will be color or unseen 
-2.  color: -1 = unseen, 0 one color, 1 another color +color: -1 = unseen, 0 one color, 1 another color 
-3.  Iterate i from 0 to end of graph. Do this to take care of disconnected sub graphs +Iterate i from 0 to end of graph. Do this to take care of disconnected sub graphs 
-4.    if the vertex at i is unseen (-1) +  if the vertex at i is unseen (-1) 
-5.        create a stack of ints +      create a stack of ints 
-6.        push i in the stack +      push i in the stack 
-7.        color the vertex i 0 +      color the vertex i 0 
-8.        while stack is not empty +      while stack is not empty 
-9.            vertex cur will equal top element popped from stack +          vertex cur will equal top element popped from stack 
-10.            // we are now in a colored node. we need to check its neighbors +           // we are now in a colored node. we need to check its neighbors 
-11.            iterate n over neighbors of vertex cur +           iterate n over neighbors of vertex cur 
-12.              if color of n == -1 meaning not colored/seen yet +             if color of n == -1 meaning not colored/seen yet 
-13.                  set color of n the opposite of color of cur +                 set color of n the opposite of color of cur 
-14.                  suspend cur by pushig it to the stack +                 suspend cur by pushig it to the stack 
-15.                  push n to the stack +                 push n to the stack 
-16.                  break out of the iteration +                 break out of the iteration 
-17.              if color of n == color of cur +             if color of n == color of cur 
-18.                  return false cause this is not BIPARTE+                 return false cause this is not BIPARTE
 </code> </code>
  
 Code: Code:
  
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 bool isBipartite(vector<vector<int>>& graph) { bool isBipartite(vector<vector<int>>& graph) {
      
Line 3184: Line 4491:
   }   }
   return true;   return true;
 +}
 +</code>
 +
 +===== Open the Lock =====
 +[[https://leetcode.com/problems/open-the-lock/|Leetcode 752]].
 +
 +**You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots:
 +''0, 1, 2, 3, 4, 5, 6, 7, 8, 9''. The wheels can rotate freely
 +and wrap around: for example we can turn 9 to be 0, or 0 to be 9' Each
 +move consists of turning one wheel one slot.
 +
 +The lock initially starts at ''0000'', a string representing the state of the 4
 +wheels.
 +
 +You are given a list of deadends dead ends, meaning if the lock displays any of
 +these codes, the wheels of the lock will stop turning and you will be unable to
 +open it.
 +
 +Given a target representing the value of the wheels that will unlock the lock,
 +return the minimum total number of turns required to open the lock, or -1 if it
 +is impossible.**
 +
 +This is a really interesting problem that I thought was a backtracking problem
 +at first. It is a graph problem. Each string has 8 neighbors and you have to
 +make the mental connection that for every turn you can only change one digit at
 +a time. You also need to realize that a BFS is the way to go here, because we
 +are looking for one target, and if you do DFS you'll be digging into every path.
 +
 +Standard BFS techniques apply. I got a litle tripped up with implementing a
 +seperator based system for the queue instead of keeping track of layer size.
 +
 +Also for keeping track of turns you have to realize that every layer is a turn.
 +
 +**Algorithm:**
 +
 +<code pseudo [enable_line_numbers="true"]>
 +Build a set of deadends and a seen set
 +Create a queuefor BFS. For less code, you keep a count for the layer
 +
 +add '0000'
 +
 +while the queue isn't empty
 +    increment a turn count
 +    iterate the number of the size of the queue
 +        pop off the top element
 +            if the element is our target, we're good
 +            if the element isn't a dead or seen
 +                add it to seen
 +                add each of its neighbors the queue
 +                
 +return -1 if we get out
 +</code>
 +
 +**Code:**
 +
 +<code cpp [enable_line_numbers="true"]>
 +int openLock(vector<string>& deadends, string target) {
 +  unordered_set<string> d(deadends.begin(), deadends.end()), seen;
 +
 +  queue<string> q;
 +  q.push("0000");
 +
 +  int turns = 0;
 +
 +  while(!q.empty()){
 +    int layer = q.size();
 +    while(layer--){
 +      string cur = q.front();
 +      q.pop();
 +      if(cur == target){
 +        return turns;
 +      }
 +      if(d.count(cur) == 0 && seen.count(cur) == 0){
 +        // Push in our cur to seen
 +        seen.insert(cur);
 +        for(int d = -1; d < 2; d+=2){
 +          for(int i = 0; i < 4; i++){
 +            // generate 8 strings that are increments and decrements
 +            string n = cur;
 +            n[i] += d;
 +            n[i] = (n[i] > '9') ? '0' : (n[i] < '0') ? '9' : n[i];
 +            q.push(n);
 +          }
 +        }
 +      }
 +    }
 +    // We are done with a layer so increment the code
 +    turns++;
 +  }
 +  return -1;
 } }
 </code> </code>
Line 3195: Line 4592:
 tying other accounts together. For example: tying other accounts together. For example:
  
-<code>+<code pseudo [enable_line_numbers="true"]>
 Account 1: A B Account 1: A B
 Account 2: C D Account 2: C D
Line 3219: Line 4616:
  
 Algorithm: Algorithm:
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1.  Build an array of sets of ints to serve as adjancency list +Build an array of sets of ints to serve as adjancency list 
-2.  Initialize the array to have empty set for every index in accounts +Initialize the array to have empty set for every index in accounts 
-3.  Create a map called EMAP of key: email string and value: index of account first seen with it +Create a map called EMAP of key: email string and value: index of account first seen with it 
-4.  Iterate A over accounts +Iterate A over accounts 
-5.      iterate E for all emails of A +    iterate E for all emails of A 
-6.      if E is in EMAP +    if E is in EMAP 
-7.          create adjacency connections: +        create adjacency connections: 
-8.              A to EMAP[E] and EMAP[E] to A +            A to EMAP[E] and EMAP[E] to A 
-9.      else add EMAP[E] = A +    else add EMAP[E] = A 
-10.   +  
-11.  Build our output: create a vector of vectors of strings called OUT +Build our output: create a vector of vectors of strings called OUT 
-12.  Create a SEEN set of ints +Create a SEEN set of ints 
-13.  iterate A over Accounts +iterate A over Accounts 
-14.    if A isn't in SEEN: +  if A isn't in SEEN: 
-15.      create a vector of strings, and add in the name as the first element +    create a vector of strings, and add in the name as the first element 
-16.      Pass this vector and node A into Explore! Explore will fill in the emails +    Pass this vector and node A into Explore! Explore will fill in the emails 
-17.  Return OUT! +Return OUT! 
-18.   + 
-19.  SUBROUTINE: +SUBROUTINE: 
-20.  Explore DFS with params: +Explore DFS with params: 
-21.    accounts ref,  +  accounts ref,  
-22.    adjacency list,  +  adjacency list,  
-23.    seen set  +  seen set  
-24.    output string set ref +  output string set ref 
-25.    node index +  node index 
-26.   + 
-27.    if the node is in the seen set, RETURN +  if the node is in the seen set, RETURN 
-28.    add the nodes emails to the emails output string set +  add the nodes emails to the emails output string set 
-29.    iterate over the neighbors +  iterate over the neighbors 
-30.      explore them!+    explore them!
 </code> </code>
  
 Code: Code:
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 // Depth first traversal of our graph, that builds a set of emails for that connected group // Depth first traversal of our graph, that builds a set of emails for that connected group
 void dfs(vector<vector<string>>& accounts, vector< set<int> > &adj,  void dfs(vector<vector<string>>& accounts, vector< set<int> > &adj, 
Line 3339: Line 4736:
   * You have a pivot somewhere. You check to see if the left array is sorted right. if it is, check to see if your target is in it. If it is, search in it.  If it isn't in it, it's gotta be on the other side!  Remove duplicates from a sorted list   * You have a pivot somewhere. You check to see if the left array is sorted right. if it is, check to see if your target is in it. If it is, search in it.  If it isn't in it, it's gotta be on the other side!  Remove duplicates from a sorted list
  
-===== Partition List =====+===== Merge k Sorted Lists =====
  
-Make sure elements greater. Had a hard time with this one +[[https://leetcode.com/problems/merge-k-sorted-lists/|Leetcode 23]].
-because I picked a approach from the start. I was moving elements to the back of +
-the list if they met a certain condition. Problem was that i entered an infinite +
-loop because i would get to the nodes i pushed back and keep pushing them back. +
-I came up with a better one pass solution after i redid it.+
  
-===== Merge k Sorted Lists =====+**You are given an array of k linked-lists lists, each linked-list is sorted in 
 +ascending order.
  
-[[https://leetcode.com/problems/merge-k-sorted-lists/|Leetcode 23]]+Merge all the linked-lists into one sorted linked-list and return it.**
  
 Very nice little problem. Many ways to solve but here's the nice optimized way. Very nice little problem. Many ways to solve but here's the nice optimized way.
Line 3358: Line 4752:
  
 Algorithm: Algorithm:
-<code> +<code pseudo [enable_line_numbers="true"]> 
-1.   Create a dummyhead and a pointer last that points to it +Create a dummyhead and a pointer last that points to it 
-2.   Create a multimap with key (value of node) and value (pointer to node) +Create a multimap with key (value of node) and value (pointer to node) 
-3.   Iterate over input lists and insert every ListNode and value into the map +Iterate over input lists and insert every ListNode and value into the map 
-4.     only add non null elements +  only add non null elements 
-5.   While multimap has at least 2 elements +While multimap has at least 2 elements 
-6.     pop off the smallest node from the mulitmap = cur +  pop off the smallest node from the mulitmap = cur 
-7.     set last->next = to cur +  set last->next = to cur 
-8.     set last = last next +  set last = last next 
-9.     if cur next isn't null +  if cur next isn't null 
-10.      add it to the multimap +    add it to the multimap 
-11.    if multimap is only one element +  if multimap is only one element 
-12.      make last next point to it +    make last next point to it 
-13.      break +    break 
-14.  return dummyhead next+return dummyhead next
 </code> </code>
  
 Code: Code:
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode* mergeKLists(vector<ListNode*>& lists) {
      
Line 3413: Line 4807:
                        
     return dh.next;     return dh.next;
 +}
 +</code>
 +
 +===== Sort List =====
 +
 +[[https://leetcode.com/problems/sort-list/|Leetcode 148]].
 +
 +**Given the head of a linked list, return the list after sorting it in ascending order.**
 +
 +This problem is easily solved by using ordered containers giving you ''O(n log
 +n)'' time and ''O(n)'' space complexity. 
 +
 +You can get ''O(log n)'' space complexity by doing a merge sort. The trick with
 +merge sort is to use a fast and slow pointer to find the middle of the list.
 +
 +We do this recursively and our base case is a ''NULL'' and a single node.
 +
 +**Algorithm:**
 +
 +<code psuedo [enable_line_numbers="true"]>
 +Merge sort
 +  divide the list in two
 +  mergesort left list
 +  mergesort right list
 +  merge left and right
 +</code>
 +
 +**Code:**
 +
 +<code cpp [enable_line_numbers="true"]>
 +ListNode* mergeSort(ListNode* node){
 +  // If we're a null node
 +  if(node == NULL){
 +    return NULL;
 +  }
 +  // If we're a single node
 +  if(node->next == NULL){
 +    return node;
 +  }
 +
 +  // find the middle with fast and slow pointer
 +  ListNode *fast = node, *slow = node, *slowPrev = NULL;
 +  while(fast && fast->next){
 +    slowPrev = slow;
 +    slow = slow->next;
 +    fast = fast->next->next;
 +  }
 +  // break the lists in two
 +  if(slowPrev){
 +    slowPrev->next = NULL;
 +  }
 +
 +  // Node is gonna be head of left list,
 +  // slow is head of right list
 +  ListNode* left = mergeSort(node);
 +  ListNode* right = mergeSort(slow);
 +
 +  // Merge two sorted lists:
 +  ListNode dh, *cur;
 +  cur = &dh;
 +
 +  while(left && right){
 +    // find the smallest of the two
 +
 +    if(left->val < right->val){
 +      // left has the smaller value
 +      cur->next = left;
 +      left = left->next;
 +    }else{
 +      // right has the smaller value
 +      cur->next = right;
 +      right = right->next;
 +    }
 +    cur = cur->next;
 +  }
 +
 +  // Take care of any remaining nodes
 +  if(left){
 +    cur->next = left;
 +  }
 +  else if(right){
 +    cur->next = right;
 +  }
 +
 +  return dh.next;
 +}
 +
 +ListNode* sortList(ListNode* head) {
 +  return mergeSort(head);
 } }
 </code> </code>
Line 3426: Line 4909:
  
 Code: Code:
-<code cpp>+<code cpp [enable_line_numbers="true"]>
 class LRUCache { class LRUCache {
 public: public:
Line 3470: Line 4953:
     }     }
 }; };
 +</code>
 +
 +===== Word Ladder II =====
 +[[https://leetcode.com/problems/word-ladder-ii/|Leetcode 126]].
 +
 +**Given two words (beginWord and endWord), and a dictionary's word list, find all
 +shortest transformation sequence(s) from beginWord to endWord, such that:
 +
 +  - Only one letter can be changed at a time
 +  - Each transformed word must exist in the word list. Note that beginWord is not a transformed word.  **
 +
 +I learned some new concepts with this problem. Particularly how to store a trace
 +of a path when doing BFS.
 +
 +This problem breaks down in first identifying that this is a graph problem. We
 +have a bunch of vertices that are one edit distance away. We then have to find
 +the SHORTEST paths to the end. 
 +
 +If we needed to find all paths, an exhaustive DFS would work. But in this case
 +we need all shortest paths. This means if we do a BFS, all the shortest paths
 +will be on one layer.
 +
 +At first I built a graph represented by an adjacency list, which was
 +''O(length_of_word * number_of_words²)'' with a memory space of
 +''O(number_of_words²)''. Then I did a one edit away function. You can also build
 +a map of word combinations of each letter removed, requiring
 +''O(number_of_letters*number_of_words)'' space.
 +
 +The other tricky part is the handling seen words. I handled it by removing words
 +in the wordset that we used on this level.
 +
 +**Algorithm:**
 +
 +<code psuedo [enable_line_numbers="true"]>
 +Create a wordList set to give us O(1) lookup in the words
 +Create a queue of string paths
 +Create a bool flag called done and set to false
 +Create an output list of strings
 +Add in the begin word in the queue as the seed path.
 +
 +While we're not done and q isn't empty:
 +  Grab the level size
 +  While levesize--
 +    get the path in the front of the q and pop it
 +    If the path is the end word
 +      add the path to the output list and set done to true
 +    add all the neighbors of this word to the base path
 +    push these new paths to the queue
 +    Add the added words to a visited list
 +  remove all the visited words from the word list
 +</code>
 +
 +**Code:**
 +
 +<code cpp [enable_line_numbers="true"]>
 +vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wL) {
 +
 +  queue<vector<string>> q;
 +
 +  unordered_set<string> wordList;
 +  for(auto w : wL){
 +    wordList.insert(w);
 +  }
 +
 +  q.push({beginWord});
 +
 +  bool done = false;
 +
 +  vector<vector<string>> out;
 +
 +  // Do a BSF Search
 +  while(!done && !q.empty()){
 +    int level = q.size();
 +    // run this loop for every path in this level
 +    list<string> visited;
 +    while(level--){
 +      vector<string> path = q.front();
 +      q.pop();
 +
 +      if(path.back() == endWord){
 +        out.push_back(path);
 +        done = true;
 +      }
 +
 +      // add our the neighbors:
 +      // Theres multiple ways of doing this.
 +      for(int i = 0; i < path.back().length(); i++){
 +        string orig = path.back();
 +        for(char c = 'a'; c <= 'z' ; c++){
 +          orig[i] = c;
 +          if(wordList.count(orig)){
 +            path.push_back(orig);
 +            q.push(path);
 +            path.pop_back();
 +            visited.push_back(orig);
 +          }
 +        }
 +      }   
 +    }
 +    for(auto & w : visited){
 +      wordList.erase(w);
 +    }
 +  }
 +  return out;
 +}
 +</code>
 +
 +===== Word Ladder =====
 +[[https://leetcode.com/problems/word-ladder/|Leetcode 127]].
 +
 +**Given two words (beginWord and endWord), and a dictionary's word list, find
 +the length of the shortest transformation sequence(s) from beginWord to endWord,
 +such that:
 +
 +  - Only one letter can be changed at a time
 +  - Each transformed word must exist in the word list. Note that beginWord is not a transformed word.  **
 +
 +I did this problem after I did part 2 and it was easier. There are a couple of
 +things that are different that you don't need. Namely, we don't need to track
 +paths, so it becomes a much easier BFS problem.
 +
 +**Algorithm:**
 +
 +<code psuedo [enable_line_numbers="true"]>
 +build a set of words
 +make a queue of paths and add first word in it
 +int dist = 0
 +while q isn't empty
 +    dist++
 +    layer = q size
 +    make a seen word list
 +    while(layer--)
 +        pop off path in the q
 +        curword = end of path
 +        if curword is out end word
 +            retun dist
 +        iterate over every char in the curword
 +            mod = curword
 +            iterate c from a to z
 +                mod[i] = c
 +                if(mod in word set)
 +                    add it to the path and add it to the q
 +                    add mod to the seen word list
 +    remove all the seen words from the wordSet
 +    dist++
 +return 0
 +</code>
 +
 +**Code:**
 +
 +<code cpp [enable_line_numbers="true"]>
 +int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
 +  unordered_set<string> wordSet;
 +
 +  // build the word set
 +  for(auto& w : wordList){
 +    wordSet.insert(w);
 +  }
 +
 +  queue<string> q;
 +  q.push(beginWord);
 +  int dist = 0;
 +
 +  while(!q.empty()){
 +    dist++;
 +    int layer = q.size();
 +    while(layer--){
 +      string cur = q.front();
 +      q.pop();
 +      if(cur == endWord){
 +        return dist;
 +      }
 +      for(int i = 0; i < cur.length(); i++){
 +        string mod = cur;
 +        for(char c = 'a'; c <= 'z'; c++){
 +          mod[i] = c;
 +          if(wordSet.count(mod) != 0){
 +            wordSet.erase(mod);
 +            q.push(mod);                            
 +          }
 +        }
 +      }
 +    }
 +  }
 +  return 0;
 +}
 +</code>
 +
 +===== Copy List With Random Pointer =====
 +[[https://leetcode.com/problems/copy-list-with-random-pointer/|Leetcode 138]].
 +
 +**A linked list is given such that each node contains an additional random
 +pointer which could point to any node in the list or null.
 +
 +Return a deep copy of the list.**
 +
 +I first approached this problem by thinking I can just two pass it and build a
 +vector array that I can use to index the nodes. I had the right idea but the
 +random pointers point to a node and not a number, and the numbers aren't unique.
 +What is unique is the memory location.
 +
 +You have to look at the problem and not be scared of writing down the high level
 +algo. That's the whole point of psuedo code, very high level code.
 +
 +I solved it with a map. You can also solve this problem recursively, also with a
 +map and a very neat way of building the copy. The recursive function returns a
 +copy of the node that was called with the following cases:
 +
 +  - If the node is null return null
 +  - If the node has been seen already, return the copy in the seen map
 +  - If none of the above, make a copy and add it to the seen
 +  - Then set the next pointer to a copy of the next node
 +  - Then set the randomon pointer to a copt of the random pointer
 +  - Return the copy
 +
 +**Algorithm Iterative:**
 +
 +<code psuedo [enable_line_numbers="true"]>
 +make a dummy head
 +make a curcopy pointer, cur original
 +while cur orignal isn't null
 +    curcopy next = new node with val of original
 +    add curcopy to a vector
 +    curcopy = curcopy next
 +    curorig = curorign next
 +           
 +second pass for random index:
 +walk the original list and keep a counter:
 +    int randpointer = cur random
 +    vector[counter]->rand = vector[rand]
 +    counter++
 +
 +return dummy head next
 +</code>
 +
 +**Code Iterative:**
 +
 +<code cpp [enable_line_numbers="true"]>
 +Node* copyRandomList(Node* head) {
 +  Node dh(0), *curOrig = head, *curCopy;
 +  curCopy = &dh;
 +
 +  // key is orig, val is the copy
 +  unordered_map<Node*, Node*> map;
 +
 +  // make a first pass copy
 +  while(curOrig != NULL){
 +    curCopy->next = new Node(curOrig->val);
 +
 +    // add it to the array
 +    map[curOrig] = curCopy->next;
 +
 +    // advanced our pointers
 +    curCopy = curCopy->next;
 +    curOrig = curOrig->next;            
 +  }
 +
 +  // second pass to copy the random pointers
 +  curOrig = head;
 +  while(curOrig){
 +    map[curOrig]->random = map[curOrig->random];
 +    curOrig = curOrig->next;
 +  }
 +
 +  return dh.next;
 +
 +}
 +</code>
 +
 +**Algorithm Recursive:**
 +
 +<code psuedo [enable_line_numbers="true"]>
 +maintain a visisted map key: original val: copy
 +
 +helper(node) return the copy
 +    if(null ) return null
 +    if( node is in visited )
 +        return the copy
 +    
 +    Node copy = new node with original's val
 +    Copy next = helperCopy(original's next)
 +    Copy rand = helperCopy(original's rand)
 +    
 +    add copy to the visited map
 +    return copy
 +</code>
 +
 +**Code Recursive:**
 +
 +<code cpp [enable_line_numbers="true"]>
 +class Solution {
 +  public:
 +    unordered_map<Node*, Node*> seen;
 +
 +    Node* helper(Node* orig){
 +      if(!orig){
 +        return NULL;
 +      }
 +
 +      if(seen.count(orig)){
 +        return seen[orig];
 +      }
 +
 +      Node* copy = new Node(orig->val);
 +
 +      // This is very important that we add it our seen list here, beause if not
 +      // we will hit infinite recursion with the random pointers
 +      seen[orig] = copy;
 +
 +      copy->next = helper(orig->next);
 +      copy->random = helper(orig->random);
 +
 +      return copy;
 +    }
 +
 +    Node* copyRandomList(Node* head) {
 +      return helper(head);
 +    }
 +};
 +</code>
 +===== Two Sum =====
 +
 +[[https://leetcode.com/problems/two-sum/|Leetcode 1]].
 +
 +**Given an array of integers nums and an integer target, return indices of the
 +two numbers such that they add up to target.**
 +
 +You can quickly do an ''O(n²)'' by checking every pair. You can do it quicker
 +with ''O(n)'' time and space by building a dictionary and looking for the
 +complement number. You have to keep in mind that you can't return the same
 +number!
 +
 +You can two pass it by building a dictionary, or do it better and simpler by
 +building the numbers as we go along and looking for the complement in the
 +previous numbers.
 +
 +**Algorithm:**
 +
 +<code psuedo [enable_line_numbers="true"]>
 +iterate over all the numbers with an index
 +  check if complement exists in the map
 +    return it if so
 +  add this number to the map
 +</code>
 +
 +**Code:**
 +
 +<code cpp [enable_line_numbers="true"]>
 +vector<int> twoSum(vector<int>& nums, int target) {
 +
 +  // key: number val val: index
 +  unordered_map<int,int> map;
 +
 +  for(int i = 0; i < nums.size(); i++){
 +    if(map.count(target-nums[i])){
 +      return {i, map[target-nums[i]]};
 +    }
 +    map[nums[i]] = i;    
 +  }
 +  return {};
 +}
 </code> </code>
  
  • algorithm_problems.1598807045.txt.gz
  • Last modified: 2020/08/30 17:04
  • by paul