LeetCode Progress as of 12/09/2019:
Leet Code by Problem Number
100 101 102 103 104 105 106 107 108 109
120 121 122 124 125 127 128 129
130 131 134 136 137 138 139 140
230 231 232 234 235 236 237 238 239
340 342 344 343 345 346 347 348 349
980 981 983 984 985 986 987 988
1180](https://github.com/kyeokabe/crackingCodingInterview/blob/master/code/LeetCode/1180_CountSubstringsWithOnlyOne%20DistinctLetter.cpp) 1183 1184 1189
1213 1214 1215 1217 1218 1219 1220
Leet Code by Problem Category (needs to be updated)
Unclassified
Combinations (Backtracking)
Backtracking
Binary Trees
94 98 100 101 102 103 104 105 106 107 108 109
Linked List
Two Pointers/Linked List
Two Pointers/Sliding Window
Two Pointers/Array
27 check 27 again
80 tricky...try 80 again
Binary Search (easy)
Binary Search (apply twice)
Vector/Map Lookup
Palindrome
Stacks
Stacks and Tricky Algo
In-Place Matrix Operation
Matrix Operation
Matrix Traversal
Recurrsion (basic)
Recurrsion (memoization i.e., top-down)
Recurrsion (Breadth First Search)
Find All Subsets
Array with Hashtables
Array using Element as Index
Array & Dynamic Programming
Array ... Sort and Process
Array ... Combinations
Bit Manipulation 89
Byte by Byte to Leet Code Mapping
01 Median of Arrays -> LC 4
02 0-1 Knapsack
03 Matrix Product
04 Find Duplicates
05 Consecutive Array
06 Zero Matrix ->LC 73
07 Square Submatrix
08 Merge K Arrays -> LC 23 (similar)
09 Matrix Search -> LC 74
10 Merge Arrays
11 Zero Sum Subarray
12 Permutations
13 N Stacks 14 Anagrams 15 Build Order 16 Shortest Path 17 Random Binary Tree
18 Lowest Common Ancestor -> LC 236
19 Sum 20 Reverse Stack
21 Tree to Doubly Linked List -> LC 426
22 Longest Consecutive Branch 23 Print Reversed Linked List 24 Balanced Binary Tree 25 Binary Search Tree Verification 26 Smallest Change **27 Inorder Traversal 28 Sort Stacks 29 Stacks from Queues 30 Palindromes 31 Max Stacks 32 Two Missing Numbers 33 Big Int Modules
34 Swap Variables -> a=a-b -> b=b+a -> a=b-a (done!)
35 Gray Code 36 Rotate Bits 37 Number of Ones In a Binary Number 38 Linked List Cycles 39 Random Linked List 40 Dedup Linked List 41 Split a Linked List 42 Nth to the Last Element
43 Three Sum -> LC 15
44 Tree Level Order -> LC 102
45 Autocomplete 46 String Deletion 47 Longest Common Substring 48 String Compression
49 Fibonacci Number -> LC 509
50 Priority Queue 51 Kth Most Frequent String
Cracking The Coding Interview
Ch 1 (Arrays and Strings)... 1 2 7 8
Ch 2 (Linked Lists)... 1 2 6 8 (incomplete)
Ch 3 (Stacks and Queues)... 2 (incomplete) 3 4
Ch 4 (Trees and Graphs)...
Ch 5 (Bit Manipulation)... 2 4 5 6 7
Ch 6 (Math and Logic Puzzles)... 1 2 3 4 6 9 10 (not really coding problems)
Ch 7 (Object-Oriented Design)...
Ch 8 (Recursion and Dynamic Programming)... 1 2 3 5 7 8 9
Ch 9 (System Design and Scalability)...
Ch 10 (Sorting and Searching)...
2/26/19 ...
6.1 (heavy pill) ... Idea problem hard to think of. Interesting solution.
6.2 (probability) ... Easy, not interesting. Think intuitively.
6.3 (dominos) ... "Proof" is based on intuition, but interesting thought.
6.4 (ants walk) ... Trivial problem.
6.9 (100 locks) ... Not easy. Figured out up to the importance of factors.
6.10 (poison) ... Good problem. Should be able to solve next time. Requires CS-like mindset.
2/28/19 ...
factorials.cpp ... simple recursion example (CS32 lec 8)
3/01/19 ...
pointerReview.cpp ... basics of pointers
array_element_sum.cpp ... simple recursion example (CS 32 lec 8)
3/02/19 ...
print_array_backwards.cpp ... simple recursion example (CS 32 lec 8)
3/03/19 ...
8.5 (recursive multiply) ... solved first time.
8.1 (Triple Steps) ... Wrong answer 1st tme, do again.
8.2 (Robot Grid) ... still has errors (incomplete!)
1.8 (Zero Matrix) ... Brute force complete. Optimized solution incomplete.
3/04/19 ...
1.7 (Rotate Matrix) ... Brute force complete. "In place" solution incomplete. ...-> completed "in place" solution on 3/12/19
3/05/19 ...
Reading Big O chapter. Stuck with Problem 8 which involves sorting knowledge. Need to do sorting first to understand. 8.11...attempted but too difficult. Try again later...
Sent MacBook out for repair.
3/06/19 ...
MacBook back from repair. Going over constructor/destructor notes (CS32 Lec 2.)
CS32 Lec 16 (intro to graphs). Come back to breadth-first later (need to review queues first.)
CS32 Lec 2 (contructors, destructors, class composition)
slide 30 is essentially what you need to know about constructor/destructor execution ordering!)
CS32 Lec 2 (slide 41 is essentially what you need to know about passing variables to classes w/ classes (initialization list)!)
3/07/19 ...
CS32 Lec 3 (pointers ... carrying over to next day)
the "this" pointer... slide 27
3/08/19 ...
CS32 Lec 3 (pointers ...completed)
copy constructors ... when a class has a pointer member variable, must create own copy constructor to prevent destructor from erasing memory when copied instance gets terminated.
dynamic variables ... new and delete command ... slide 37~.
slide 22 shows the two ways to use class methods (*ptr).func() or ptr->func()
3/09/19 ...
CS32 Lec 5 (stacks and queues ...skipped infix to post fix conversion algorithm, review psudo code for maze ...slide 23 & 35)
3/10/19 ...
CS32 Lec 14 (hash tables ... carrying over to next day)... went through "closed" hash tables. Should review insert (p.27) and search (p.30) implementation.
3/11/19 ...
CS32 Lec 14 (hash tables ... completed)... "open" hash tables, (regular) tables. Slide 66 important. continuing. map, vector not reviewed yet, but appeared.
3/12/19 ...
1.7 (Rotate Matrix) ... Completed previously skipped "in place" solution.
Fibonacci Series w memoization ... Simple recurssion problem using memoization. Good practice to grasp the concept.
3/13/19 ...
CS32 Lec 4 (Assignment Operators, Linked lists)
nullptr
8.9 (Parentheses) ... Very time consuming. Probably didn't solve it the way it was intended. Coming up with the binary representation was the trick. Alternative (more elegant) solutions wanted.
8.7 (Permutations without dups) ... Seemingly trivial problem. Shouldn't even be included in the recursion chapter.
3/14/19 ...
8.8 (Permutations with dups) ... Good review of math combinations (probability). Didn't use recursion.
8.3 (Magic Index) ... Not interesting. Why is this included as a problem?
5.5 (Debugger) ... all about knowing what (for example) 13 & 7 will do.
5.6 (Conversion) ... knowing "&" (same as 5.5) helps. Made a small mistake forgetting to implement overlap_digits function.
pointer arithmetic ... basic review
3/15/19 ...
6.6 (Blue-Eyed Island) ... c = 3 solution seems strange. (day 1 behaviour should change.) CS32 Lec 10 (Big O) ... Sorting section left for tomorrow
3/16/19 ...
no progress
3/17/19 ...
CS32 Lec 10 (Selection Sort, Insertion Sort, Bubble Sort) ... Skimmed through this as it doesn't seem that important. Skipped shell sort. These methods are typically too slow for real world sorts according to Carey. (Gayle says, Merge, Quick, & Bucket Sort are most common.)
16.1 Number Swapper ... good problem! Good to know in-place swapping is possible.
5.2 Binary To String ...Standard difficulty feeling problem. Good practice.
1/2 // returns 0
1/2.0 // returns 0.5
1.2 Check Permutation ... (int)char converts the char to the int ascii code (0~127).
char foo="a";
cout<<(int)foo<<endl; // prints 97
3/18/19 ...
1.1 Is Unique ... Similar to Q1.2. Have not solved second half (additional constraint of no additional data structure usage).
5.4 Next Number ... Relatively straight forward.
5.7 Pairwise Swap ... Made several small errors. More of a grit problem. Exponentials can be obtained by
#include <math.h>
int foo = pow(2,3);
3.2 Stack Min ... incomplete
a class type in the same class type seems unusual, but you can define a pointer to that class type.
3/19/19 ...
3.3 Stack of Plates ... More of a syntax problem rather than a thinking problem. Assumed a fixed maximum number of stacks.
16.10 Living People ... Think about how to reorganize the arrray for convenience. Not too hard, but made a few (trivial) errors.
3/20/19 ...
2.8 Loop Detection ... Solved first question for linked lists. Implementation took a long time. Interesting question. Kind of relies on whether you know the trick or not. Supposedly a classical question.
3/21/19 ...
3.4 Queue via Stacks ... Fairly basic as long as you know STL queue and stack syntax.
3/22/19 ... 2.1 Remove Dups ... Debugged error from yesterday. Good problem to learn how to use XCode debugger. Tough to do without a single error.
3/23/19 ...
3/24/19 ...
LC 94 Binary Tree In Order Traversal
LC 98 Validate Binary Search Tree
3/25/19 ...
LC 7 Reverse Integer ... taking care of details took way too long. Trick: process with long, evaluate if overflow at the end.
LC 69 Sqrt(x) ... Fairly easy.
3/26/19 ...
3/27/19 ...
LC 101 Symmetric Tree ... interesting problem. Should visit later to check I can solve it.
LC 104 Maximum Depth of Binary Tree
LC 74 Search A 2D Matrix ... most likely didn't solve as intended (slow)
3/28/19 ...
LC 701 Insert Into A Binary Search Tree
LC 669 Trim a Binary Search Tree
LC 700 Search In A Binary Search Tree
3/29/19 ...
LC 173 Binary Search Tree Iterator
3/30/19
LC 136 Single Number ... interesting problem. Sort of "need to know the trick prior" kind of problem.
3/31/19
LC 24 Swap Nodes in Pairs ... forgot to pass pointer by reference first time...
4/01/19
LC 200 Number Of Islands ... very good problem. Revisit and do again!
LC 160 Intersection Of Two Linked Lists
4/02/19
LC 637 Average Of Levels In Binary Tree ... interesting problem. Worth revisiting. My initial thought was to first traverse and get the depth, then traverse again and if the depth matched for each level, get the sum of vals, then take the average.
LC 144 Binary Tree Preorder Traversal
LC 513 Find Bottom Left Tree Value
LC 783 Minimum Distance Between BST Nodes
LC 199 Binary Tree Right Side View ... using "get depth" function seems to be useful for several Binary Tree problems! Also, passing references often times seems to be a convenient way of dealing with binary tree problems. This gives you a way to "communicate" between branches when using recurrsion.
LC 121 Best Time to Sell and Buy Stock
LC 1013 Partition Array Into Three Parts With Equal Sum ... there has got to be a cleaner way of doing this. Revisit if time permits.
04/03/2019
LC 198 House Robber ... Interesting problem! Good for practicing DP (dynamic programming). Revisit if time permits!
04/04/2019
LC 242 Valid Anagram ... Easy problem. No need to repeat.
LC 230 Kth Smallest Element In A BST
04/05/2019
04/06/2019
LC 217 Contains Duplicate ... Easy, but make sure C++ map syntax is understood! (insert, find, itorator, etc)
04/07/2019 no coding
04/08/2019
04/09/2019
LC 107 Binary Tree Level Order Traversal II
LC 201 Bitwise AND of Numbers Range
LC Best Time To Buy And Sell Stock II ... should have realized the trick without looking at the solution!
04/10/2019
LC 876 Middle of the Linked List
LC 693 Binary Number With Alternating Bits
LC 19 Remove Nth Node From End of List
LC 976 Largest Perimeter Triangle
LC 771 Jewels and Stones ... too easy. Do not revisit.
04/11/2019 struggled on the A/B soup devide problem (LC 808). Have recursion solution, but not fast enough to pass the test. Will update the code Sat or Sun with dynamic programming.
04/12/2019
04/13/2019
04/14/2019
04/15/2019
04/16/2019
LC 83 Remove Duplicates from Sorted List
04/17/2019
LC 1010 Pairs of Songs With Total Durations Divisible by 60
LC 328 Odd Even Linked List ... good problem. Come back later.
LC 237 Delete Node in a Linked List
04/18/2019
LC 82 Remove Duplicates From Sorted Linked List II
04/19/2019
LC 852 Peak Index In A Mountain Array
LC 114 Flatten Binary Tree to Linked List
04/20/2019
LC 387 First Unique Character In a String
04/21/2019
LC 821 Shortest Distance To A Character
LC 931 Minimum Falling Path Sum
04/22/2019
LC 349 Intersection of Two Arrays
LC 111 Minimum Depth Of Binary Tree
04/23/2019
LC 1008 Construct Binary Search Tree from Preorder Traversal
LC 1022 Sum of Root To Leaf Binary Numbers
04/24/2019
LC 1026 Maximum Difference Between Node and Ancestor
04/25/2019
LC 129 Sum Root to Leaf Numbers
04/26/2019
LC 442 Find All Duplicates In An Array
LC 589 N-ary Tree Preorder Traversal
LC 515 Find Largest Value in Each Tree Row
LC 109 Convert Sorted List to Binary Search Tree
LC 145 Binary Tree Post Order Traversal
04/27/2019
04/28/2019
LC 222 Count Complete Tree Nodes
04/29/2019
LC 670 Maximum Swap ... Revisit again later!
LC 1014 Best Sightseeing Pair ... technique when maximizing a value w multiple components (e.g., A(i)+i+A(j)-j), think if the components can be split up and calculated separately to simplify the problem. Revisit again later!
LC 409 Longest Palindrome ... technique
count(s.begin(),s.end(),c) //counts num of char c in string s
int odd=0;
for (int i=0;i<SIZE;i++)
odd += num[i]&1; // sums number of odd components
...Revisit again later!
syntax to convert int to string...
int foo=425;
string s=to_string(foo);
04/30/2019
LC 260 Single Number III ... techniques
int k=632;
k=k&(-k); //returns least common "1" bit which is 8.
int a=8;
int b=8+2;
if(a&b) //unintuitively, this line returns true if any "1" bit(s) of a and b are common.
cout<<"foo"<<endl; // foo will be outputted
LC 628 Maximum Product of Three Numbers
LC 492 Construct the Rectangle
LC 897 Increasing Order Search Tree
LC 747 Largest Number At Least Twice Of Others
05/01/2019
05/02/2019
05/03/2019
05/04/2019
LC 108 Convert Sorted Array To Binary Search Tree
LC 988 Smallest String Starting From Leaf
05/05/2019
LC 1038 Binary Search Tree to Greater Sum Tree
05/06/2019
LC 1019 Next Greater Node in Linked List
LC 503 Next Greater Element II
LC 674 Longest Continuous Increasing Subsequence
LC 559 Maximum Depth Of N-ary Tree
05/07/2019
LC 553 Optimal Division ... not necessarily a good problem.
05/08/2019
LC 508 Most Frequent Subtree Sum ... Very good problem. Unusual type of binary tree question. Learned three things. i) "unordered_map" can be used just like "map", and on average has faster access time (O(1) unordered_map vs O(log(n)) for map). Worst case is slower (O(n) vs O(log(n)). ii) map values are initialized to 0, so you can just ++ without explicit initializing. iii) iterate over map keys
//sample code for map key iterations
unordered_map<int,int> m;
//...some key to value assignments...
m[2]++; // key 2 is assigned to val 1
for(auto it=m.begin();it!=m.end();it++){
if(it->second==foo)
//etc...
}
LC 572 Subtree Of Another Subtree ... for some reason, took 3 tries to get it right. Shouldn't be that hard. Try again later. (Part of the problem was trying to fit branch cases into cases that wouldn't work too well...)
LC 525 Contiguous Array ... Unintuitive catch (or trick) used in the solution. Revisit again.
05/09/2019
LC 873 Length of Longest Fibonacci Subsequence
LC 539 Minimum Time Difference
05/10/2019
LC 5 Longest Palindromic Substring
LC 501 Find Mode in Binary Search Tree
05/11/2019
LC 590 N-ary Tree Postorder Traversal
LC 530 Minimum Absolute Difference
LC 538 Convert BST to Greater Tree
05/12/2019
LC 551 Student Attendance Record
05/13/2019
LC 1041 Robot Bounded In Circle
LC 543 Diameter of Binary Tree
LC 103 Binary Tree Zigzag Level Order Traversal
LC 102 Binary Tree Level Order Traversal
LC 105 Construct Binary Tree from Preorder Traversal ... Good problem. There should be a more simple way to code this. Come back later if time permits...
05/14/2019
LC 106 Construct Binary Tree from Inorder and Postorder Traversal
LC 977 Squares of a Sorted Array
05/15/2019
ugly but useful custom sorting lambda syntax
sort(s.begin(),s.end(),[](string &s1, const string &s2){return s1+s2>s2+s1;});
//Given {"3","30","9"}, will return {"9","3","30"}.
LC 599 Minimum Index Sum of Two Lists
05/16/2019
LC 350 Intersection of Two Arrays II
05/17/2019
05/18/2019
LC 232 Implement Queue Using Stacks
LC 225 Implement Stack Using Queues
LC 1005 Minimum Sum Of Array After K Negations
TO DO Read bit manipulation summary
https://leetcode.com/problems/sum-of-two-integers/discuss/84278/A-summary%3A-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently
LC 338 Counting Bits ... Naiive solution is easy. Almost impossible to come up with/realize optimized solution...
LC 167 Two Sum II - Input Array is Sorted
//This question uses binary search. Make sure to review and be able to implement it.
05/19/2019
LC 1047 Remove All Adjacent Duplicates In String
LC 153 Find Minimum In Rotated Sorted Array
5/20~5/24 sick + SRC review meeting
05/25/2019
05/29/2019
LC 1052 Grumpy Bookstore Owner ... Good problem to get a feel of how the "sliding window" technique works. Worth revisiting if time permits.
LC 75 Sort Colors ... Not the solution Leetcode wants, but passes test. Could come back for alternative solution, but low priority.
06/04/2019
LC 496 Next Greater Element I ... previously solved with O(nxn). This solution is O(n).
LC 556 Next Greater Element III ...
need to know
vector<int> v;
while(!s.empty()){
v.push_back(s.top());
s.pop();
}
next_permutation(v.begin(), v.end());
06/05/2019
LC 70 Climbing Stairs ... Revisited. Uses simple dynamic programming
06/07/2019
LC 958 Check Completeness of a Binary Tree
LC 973 K Closest Points to Origin sort lambda syntax
sort(points.begin(),points.end(),[](vector<int> &p,vector<int> &q){return p[0]*p[0]+p[1]*p[1]<q[0]*q[0]+q[1]*q[1];});
LC 15 3 Sum ... not easy
LC 984 String without AAA or BBB
06/10/2019
LC 137 Single Number II ... Solved in O(n) time and O(n) memory, but apparently there is a better solution using O(n) time & O(1) memory.
06/11/2019
08/19/2019
LC 260 Single Number III (revisit)
LC 27 Remove Element (revisit)
08/20/2019
08/21/2019
08/22/2019
08/23/2019
LC 3 Longest Substring Without Repeating Characters
LC 153 Find Minimum in Rotated Sorted Array revisit ... This time using binary search! O[log(n)]
08/24/2019
LC 80 Remove Duplicates from Sorted Array II
LC 287 Find the Duplicate Number ... binary search excersize
08/26/2019
LC Max Consecutive Ones III ... probably relatively standard "sliding window" problem. Tricky to get everything correct the first time. Trick: add 0s to an array for convenience of edge cases.
08/30/2019
LC 278 First Bad Version ... Basic Binary Search Problem
08/31/2019
LC 240 Search a 2D Matrix ... once you know the trick it is easy. Overthough about using binary sort...
09/02/2019
LC 209 Minimum Size Subarray Sum ... standard "sliding window" problem. Writing out an example on a sheet of paper and going through what happens step by step is a good way to verify algorithm edge cases.
09/03/2019
LC 904 Fruit Into Baskets ...Another "sliding window" problem. Used two queues to solve this particular problem. Probably standard (= medium) difficulty.
09/04/2019
LC 284 Game of Life ... trick for inplace processing is to make your own encoding scheme.
LC 1176 Diet Plan Performance ... Very basic form of "sliding window" problem.
09/05/2019
LC 238 Product of Array Except Self ...Felt like this is the type of problem whether you either know how to solve or have no idea. Trick is to realize product of all elements except self can be broken down to product of everything to the left times product of everything to the right. Further more, memory can be reduced from O(n) to O(1) by storing one of the arrays above as the answer and computing the other "array" on the fly and only storing the most recent result as an integer.
09/06/2019
LC 498 Diagonal Traverse ... not too difficult to find the "pattern", but need to be careful about "edge cases" (= r=1 or c=1 input).
LC 643 Maximum Average Subarray I ... easy "two pointer" problem.
09/08/2019
LC 470 Implement Rand10() using Rand7()
09/09/2019
LC 429 N-ary Tree Level Order Traversal ... simple algorithm tree problem. Good refresher for basic tree class syntax.
09/10/2019
LC 307 Range Sum Query ... not sure why it is medium difficulty
LC 229 Majority Element II ... interesting problem. Had to check discussion board to understand solution. Worth revisiting.
LC 219 Contains Duplicate ... easy problem that uses unordered map
09/11/2019
LC 152 Maximum Product Subarray ... Very tricky subarray problem. Probably could not solve again without looking at solution.
LC 235 Lowest Common Ancestor Of A Binary Search Tree ... Easy to solve if you can think which direction to search relative to roo->val, p->val, and q->val relationship.
LC 236 Lowest Common Ancestor Of A Binary Tree ... Solved it using same idea as LC 235. However, there is probably a more efficient way of doing this.
09/12/2019
Read this post about dynamic programming!
LC 509 Fibonacci Number revisiting ...
Very good session reviewing difference between dynamic programming and memoization. Both techniques are about avoiding duplicate computation. Dynamic programming is when the code is framed to solve bottom up which is typically iterative whereas memoization is when the code is framed to solve top to bottom which is typically recursive.
Wrote this post about dynamic programming & memoization
09/13/2019
LC 193 House Robber revisited ... Solved using the 5 step process including 1. Get recursive relation 2. Solve recursively (top-down) 3. Solve recursively (top-down) with memoization 4. Solve iteratively (bottom-up) with dynamic programming 5. Solve iteratively (bottom-up) with constant space
09/14/2019
LC 337 House Robber III ... Still need to try iterative solution!
09/14/2019
LC 1189 Maximum Number of Balloons
LC 1191 K-Concatenation Maximum Sum
LC 1161 Maximum Level Sum of a Binary Tree
09/15/2019
LC 84 Largest Rectangle in Histogram ... Very difficult! Try again. Type of problem where you maintain maximum area using a stack.
09/17/2019
LC 67 Add Binary ... revisited
LC 951 Flip Equivalent Binary Trees ... Pretty easy.
09/18/2019
LC 983 Minimum Cost for Tickets ... Fortunately was able to solve it within ~45 min or so, but not that easy. First submission was with just recursion. Second submission was with +DP modification.
LC 985 Sum of Even Numbers After Queries ... missed negative odd mod even pos results. e.g., -3%2->-1 (not 1)
LC 993 Cousins in Binary Tree ... Relatively simple binary tree problem.
09/19/2019
LC 987 Vertical Order Tracersal of a Binary Tree ... not algorighmically hard, but was annoying to get it right.
LC 1072 Flip Columns For Maximum Numbers Of Equal Rows ... learned that unordered_map does not have pre defined operator to use vector as keys but map does.
09/20/2019
LC 3 Longest Substring Without Repeating Characters ... Revisited. This time, solved with "two pointers" making time complexity O(n) rather than O(n^2)
09/23/2019
revisited LC 973 K Closest Points to Origin ... lambda sort syntax is tricky!
LC 953 Verifying An Alien Dictionary
09/24/2019
LC 863 All Nodes Distance K in Binary Tree ... Good question. New concept: 1. Use maps to move from child to parent node. 2. Use queue for breadth first search, stacks for deoth first search.
09/25/2019
LC 253 Meeting Rooms II ... The tricky part is to realize that this problem can be easily solved by sorting based on starting times. Note that to sort based on the first element, this is all you need to do.
vector<vector<int> v; //v=[[30,40],[50,60],[20,30]]
sort(v.begin(),v.end()); //v=[[20,30],[30,40],[50,60]]
LC 252 Meeting Rooms ... Eassier version of meeting rooms II, but the basic idea (i.e., trick) is the same.
LC 41 First Missing Positive ... Was able to come up with the trick. The trick is to use the elements as indicies and keep hopping to the corresponding element while it is a valid range and mark it (=INT_MIN) as existing. i.e., n_i = INT_MIN means that i was a positive integer in the array.
LC 53 Maximum Subarray ... Watched youtube channel "Back To Back SWE" to get the answer.
09/26/2019
09/27/2019
LC 380 Insert Delete GetRandom O(1) ... Great problem. The trick for O(1) return is to use rand()%size on an array. The problem is how to delete an element in an array. The trick is to fill a particular element with the last number of the array and pop_back the array.
LC 11 Container With Most Water ... Not too difficult if you can realize it can be solved using the "two pointer sliding window" technique.
LC 6 ZigZag Conversion ... Algorithm was not too hard but encountered a few bugs before getting it correct.
09/31/2019
LC 1207 Unique Number of Occurrences ... Easy problem. No real tricks.
LC 1208 Get Equal Substrings Within Budget ... Basically standard sliding window problem, but struggled much more than I should due to overthinking ptr1 termination conditions.
LC 39 Combination Sum ... Got the answer correct the first time but a bit tricky. May not be able to solve on an off day.
LC 40 Combination Sum II ... My solution seems a bit messy. Probably room to improve.
LC 55 Jump Game ... trick 1: You only need to think about where the 0s are, and what precedes them. trick 2: If the final index is 0, it doesn't matter whether it is jumpable or not because you will land on it if everything before is jumpable.
10/01/2019
LC 300 Longest Increasing Subsequence
LC 34 Find First and Last Position of Element In Sorted Array ... Trick was to use binary search twice to individually search for first and last element. My prefernece for implementing binary search is to alway use mid=(right-left)/2+left and update left, right index recurrsion with either (mid,right) or (left, mid). Deal with base case of righ-left<=1 to avoid getting stuck in a loop.
LC 150 Evaluate Reverse Polish Notation ... Very easy question using one stack. Do not bother to revisit.
LC 742 Closest Leaf in a Binary Tree ... Similar to problem LC 863 All Nodes Distance K in Binary Tree
10/02/2019
LC 127 Word Ladder ... Surprisingly got the basic idea pretty quickly. However, took time debugging details. A good idea I had was to use the competitive programming technique to delete an element in wordList. The basic idea is to replace wordList[j] with wordList[wordList.size()-1]. However, if j!=wordList.size()-1, j-- is necessary so the next iteration will consider whether the new entry needs to be evaluated.
10/03/2019
LC 33 Search in Rotated Array ... Trick is to apply binary search twice. The first search is for finding the pivot point. Similar to LC 34 Find First and Last Position of Element In Sorted Array.
LC 28 Implement strStr() ... Basic array string problem.
LC 933 Number of Recent Calls ... API not clear.
10/04/2019
LC 121 Best Time to Buy and Sell Stock revisited ... Trick is to think from back of the array and store the max selling price. Compare with current price and if gains are greater, store as temperary answer.
LC 346 Moving Average from Data Stream ... Easy problem...
LC 426 Convert Binary Search Tree to Sorted Doubly Linked List ... Tricky problem! Should realize that basic function should resemble in-order processing format due to linked list vs tree node relationships. Trick 1: In-order code structure. Trick 2: Private Node* tempvariable. Trick 3:
Node* dummy = new Node(0,nullptr,nullptr);
temp=dummy;
10/05/2019
LC 1217 Play with Chips ... Relatively easy problem. Got it correct first try in 10 min or so.
LC 1220 Count Vowels Permutation ... Did not find too difficult despite it being a hard problem.
10/07/2019
LC 1214 Two Sum BSTs ... Easy standard question traversing BST and storing vals in HashTables.
LC 1213 Intersection of Three Sorted Arrays ... Easy "three pointers" problem.
LC 1219 Path with Maximum Gold ... Very important problem. Great excersize for depth first search. The tricky part of this problem is to think of how we can search a grid showing places we have already visited just by passing the grid by reference (so we can save memory). The basic idea is
//store grid value
int temp=grid[r][c];
//mark grid as visited
grid[r][c]=0;
//recursively visit other grids
help(grid, r+1,c, etc.)
help(... etc)
//unmark grid
grid[r][c]=temp;
Since only valid grid positions can be marked as visited and after the recursion function the unmark is always called, there is no worry for the algorithm to forget to "unmark" a grid. Worth visiting later again.
LC 22 Generate Parentheses ... Used idea shown above (LC 1219) for saving memory. Backtracking/combinations problem.
LC 99 Recover Binary Search Tree ... Had to look at discussions to get a hint for how to solve the problem. The idea is that in-order traversal for BST gives sorted order. This idea has appeared previously in one of the questions. Should get it right next time.
10/08/2019
read union find algorighm
reviewed min/max heaps
LC 414 Third Maximum Number ... Fairly straight forward.
[Pramp Array Quadruplet] preparation
10/09/2019
LC 18 4Sum ...Found it fairly straight forward.
LC 413 Arithmetic Slices ... Seemed to use similar technique to one of the Back to Back SWE youtube videos I watched previously. Wrote two answers (one with O(n) time, O(1) memory, the other with O(n) time, O(n) memory.)
10/10/2019
LC 94 Binary Tree Inorder Traveral ... Added iterative solution which was not trivial. Uses a stack.
LC 478 Generat Random Point in a Circle ... Sample rejection method was my original thought but it timed out. Using polar coordintates was the first trick. Second trick was
double(double(rand())/RAND_MAX)
which will give you a uniform float distribution between 0 and 1. Third trick was to sqrt the radius to make the distribution uniform.
10/11/2019
LC 653 Two Sum IV - Input is a BST ... Easy problem.
Added new solution to LC 253 Meeting Rooms II
//priority queues are max heap by default.
//to make them a min heap, use
priority_queue<int,vector<int>, greater<int>> q;
//also note that despite the name "queue" use
//q.top() rather than q.front()
LC 215 Kth Largest Element in an Array ... Good practice to make sure you know min heap priority queue implementation.
LC 703 Kth Largetst Element in a Stream ... Very similar to LC 215 (problem above).
10/12/2019
LC 208 Implement Trie (Prefix Tree) ... Easy problem.
LC 1196 How Many Apples Can You Put into a Baskit ... Easy problem.
LC 402 Remove K Digits ... Tricky to get bug free answer within 40 min or so. Do again for practice.
LC 1222 Queens That Can Attack the King ... Not hard except for a small trick of thinking from the king's standpoint rather than iterating through all queens.
LC 1221 Split a String in Balanced Strings ... Fairly easy problem.
10/13/2019
LC 340 Longest Substring with At Most K Distinct Characters ... Standard "sliding window" problem.
LC 32 Longest Valid Parentheses ... Hard problem. Needed to check discussions to get the answer. The basic idea is to break the problem into two phases. Phase 1: Find indices of invalid parentheses and mark in a new vector. Phase 2: Count longest contegious valid vector length.
10/14/2019
LC 16 3Sum Closest ... Sliding window problem. Not hard if you can realize this can be solved by a sort -> sliding window combination.
LC 14 Longest Common Prefix ... Easy problem.
LC 1119 Remove Vowels From A String ... Very easy problem.
LC 345 Reverse Vowels in a String ... Standard two pointers problem.
LC 62 Unique Paths ... Added new solution. Should review permutation equations. Be careful of overflow issues. Unsigned long long doesn't seem to do division correctly when numbers are large?
10/15/2019
LC 270 Closest Binary Search Tree Value ... Simple tree traversal problem.
LC 63 Unique Paths II ... Recurrsion Breadth First Search (BFS) problem. In hind sight, it would have been better to build the BFS from start to finish rather than finish to start to avoid int overflows at mid points (actually this could happen either way...test case is not "fair"). Do not forget to add coordinate to Q for BFS even if that coordinate itself is blocked (==1).
LC 980 Unique Paths III ... Despite being categorized as a "hard" problem, it uses standard DFS and backtracking techniques. Build a recursive function, if adjacent position is unvisited empty path or the goal, mark current position visited and dive into the recurring position. Unmark the current position after diving out of the function.
10/16/2019
LC 221 Maximal Square ... Interesting question. Had to see discussion to realize the question was asking for squares, not rectangles. Review again in the future.
LC 293 Flip Game ... Easy problem.
LC 17 Letter Combinations of A Phone Number ... Backtracking practice problem. Do not forget to increment iterators if using a while condition (I tend to do this)!
LC 170 Two Sum III ... Easy problem.
LC 288 Unique Word Abbreviation ... Unclear problem description. Don't bother to do again.
LC 79 Word Search ... Standard backtracking problem.
10/17/2019
LC 1086 High Five ... When you get a problem that wants "top 5 highest (or lowest)" think priority queue.
LC 849 Maximize Distance to Closest Person ... Easy problem, but could have done in 1 pass constant memory.
LC 298 Binary Tree Longest Consecutive Sequence ... Not too difficult.
LC 622 Design Circular Queue ... First time using lists (typically implemented as doubly linked lists). Lists guarantee constant insert and delete anywhere within the chain. However, access to a particular element is not constant time. For instance, if you don't have an iterator to begin with, accessing to the middle of the lists requires traversing fron the beginning or end of the list (which is linear time).
LC 641 Design Circular Dequeue ... Very similar to previous question (LC 622). Easy if you use C++ lists. Note that back is typically used to access the back when not using iterators while end tends to get used for accessing the "end" when using iterators.
LC 633 Sum of Square Numbers ... Fairly easy. Solved is as a "two sum" problem.
10/18/2019
LC 246 Strobogrammatic Number ... Fairly easy problem.
LC 247 Strobogrammatic Number II ... Good backtracking practice problem.
LC 706 Design HashMap ... Pretty easy.
LC 281 Zigzag Iterator ... If you are allowed to use private variables (and copy v1 & v2) not sure what the intent of the problem is. Is it possible to solve without private variables...?
10/19/2019
LC 1228 Missing Number In Arithmetic Progression
LC 1230 Toss Strange Coins ... Very difficult but good DP practice.
LC 1233 Remove Sub-Folders from the Filesystem
LC 1232 Check if it is a Straight Line
10/20/2019
LC 1234 Replace the Substring for Balanced String ... When doing sliding window problem, consider adding second while loop at the back covering ptrR==end but ptrL need to slide more cases.
LC 416 Partition Equal Subset Sum ... Though of good solution.
LC 487 Max Consecutive Ones II ... Soved non-two pointer way.
10/21/2019
LC 486 Predict The Winner ... Very good question testing minimax algo & DP.
LC 54 Spiral Matrix ... Fairly easy, but hard if there is an O(1) memory constraint. Can you do with O(1) memory?
LC 46 Permutations ... Two solutions. Excellent backtracking practice problem. Note that STL provides
next_permutation(v.begin(),v.end())
10/22/2019
LC 523 Continusous Subarray Sum .. Took 8 total trials to get it correct (record worse). Edge cases are rediculous to keep track of. Not a reasonable interview question.
LC 494 Target Sum ... Solved without using DP. Try again using DP. ...-> Added DP solution. Very hard to do without seeing the solution. Do again.
10/23/2019
LC 146 LRU Cache ... Difficult problem, but good excersize. Is there a way to solve this without two hashmaps and two lists? Do again later.
LC 138 Copy List with Random Pointer ... Interesting question. If you can come up with using an unordered_map<Node*,Node*> to map original to copy, the basic idea is not too hard.
LC 276 Paint Fence ... Elusive problem. Not sure if I fully understand what I did. Review again later.
LC 256 Paint House ... Had a tough time solving DP a few weeks ago, but this time solved the problem almost immediately.
LC 265 Paint House II ... Similar to Paint House I. Still not have solved with O(nk). Review again.
LC 1165 Single-Row Keyboard ... Easy problem.
10/24/2019
very good state machine discussion
LC 309 Best Time To Buy And Sell Stock With Cooldown ... Great problem to introduce the idea of state machines. Pay attention to difference between state and actions.
10/25/2019
LC 1143 Longest Common Subsequence ... Not trivial at all! Had to check the solution. Do again.
LC 347 Top K Frequent Elements ... Interesting idea where you can allocate O(n) memory to "sort" in O(n) time!
[supposedly similar problems] 1092. Shortest Common Supersequence 1062. Longest Repeating Substring 516. Longest Palindromic Subsequence
10/27/2019
LC 89 Gray Code ... Should know what Gray code is. Note that the conversion from binary to Gray is
B->G
G=B^(B>>1)
LC 1238 Circular Permutation in Binary Representation ... This is another Gray Code problem, but with a bit more twist. Make Binary to Gray hash table. Push back the binary number correspondint to the gray code which maches the start in binary. Keep pushing back the binary+1%(1<<n) transformations.
LC 1236 Web Crawler ... Not too interesting.
10/28/2019
LC 1093 Statistics From A Large Sample
LC 858 Mirror Reflection ... Interesting problem. Did not think in the "simple answer" direction.
LC 991 Broken Calculator ... The non-BFS solution is not intuitive to come up with, but a good takeaway is to consider solving the given problem "backwards" (i.e., B->A rather than A->B).
LC 978 Longest Turbulent Subarray ... Seen similar type of problem before. I think it was covere by the Back to Back SWE Youtube channel.
10/29/2019
LC 1055 Shortest Way To Form String ... Can't fully explain why greedy works here.
LC 1133 Largest Unique Number ... Easy. When element range is limited, sometime creating a vector with size matching the element range is a good technique.
LC 331 Verify Preorder Serialization Of A Binary Tree ... Did not come up with the idea of keeping track of "the number of pointers" while scanning through the string.
10/30/2019
LC 373 Find K Pairs with Smallest Sum ... Not easy. The idea is to realize this can be thought (somewhat) similar to search a semi-sorted 2D matrix problem. Similar to LC 74
Finally came back to K-Messed Array. Takeaway: Think if priority queues can be used if a question wants only k numbers of max/min or only if k out of n items need to be sorted.
LC 1239 Maximum Length of a Concatenated String with Unique Characters ... Not easy. Trick 1: Words with unique chatacters can be checked by mapping a->2^0,b->2^1...z->2^26. Trick 2: Split one long combinatorial for loop into two for loops.
LC 1002 Find Common Characters ... Easy question.
10/31/2019
LC 187 Repeated DNA Sequences ... Easy problem. Could encode 10 char sequence to single int. A->0,B->1,C->2,D->3, then bitshift 2x position and sum up.
LC 998 Maximum Binary Tree II ... Fairly easy.
LC 562 Longest Line of Consecutive Ones .. Traversing matricies diagonally was not as easy as I thought. Key is to split it into two separate for loops. Start from row 0M.size()-1, then start from col 1M[0].size()-1 etc.
LC 861 Score After Flipping Matrix ... Prety easy greedy problem.
11/01/2019
LC 836 Rectangle Overlap ... Think about 1D overlapping case and expand idea to 2D.
LC 159 Longest Substring With At Most Two Distinct Characters ... Not too difficult sliding window problem.
Sliding window template discussion
11/02/2019
LC 348 Design Tic-Tac-Toe ... Have not implemented O(1) solution yet.
LC 1243 Array Transformation ... Easy.
LC 1244 Design A Leaderboard ... Wasn't too hard. Vector + hashtable combination.
11/04/2019
LC 216 Combination Sum III ... Relatively straight forward backtracking problem.
LC 134 Gas Station ... Tricky to get O(n) solution.
LC 1007 Minimum Domino Rotations For Equal Row ... Fairly easy.
LC 277 Find The Celebrity ... Straight forward logic.
LC 419 Battleships In A Board ... Similar to Number of Islands problem, but additional constraints allows to solve with O(1) memory without modifying array. Count number of "top" pieces of battleship ('.' on top & '.' to the left or 'X' is on top or left most row.)
11/05/2019
LC 735 Asteroid Collision ... Idea is simple. Edge cases are messy.
LC 605 Can Place Flowers ... Easy.
LC 981 Time Based Key-Value Store ... Imporant question. Learded upper_bound and prev.
//assume m[1]=7,m[4]=8,m[6]=13;
//learned auto it=m.upper_bound(5);
//it points to m[6]
//learded auto it2 = prev(it);
LC 1247 Minimum Swaps to Make Strings Equal ... Easy once you see the pattern.
LC 1151 Minimum Swaps To Group All 1s Together ... Took ~25 min to realize this was a sliding window problem.
LC 1200 Minimum Absolute Difference ... Sort and choose.
11/06/2019
LC 895 Maximum Frequency Stack ... Took several hoursto get the first answer today... Idea is simple but managing data structure needs caution.
11/07/2019
LC 295 Find Median From Data Stream ... Slow day again. Learned that for multisets when an existing number gets added, it is added behind the pre-existing duplicate number (at least for C++ 11). This guarantee is what makes this algo work.
11/08/2019
LC 151 Reverse Words In A String
LC 223 Rectangle Area ... Watch out for overflow.
LC 433 Minimum Genetic Mutation ... Remember that for unordered_map the order of the elements is not guaranteed to be the same after you erase elements
LC 1183 Maximum Number of Ones ... Interesting question. Besides coming up with the general idea, indexing the submatricies based on correct r,c MOD is the trickiest part.
LC 716 Max Stack ... Similar to LRU cache problem, but a bit simpler. Regardings lists, auto it = prev(lst.end()) is how to get the iterator of the last actual element in the list. lst.end() does not point to an actual element.
LC 545 Boundary of Binary Tree ... Idea is to traverse the tree three times. Watch for edge cases.
11/09/2019
LC 557 Reverse Words In A String III
LC 370 Range Addition ... Farily easy to recognize trick.
11/11/2019
LC 1103 Distribute Candies To People
LC 746 Min Cost Climbing Stairs
LC 931 Minimum Falling Path Sum revisited
LC 1155 Number of Dice Rolls With Target Sum
LC 303 Range Sum Query - Immutable
LC 325 Maximum Size Subarray Sum Equals K
11/12/2019
LC 740 Delete and Earn ... Great question. Can reframe it to become a houserobber probelm. Review again!
LC 937 Reorder Data In Log Files
LC 322 Coin Change .. Solved using a breadth first search approach. REDO w/ DP!
11/13/2019
LC 72 Edit Distance ... HARD dinamic programming question. Review again! Setting up DP(i,j) with 0 inclusive i non-inclusive is tricky.
LC 1087 Brace Expansion ... Forgot to push back "" to vector in one of the first lines. (For loop didn't work without a vector element entry.)
LC 784 Minimum Distance Between BST Nodes ... Fairly easy.
11/14/2019
LC 1035 Uncrossed Lines ... Was able to come up with my own solution inspired by a previous question (LC 373) designed by Stefan Pochmann. The basic idea started out by making an mxn matrix, with 1s where A_i==B_j. At any (i,j) the question basically becomes how can you get the most ones travelling only down or right.
LC 1122 Relative Sort Array ... Fairly straight forward.
11/15/2019
LC 734 Sentence Similarity ... Easy but had dumb bugs.
LC 329 Longest Increasing Path In A Matrix ... Surprisingly didn't find it hard despite it being classified as a "hard" problem. Use a supplementary matrix to store longest path of each traversed cell. Also refer to LC 1035 Uncrossed Lines
11/16/2019
LC 712 Minimum ASCII Delete Sum for Two Strings ... Have encountered several problems where building a 2D matrix and finding the longest common subsequence helps solve the problem.
LC 583 Delete Operation for Two Strings ... Essentially the same as the previous question (LC 712 Minimum ASCII Delete Sum for Two Strings). The basic idea is to find the length of the longest common subsequence.
11/17/2019
LC 561 Array Partition I ... Easy.
11/18/2019
LC 171 Excel Sheet Column Number
LC 1099 Two Sum Less Than K ... Special sliding window where the pointers begin at the two ends and move inwards.
LC 655 Print Binary Tree ... A bit messy but solved.
LC 250 Count Univalue Subtrees ... Review if there is a more elegant solution.
LC 705 Design Hash Set ... Super easy.
11/19/2019
LC 797 All Paths From Source To Target
LC 1066 Campus Bikes II ... Solution ended up being "brute force" backtracking with minor pruning condition added. Changing the helper function fom passing a regular variable to passing by reference made it from time limit exceeded (TLE) to accepted (AC)!
11/20/2019
LC 124 Binary Tree Maximum Path ... Very tricky problem because what you "check" within the helper function to determine the answer is different from what you return using the helper function. Unique problem.
LC 31 Next Permutation ... Missed key insight that once you swap the two elements, the "back" of the array can just be reversed rather than re-sorted.
LC 71 Simplify Path ... Refer to recap in source code for basic idea. Kind of annoing problem.
11/21/2019
LC 986 Interval List Intersections ... Key insight is to realize if (A.start<=B.end && B.start<=A.end) condition.
LC 767 Reorganize String ... Thought of solving it by first writing out sequence with adjacent chars aaaaabbbc, then split it into two strings aaaaa & bbbc, then merge them together abababaca.
LC 824 Goat Latin ... Easy but annoying problem.
11/22/2019
LC 139 Word Break ... Good trick: Search from the back
LC 90 Subsets II ... Added termination condition which reduced time from TLE to AC.
LC 320 Generalized Abbreviation
11/25/2019
LC 1265 Linked List In Reverse ... Very easy.
LC 1259 Handshakes That Don't Cross
11/26/2019
LC 695 Maximum Area of Island ... Easy problem.
LC 1198 Find Smallest Common Element In All Rows
LC 1128 Number Of Equivalent Domino Pairs ... Confusing problem description.
11/27/2019
LC 1120 Maximum Average Subtree ... Was a bit tricky to figure out how to keep track of multiple variables. Using maps with pointers as keys is sometimes a helpful way of solving tree questions.
11/29/2019
LC 1274 Number Of Ships In A Rectangle ... Relatively straight forward. Apply binary search twice.
12/01/2019
12/02/2019
LC Count Substrings With Only One Distinct Letter ... Easy
12/03/2019
LC 922 Sort Array By Parity II ... Tricky to figure out how to do in place one pass. Review again.
12/04/2019
LC 1162 As Far From Land As Possible ... Took forever to realize bug. When using queues (like for BFS), do not use for loops with i<q.size() and pop within the for loop. Use while (!q.empty()){} instead!
LC 1160 Find Words That Can Be Formed By Characters
LC 1137 Nth Tribonacci Number ... Straight forward.
12/05/2019
LC 1273 Delete Tree Nodes ... There is probably a way to solve this with fewer lines. Did a lot of "data shuffling". Made mistake on pop size when shuffling data (watch out for when parent = -1).
LC 1121 Divide Array Into Increasing Sequences ... Should be rated as a medium difficulty problem rather than hard. Key insight is to realize the bottleneck is what the count of the most occuring number is. The minimum length of increasing arrays will be limited by that.
12/06/2019
LC 921 Minimum Add To Make Parentheses Valid ... Easy
12/08/2019
LC 1281 Subtract The Product And Sum Of Digits Of An Integer ... Easy problem.
LC 1282 Group The People Given The Group Size They Belong To ... Took a few minutes to get the idea of how to structure the program.
LC 1283 Find The Smallest Divisor Given A Threshold ... A relatively standard binary search problem.
12/09/2019
LC 1284 Minimum Number Of Flips To Convert Binary Matrix To Zero Matrix ... Trick is to start from 0 matrix and do BFS.
LC 60 Permutation Sequence ... Redo again without using next_permutation function in CPP.
LC 723 Candy Crush ... Brute force problem.
LC 130 Surround Regions ... Similar to islands problem. Solved by depth first search.
12/10/2019
LC 868 Binary Gap ... Relatively easy problem.
LC 403 Frog Jump ... Solved using BFS with hashmaps. Used regular map for vector storage. Other than that, maybe there is a way to improve efficiency...?
LC 731 My Calendar II ... Had to look at the solutions for simple answer.
LC 729 My Calendar I ... Refer to My Calendar II for simple solution.
LC 732 My Calendar III ... Similar to other my calendar problems.
12/11/2019
LC 853 Car Fleet ... Sort, then calculate the time for arrival.
LC 186 Reverse Words In A String ... Array manipulation problem.
12/12/2019
LC 243 Shortest Word Distance ... Relatively straight forward. Watch out for duplicate words.
LC 244 Shortest Word Distance II ... Similar to Shortest Word Distance I.
LC 245 Shortest Word Distance III ... Similar to Shortest Word Distance I. Branch cases if word1==word2.
LC 1184 Distance Between Bus Stops
12/13/2019
LC 892 Surface Area Of 3D Shapes ... A bit tricky. Think of how to subtract overlapping areas.
12/14/2019
LC 1288 Remove Covered Interval ... Had a complicated idea using hashmaps and a stack like vector. Referred to Lee215's idea to solve. Note the special treatment for sort is neccessary.
LC 762 Prime Number Of Set Bits In Binary Representation
LC 846 HandOf Straights ... Hashmap and hustle.
LC 885 Spiral Matrix III ... Used more memory than necessary. Review again.
12/17/2019
LC 1033 Moving Stones Until Consecutive...Easy.
/12/19/2019
Reviweing interval problems... When dealing with interval problems, there is a guranteed overlap when A[i][1]>=B[j][0]&&A[i][0]<=B[j][1] This can save a lot of trouble compared to thinking of 6 cases of overlapping conditions!
LC 986 Interval List Intersections revisited
LC 56 Merge Intervals revisited
LC 372 Guess Number Higher or Lower
12/20/2019
LC 904 Fruit Into Baskets revisited
12/23/2019
Merge Sort ... Merge sort practice. Don't forget to return v if v.size()==1 in sort function!
LC 322 Coin Change revisited ... Encountered small runtime error bug.
LC 64 Minimum Path Sum revisited
12/24/2019
LC 1145 Binary Tree Coloring Game
12/27/2019
LC 518 Coin Change 2 ... This is the so-called 0/1 "unlimited" knapsack problem. For the "unlimited" problem you can repeatedly use items as many times as you want whereas in the "regular" problem you can only use and item once. Note that the difference between the "regular" and "unlimited" 0/1 knapsack problem is the way you use the cache table. In both cases you will check the cell directly above (when not choosing current item). However, when choosing a current item, you must look on the same row with the column elements to the left for the "unlimited" problem. For the "regular" problem, you look on the row above with elements to the left column. Very important problem!
LC 273 Integer To English Words
12/28/2019
LC 430 Flatten A Multilevel Doubly Linked List
12/29/2019
LC 1302 Deepest Leaves Sum ... Easy problem.
12/31/2019
LC 692 Top K Frequent Words ... Basically a syntax question. Know how to make custom comparisons with priority_queues. If operator()() is true, second will be returned first.
LC 347 Top K Frequent Elements revisited ... The words problem is trickier due to syntax issues. Idea is the same.
LC 451 Sort Characters By Frequency ... Similar to above.
LC 752 Open The Lock ... Relatively standard BFS problem.
1/1/2020
1/4/2020
LC 535 Encode And Decode Tiny URL
1/5/2020
LC 131 Palindrome Partitioning
LC 516 Longest Palindromic Subsequence ... Rated medium but hard dynamic programming problem. The key is to reaize it can be solved top down with transition equation of DPi,j = 2+DPi+1,j-1 if si==sj or DPi,j=max(DPi+1,j , DPi,j-1) if si!=sj. DPi,j represents longest palindrome you can make from si to sj, index inclusive.
LC 1312 Minimum Insertion Steps To Make A String Palindrome
1/6/2020
LC 283 Moving Zeroes revisited
Several intervals questions.
LC 252 Meeting Rooms revisited ... Intervals question. Sort array based on first element (smaller first). Then, use overlapping conditions v_1>z_0&&v_0<z_1 to assess whether an interval overlaps. Ask clarification about how to treat cases where boundries overlap (this will change overlapping conditions from > to >=).
LC 253 Meeting Rooms II revisited ... Intervals question. Use map to store boundaries(keys) and values(+1 for begin, -1 for end). Go through map from beginning and count maximum number of it->second sums.
LC 452 Minimum Number Of Arrows To Burst Balloons... Sort array based on first element (smaller first). Then, use priority queue to store end of baloon coordinates. If new baloon begin coordinate is after the smallest end coordinate in the PQ, pop all PQ and increment answer by 1.
LC 1094 Car Pooling... Very similar to LC 253.
1/7/2020
LC 1057 Campus Bikes ... Interesting problem. Can make it into O(MN) time complexity.
LC 581 Shortest Unsorted Continuous Subarray
1/8/2020
LC 140 Word Break II ... There is supposedly a DP solution. I used backtracking. Check DP solution later.
1/11/2020
LC 398 Random Pick Index ... Fairly straight forward.
LC 382 Linked List Random Node ... Similar as LC 398.
LC 301 Remove Invalid Parentheses ... Think if there is a way to treat non '(' or ')' differently so it is not backtracking.
1/13/2020
LC 1315 Sum Of Nodes With Even-Valued Grandparent
LC 323 Number Of Connected Components In An Unidirected Graph ... Union find problem. Must review again!
LC 1319 Number Of Operations ... Union find problem. Note that the m map does not guarantee to point to the top parent based on my implementation. Only top parent info (it->first==it->second) is necessary for this question.
LC 547 Friend Circles ... Union find, but a bit more complicated.
LC 684 Redundant Connection...Union find, but a bit more complicated.
1/14/2020
LC 1313 Decompress Run-Length Encoded List ... Example is not clear.
1/15/2020
LC 189 Rotate Array revisited ... Cool trick of flipping the array in three parts solves the problem in O(n) time O(1) memory. The order of when you flip all the vector decides right shift vs left shift.
1/16/2020
LC 611 Valid Triangle Number ... Had been a while since I've done two/three pointer types of problems and found it difficult.
LC 692 Top K Frequent Words revisited ... Custom comparators syntax for priority queues can be tricky to remember.
1/18/2020
1/21/2020
LC 394 Decode String Revisited
LC 128 Longest Consecutive Sequence ... The trick is to use two unordered_sets. Once is to store all elements in the vector. The other is to keep track of numbers already seen. As you go through the vector elements, check whether the number before and after it exists in unordered_set1. If it does and has not been registered in unordered_set2, register it and keep traveling.
1/22/2020
LC 146 LRU Cache revisited ... Revisited the LRU Cache problem. This time the complexity of the data structure has decreased. The trick was for the hash table to store a
pair<int,list<int>::iterator> where the first element is the value and the second element is a pointer to the list with the corresponding key. The list will store keys which will allow us to search for the element that must be deleted when the list size goes over the capacity.
1/28/2020
1/29/2020
LC 1209 Remove All Adjacent Duplicates In String II ... Did not think of using pairs in stacks.
LC 1328 Break A Palindrome ...
2/3/2020
read this [https://leetcode.com/problems/sum-of-subarray-minimums/discuss/178876/stack-solution-with-very-detailed-explanation-step-by-step] ... Simplified solution and did not use alphabet for URL.
TODO ... permutations, best time to buy/sell, DP bootcamp